We propose a surprisingly simple new way of breaking all value symmetries withconstraints. Our method requires the addition of one variable per value of the problem plus a linear number of binary constraints. the set...
详细信息
We present an interface between the ECLiPSe constraint logic programming system and the GAP computational abstract algebra system. the interface provides a method for efficiently dealing with large numbers of symmetri...
详细信息
this paper studies how to verify the conformity of a program with its specification and proposes a novel constraint-programming framework for bounded program verification (cpBPV). the cpBPV framework uses constraint s...
详细信息
ISBN:
(纸本)3540859578
this paper studies how to verify the conformity of a program with its specification and proposes a novel constraint-programming framework for bounded program verification (cpBPV). the cpBPV framework uses constraint stores to represent boththe specification and the program and explores execution paths of bounded length nondeterministically. the cpBPV framework detects non-conformities and provides counter examples when a path of bounded lengththat refutes some properties exists. the input program is partially correct under the boundness restrictions, if each constraint store so produced implies the post-condition. cpBPV does not explore spurious execution paths, as it incrementally prunes execution paths early by detecting that the constraint store is not consistent. cpBPV uses the rich language of constraintprogramming to express the constraint store. Finally, cpBPV is parameterized with a list of solvers which are tried in sequence, starting withthe least expensive and less general. Experimental results often produce orders of magnitude improvements over earlier approaches, running times being often independent of the size of the variable domains. Moreover, cpBPV was able to detect subtle errors in some programs for which other frameworks based on bounded model checking have failed.
A conditional constraint satisfaction problem (CCSP) extends a standard constraint satisfaction problem (cpS) with a conditionbased component that controls what variables participate in problem solutions. CCSPs adequa...
详细信息
the Distributed constraint Optimization Problem (DCOP) is an elegant paradigm for modeling and solving multi-agent problems which are distributed in nature, and where agents cooperate to optimize a global objective wi...
详细信息
ISBN:
(数字)9783319983349
ISBN:
(纸本)9783319983349;9783319983332
the Distributed constraint Optimization Problem (DCOP) is an elegant paradigm for modeling and solving multi-agent problems which are distributed in nature, and where agents cooperate to optimize a global objective within the confines of localized communication. Since solving DCOPs optimally is NP-hard, recent effort in the development of DCOP algorithms has focused on incomplete methods. Unfortunately, many of such proposals do not provide quality guarantees or provide a loose quality assessment. thus, this paper proposes the Distributed Large Neighborhood Search (DLNS), a novel iterative local search framework to solve DCOPs, which provides guarantees on solution quality refining lower and upper bounds in an iterative process. Our experimental analysis of DCOP benchmarks on several important classes of graphs illustrates the effectiveness of DLNS in finding good solutions and tight upper bounds in both problems with and without hard constraints.
constraintprogramming (cp) is a healthy research area in the academic community. the growing number of participants to the cpconference series, as well as the number of workshops around cp is a good evidence of it. ...
ISBN:
(纸本)3540232419
constraintprogramming (cp) is a healthy research area in the academic community. the growing number of participants to the cpconference series, as well as the number of workshops around cp is a good evidence of it. Many major conferences have a cp track, both in artificial intelligence, and in operations research. the existence of several commercial companies that offer cp tools and services is a further evidence of the value of cp as an industrial technology. ILOG is one of such companies. One of our uniqueness, as far as cp is concerned, is that the research and development team that produces our cp products is also responsible for the development of our mathematical programming (MP) tool, namely ILOG cpLEX. this provides a unique opportunity to contrast the way these products are developed, marketed and used. In this paper we argue that current cp technology is much too complex to use for the average engineer. Worse, we believe that much of the research occurring in the cp academic community makes this even worse every year. the rest of the paper provides evidence for this claim, and suggests ways to address the issue of simplicity of use by looking at how a similar issue has been addressed in the mathematical programming community.
作者:
Junker, UlrichILOG
9 rue de Verdun BP 85 Gentilly CedexF-94253 France
Finding good problem decompositions is crucial for solving large-scale key/lock configuration problems. We present a novel approach to problem decomposition where the detection of a subproblem hierarchy is formulated ...
详细信息
A constraint satisfaction problem instance consists of a collection of variables that need to have values assigned to them. the assignments are limited by constraints that force the values taken by certain collections...
详细信息
ISBN:
(纸本)3540202021
A constraint satisfaction problem instance consists of a collection of variables that need to have values assigned to them. the assignments are limited by constraints that force the values taken by certain collections of variables (the constraint scopes) to satisfy specified properties (the constraint relations). As the general CSP problem is NP-hard there has been significant effort devoted to discovering tractable subproblems of the CSP. the structure of a CSP instance is defined to be the hypergraph formed by the constraint scopes. Restricting the possible structure of the CSP instances has been a successful way of identifying tractable subproblems. the language of a CSP instance is defined to be the set of constraint relations of the instance. Restricting the language allowed for CSP instances has also yielded many interesting tractable subproblems. Almost all known tractable subproblems are either structural or relational. In this paper we construct tractable subproblems of the general CSP that are neither defined by structural nor relational properties. these new tractable classes are related to tractable languages in much the same way that general decompositions (cutset, tree-clustering, etc.) are related to acyclic decompositions. It may well be that our results will begin to make language based tractability of more practical interest. We show that our theory allows us to properly extend the binary maxclosed language based tractable class, which is maximal as a tractable binary constraint language. Our theory also explains the tractability of the constraint representation of the Stable Marriage Problem which has not been amenable to existing explanations of tractability. In fact we provide a uniform explanation for the tractability of the class of maxclosed CSPs and the SMP. there has been much work done on so called renamable HORN theories which are a tractable subproblem of SAT. It has been shown that renamable HORN theories are tractably identifiable and
Arc consistency plays a central role in solving constraint Satisfaction Problems. this is the reason why many algorithms have been proposed to establish it. Recently, an algorithm called AC2001 and AC3.1 has been inde...
详细信息
Computer trading systems are essential for today9;s financial markets where the trading systems9; correctness is of paramount economical significance. Automated random testing is a useful technique to find bugs ...
详细信息
暂无评论