检索结果-内蒙古大学图书馆

19th Annual international conference on principles and practice of constraint programming (cp)

作者： Schaub, Torsten Simon Fraser Univ Burnaby BC V5A 1S6 Canada

ISBN: (纸本)9783642406263;9783642406270

Answer Set programming (ASP; [1,2,3]) is a declarative problem solving approach, combining a rich yet simple modeling language with high-performance Boolean constraint solving capacities. ASP is particularly suited for modeling problems in the area of Knowledge Representation and Reasoning involving incomplete, inconsistent, and changing information. As such, it offers, in addition to satisfiability testing, various reasoning modes, including different forms of model enumeration, intersection or unioning, as well as multi-criteria and -objective optimization. From a formal perspective, ASP allows for solving all search problems in NP (and NP NP ) in a uniform way. Hence, ASP is wellsuited for solving hard combinatorial search problems, like system design and timetabling. Prestigious applications of ASP include composition of Renaissance music [4], decision support systems for NASA shuttle controllers [5], reasoning tools in systems biology [6,7,8] and robotics [9,10], industrial team-building [11], and many more. the versatility of ASP is nicely reflected by the ASP solver clasp [12], winning first places at various solver competitions, such as ASP,MISC, PB, and SAT competitions. the solver clasp is at the heart of the open source platform Potassco hosted at *** . Potassco stands for the “Potsdam Answer Set Solving Collection-[13] and has seen more than 30000 downloads world-wide since its inception at the end of 2008. the talk will start with an introduction to ASP, its modeling language and solving methodology, and portray some distinguished ASP systems.

关键词： Problem solving

来源：评论

学校读者我要写书评

暂无评论

A Join-Based Hybrid Parameter for constraint Satisfaction 25th

A Join-Based Hybrid Parameter for Constraint Satisfaction

引用

25th international conference on the principles and practice of constraint programming (cp)

作者： Ganian, Robert Ordyniak, Sebastian Szeider, Stefan TU Wien Algorithms & Complex Grp Vienna Austria Univ Sheffield Algorithms Grp Sheffield S Yorkshire England

ISBN: (纸本)9783030300487

We propose joinwidth, a new complexity parameter for the constraint Satisfaction Problem (CSP). the definition of joinwidth is based on the arrangement of basic operations on relations (joins, projections, and pruning), which inherently reflects the steps required to solve the instance. We use joinwidth to obtain polynomial-time algorithms (if a corresponding decomposition is provided in the input) as well as fixed-parameter algorithms (if no such decomposition is provided) for solving the CSP. Joinwidth is a hybrid parameter, as it takes both the graphical structure as well as the constraint relations that appear in the instance into account. It has, therefore, the potential to capture larger classes of tractable instances than purely structural parameters like hypertree width and the more general fractional hypertree width (fhtw). Indeed, we show that any class of instances of bounded fhtw also has bounded joinwidth, and that there exist classes of instances of bounded joinwidth and unbounded fhtw, so bounded joinwidth properly generalizes bounded fhtw. We further show that bounded joinwidth also properly generalizes several other known hybrid restrictions, such as fhtw with degree constraints and functional dependencies. In this sense, bounded joinwidth can be seen as a unifying principle that explains the tractability of several seemingly unrelated classes of CSP instances.

关键词： constraint satisfaction problems

来源：评论

学校读者我要写书评

暂无评论

Specialised constraints for stable matching problems

引用

11th international conference on principles and practice of constraint programming (cp 2005)

作者： Unsworth, C Prosser, P Univ Glasgow Dept Comp Sci Glasgow G12 8QQ Lanark Scotland

ISBN: (纸本)3540292381

the stable marriage problem (SM) and the Hospital / Residents problem (HR) are both stable matching problems. they consist of two sets of objects that need to be matched to each other;in SM men to women, and in HR residents to hospitals. Each set of objects expresses a ranked preference for the objects in the other set, in the form of a preference list. the problem is then to find a matching of one set to the other such that the matching is stable. A matching is stable iff it contains no blocking pairs. A blocking pair in a matching M consists of two objects x and y one from each set(x = man and y = woman for SM or x = hospital and y = resident in HR), such that x and y are not matched in M and both x and y would rather be matched to each other than to there assignment in M. Algorithms have been published for both of these problems and optimal constraint models have been published for the stable marriage problem. So the main question would be why the need for specialised constraint for these problems? the SM algorithm and the optimal constraint encodings all have a time complexity of O(n²), but in practice it can take over a minute for the constraint models to find a solution to a problem of size 45 while the SM algorithm can find a solution in less than two hundredths of a second. there have not been any optimal HR constraint models published, but I assume the same performance gap would exist. the advantage of the constraint solutions are their versatility. Many harder valiants of the stable matching problems can be solved by adding simple side constraints to the existing;models, this is not possible with the matching algorithms. So the motivation behind a specialised constraint is to try and combine the efficiency of the algorithm with the versatility of the constraint models. In the full version of this paper I discuss issues concerning the creation of specialised constraints to solve these problems. I then go on to present some empirical results that

关键词： constraint theory

来源：评论

学校读者我要写书评

暂无评论

Maintaining Soft Arc Consistencies in BnB-ADOPT⁺ during Search

Maintaining Soft Arc Consistencies in BnB-ADOPT<SUP>+</SUP> ...

引用

19th Annual international conference on principles and practice of constraint programming (cp)

作者： Gutierrez, Patricia Lee, Jimmy H. M. Lei, Ka Man Mak, Terrence W. K. Meseguer, Pedro Univ Autonoma Barcelona IIIA CSIC Bellaterra 08193 Spain Chinese Univ Hong Kong Dept Comp Sci & Engn Shatin Peoples R China NICTA Victoria Lab Melbourne Vic 3010 Australia Univ Melbourne Melbourne Vic 3010 Australia

ISBN: (纸本)9783642406263;9783642406270

Gutierrez and Meseguer show how to enforce consistency in BnB-ADOPT(+) for distributed constraint optimization, but they consider unconditional deletions only. However, during search, more values can be pruned conditionally according to variable instantiations that define subproblems. Enforcing consistency in these subproblems can cause further search space reduction. We introduce efficient methods to maintain soft arc consistencies in every subproblem during search, a non trivial task due to asynchronicity and induced overheads. Experimental results show substantial benefits on three different benchmarks.

关键词： constraint theory

来源：评论

学校读者我要写书评

暂无评论

Decomposition of the NVALUE constraint

Decomposition of the NVALUE Constraint

引用

16th Annual international conference on the principles and practice of constraint programming

作者： Bessiere, Christian Katsirelos, George Narodytska, Nina Quimper, Claude-Guy Walsh, Toby CNRS LIRMM Montpellier France CNRS CRIL Lens France NICTA Sydney NSW Australia Univ NSW Sydney NSW Australia Univ Laval Quebec City PQ G1K 7P4 Canada

ISBN: (纸本)9783642153952

We study decompositions of the global NVALUE constraint. Our main contribution is theoretical: we show that there are propagators for global constraints like NVALUE which decomposition can simulate with the same time complexity but with a much greater space complexity. this suggests that the benefit of a global propagator may often not be in saving time but in saving space. Our other theoretical contribution is to show for the first time that range consistency can be enforced on NVALUE with the same worst-case time complexity as bound consistency. Finally, the decompositions we study are readily encoded as linear inequalities. We are therefore able to use them in integer linear programs.

关键词： Integer programming

来源：评论

学校读者我要写书评

暂无评论

Robustness and Stability in constraint programming under Dynamism and Uncertainty

Robustness and Stability in Constraint Programming under Dyn...

引用

20th international conference on the principles and practice of constraint programming (cp)

作者： Climent, Laura Wallace, Richard J. Salido, MiguelA. Barber, Federico Natl Univ Ireland Univ Coll Cork Insight Ctr Data Analyt Cork Ireland Univ Politecn Valencia Inst Automat Informat Ind Madrid Spain

ISBN: (纸本)9783319104287;9783319104270

Because of the dynamism and uncertainty associated with many real life problems, these problems and their associated constraint Satisfaction Problem (CSP) models may change over time; thus an earlier solution found for the latter may become invalid. Moreover, many approaches proposed in the literature cannot be applied when the required information about dynamism is unknown ([9], [4], [5], [11], [10], etc.). this fact has motivated us to consider dynamic situations where, in addition, only limited assumptions about changes can be made. Our analysis focuses on CSPs with ordered and discrete domains that model problems for which the order over the elements of the domain is significant. In these cases, a common type of change that problems may undergo is restrictive modifications over the bounds of the solution space. A discussion of these assumptions, their motivation and real life examples can be found in [3]. In this paper, we present an algorithm that meets the goal of combining solution stability (meaning that solutions can often be repaired using other similar values if they undergo a value loss) and robustness (meaning that solutions have a high likelihood of remaining solutions after changes). the desireability of this combination of features was noted in the survey [8]. Furthermore, in this work we have extended both concepts to apply to the type of CSP analyzed. the paper is organized as follows. Section 2 presents the new conceptions of robustness and stability. Section 3 describes our approach for finding solutions that simultaneously meet both these criteria. In Section 4 we present some experimental results. Section 5 gives conclusions.

关键词： constraint satisfaction problems

来源：评论

学校读者我要写书评

暂无评论

Memoisation for constraint-based local search

Memoisation for constraint-based local search

引用

15th international conference on principles and practice of constraint programming, cp 2009

作者： Ågren, Magnus Swedish Institute of Computer Science Box 1263 Kista SE 164 29 Sweden

ISBN: (纸本)3642042430

We present a memoisation technique for constraint-based local search based on the observation that penalties with respect to some interchangeable elements need only be calculated once. We apply the technique to constraint-based local search on set variables, and demonstrate the usefulness of the approach by significantly speeding up the penalty calculation of a commonly used set constraint. © 2009 Springer Berlin Heidelberg.

关键词： Local search (optimization)

来源：评论

学校读者我要写书评

暂无评论

principles and practice of constraint programming – cp 2004 1

引用

丛书名： Lecture Notes in Computer Science

1000年

作者： Mark Wallace

ISBN: (数字)9783540302018

ISBN: (纸本)9783540232414

the 10th international conference on the principles and practice of constraint programming (cp 2003) was held in Toronto, Canada, during September 27 – October 1, 2004. Information about the conference can be found on the Web at http://***/~cp2004/ constraint programming (cp) is about problem modelling, problem solving, programming, optimization, software engineering, databases, visualization, user interfaces, and anything to do with satisfying complex constraints. It reaches into mathematics, operations research, arti?cial intelligence, algorithms, c- plexity, modelling and programming languages, and many aspects of computer science. Moreover, cp is never far from applications, and its successful use in industry and government goes hand in hand with the success of the cp research community. constraintprogrammingcontinuesto beanexciting,?ourishingandgrowing research?eld,***, from 158 submissions, we chose 46 to be published in full in the proceedings. Instead of selecting one overall best paper, we picked out four “distinguished” papers – though we were tempted to select at least 12 such papers. In addition we included 16 short papersin the proceedings– these were presentedas posters at cp 2004. this volume includes summaries of the four invited talks of cp 2004. Two speakers from industry were invited. However these were no ordinary industrial representatives,buttwoofthe leadingresearchersinthe cpcommunity:Helmut Simonis of Parc Technologies, until its recent takeover by Cisco Systems; and Jean Francoi ¸ s Puget, Director of Optimization Technology at ILOG. the other two invited speakers are also big movers and shakers in the researchcommunity.

关键词： Software Engineering/programming and Operating Systems programming Techniques programming Languages, Compilers, Interpreters Logics and Meanings of Programs Mathematical Logic and Formal Languages Artificial Intelligence

来源：评论

学校读者我要写书评

暂无评论

constraints in Software Testing, Verification and Analysis CSTVA 2013

Constraints in Software Testing, Verification and Analysis C...

引用

6th IEEE international conference on Software Testing, Verification and Validation (ICST)

作者： Cadar, Cristian Dadeau, Frederic Univ London Imperial Coll Sci Technol & Med South Kensington Campus London SW7 2AZ England INRIA CASSIS FEMTO ST Inst F-25030 Besancon France

ISBN: (纸本)9780769549934;9781479913244

Recent years have seen an increasing interest in the application of constraint solving techniques to test, verify and analyze software systems. A significant body of constraint-based techniques has been proposed and investigated in the context of test input generation, model-based testing, symbolic execution, static analysis, program verification, and many other areas. these techniques use or extend constraint solvers such as SAT and SMT solvers to reason about boolean, integer, real and floating-point data types, as well as complex data structures, control structures, method calls and other program features. the constraint systems that result from this work usually share many common features and are relevant to a variety of application domains. Following a first meeting held with the principles and practice of constraint programming (cp) conference in 2006, and three subsequent meetings at the international conference on Software Testing, Verification and Validation (ICST) in 2010, 2011 and 2012, the aim of this paper is to bring together researchers and practitioners working in constraint-based software testing, verification and analysis, to investigate future developments in this research field.

关键词： constraint handling formal verification program testing

来源：评论

学校读者我要写书评

暂无评论

An MDD-based generalized arc consistency algorithm for positive and negative table constraints and some global constraints

引用

constraintS 2010年第2期15卷 265-304页

作者： Cheng, Kenil C. K. Yap, Roland H. C. Chinese Univ Hong Kong Dept Comp Sci & Engn Hong Kong Hong Kong Peoples R China Natl Univ Singapore Sch Comp Singapore 117548 Singapore

A table constraint is explicitly represented as its set of solutions or non-solutions. this ad hoc (or extensional) representation may require space exponential to the arity of the constraint, making enforcing GAC expensive. In this paper, we address the space and time inefficiencies simultaneously by presenting the mddc constraint. mddc is a global constraint that represents its (non-)solutions with a multi-valued decision diagram (MDD). the MDD-based representation has the advantage that it can be exponentially smaller than a table. the associated GAC algorithm (called mddc) has time complexity linear to the size of the MDD, and achieves full incrementality in constant time. In addition, we show how to convert a positive or negative table constraint into an mddc constraint in time linear to the size of the table. Our experiments on structured problems, car sequencing and still-life, show that mddc is also a fast GAC algorithm for some global constraints such as sequence and regular. We also show that mddc is faster than the state-of-the-art generic GAC algorithms in Gent et al. (2007), Lecoutre and Szymanek (2006), Lhomme and R,gin (2005) for table constraint.

关键词： Ad hoc constraint Global constraint Table constraint Positive constraint Negative constraint Multi-valued decision diagram Generalized arc consistency

来源：评论

学校读者我要写书评

暂无评论

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：