When implementing a propagator for a constraint, one must decide about variants: When implementing min, should one also implement max? Should one implement linear equations both with and without coefficients? Constrai...
详细信息
ISBN:
(纸本)9783319104287;9783319104270
When implementing a propagator for a constraint, one must decide about variants: When implementing min, should one also implement max? Should one implement linear equations both with and without coefficients? constraint variants are ubiquitous: implementing them requires considerable effort, but yields better performance. this abstract shows how to use views to derive propagator variants where derived propagators are perfect in that they inherit essential properties such as correctness and domain and bounds consistency. Techniques for systematically deriving propagators are developed, and the abstract sketches an implementation architecture for views that is independent of the underlying constraintprogramming system. Evaluation of views implemented in Gecode shows that derived propagators are efficient and that views often incur no overhead. Views have proven essential for implementing Gecode, substantially reducing the amount of code that needs to be written and maintained.
A wide range of constraints can be specified using automata or formal languages. the GRAMMAR constraint restricts the values taken by a sequence of variables to be a string from a given context-free language. Based on...
详细信息
ISBN:
(纸本)9783540749691
A wide range of constraints can be specified using automata or formal languages. the GRAMMAR constraint restricts the values taken by a sequence of variables to be a string from a given context-free language. Based on an AND/OR decomposition, we show that this constraint can be converted into clauses in conjunctive normal form without hindering propagation. Using this decomposition, we can propagate the GRAMMAR constraint in O(n(3)) time. the decomposition also provides an efficient incremental propagator. Down a branch of the search tree of length k, we can enforce GAC k times in the same O(n(3)) time. On specialized languages, running time can be even better. For example, propagation of the decomposition requires just O(n|delta|) time for regular languages where |delta| is the size of the transition table of the automaton recognizing the regular language. Experiments on a shift scheduling problem with a constraint solver and a state of the art SAT solver show that we can solve problems using this decomposition that defeat existing constraint solvers.
Competition and cooperation can boost the performance of search. Both can be implemented with a portfolio of algorithms which run in parallel, give hints to each other and compete for being the first to finish and del...
详细信息
ISBN:
(纸本)3540292381
Competition and cooperation can boost the performance of search. Both can be implemented with a portfolio of algorithms which run in parallel, give hints to each other and compete for being the first to finish and deliver the solution. In this paper we present a new generic framework for the application of algorithms for distributed constraint satisfaction which makes use of both cooperation and competition. this framework improves the performance of two different standard algorithms by one order of magnitude and can reduce the risk of poor performance by up to three orders of magnitude. Moreover it greatly reduces the classical idleness flaw usually observed in distributed hierarchy-based searches. We expect our new methods to be similarly beneficial for any tree-based distributed search and describe ways on how to incorporate them.
Scheduling a subset of solvers belonging to a given portfolio has proven to be a good strategy when solving constraint Satisfaction Problems (CSPs). In this paper, we show that this approach can also be effective for ...
详细信息
ISBN:
(纸本)9783319104287;9783319104270
Scheduling a subset of solvers belonging to a given portfolio has proven to be a good strategy when solving constraint Satisfaction Problems (CSPs). In this paper, we show that this approach can also be effective for constraint Optimization Problems (COPs). Unlike CSPs, sequential execution of optimization solvers can communicate information in the form of bounds to improve the performance of the following solvers. We provide a hybrid and flexible portfolio approach that combines static and dynamic time splitting for solving a given COP. Empirical evaluations show the approach is promising and sometimes even able to outperform the best solver of the porfolio.
Counting-based branching heuristics such as maxSD were shown to be effective on a variety of constraint satisfaction problems. these heuristics require that we equip each family of constraints with a dedicated algorit...
详细信息
ISBN:
(纸本)9783642406263;9783642406270
Counting-based branching heuristics such as maxSD were shown to be effective on a variety of constraint satisfaction problems. these heuristics require that we equip each family of constraints with a dedicated algorithm to compute the local solution density of variable assignments, much as what has been done with filtering algorithms to apply local inference. this paper derives an exact polytime algorithm to compute solution densities for a spanning tree constraint, starting from a known result about the number of spanning trees in a graph. We then empirically compare branching heuristics based on that result with other generic heuristics.
We propose an adaptation of the Embarrassingly Parallel Search (EPS) method for data centers. EPS is a simple but efficient method for parallel solving of CSPs. EPS decomposes the problem in many distinct subproblems ...
详细信息
ISBN:
(纸本)9783319104287;9783319104270
We propose an adaptation of the Embarrassingly Parallel Search (EPS) method for data centers. EPS is a simple but efficient method for parallel solving of CSPs. EPS decomposes the problem in many distinct subproblems which are then solved independently by workers. EPS performed well on multicores machines (40), but some issues arise when using more cores in a datacenter. Here, we identify the decomposition as the cause of the degradation and propose a parallel decomposition to address this issue. thanks to it, EPS gives almost linear speedup and outperforms work stealing by orders of magnitude using the Gecode solver.
Stochastic constraint Satisfaction Problems (SCSPs) are a powerful modeling framework for problems under uncertainty. To solve them is a P-Space task. the only solution approach to date compiles down SCSPs into classi...
详细信息
ISBN:
(纸本)9783642042430
Stochastic constraint Satisfaction Problems (SCSPs) are a powerful modeling framework for problems under uncertainty. To solve them is a P-Space task. the only solution approach to date compiles down SCSPs into classical CSPs. this allows the rouse of classical constraint solvers to solve SCSPs, but at the cost of increased space requirements and weak constraint propagation. this paper tries to overcome some of these drawbacks by automatically synthesizing filtering algorithms for global chance-constraints. these filtering algorithms are parameterized by propagators for the deterministic version of the chance-constraints. this approach allows the rouse of existing propagators in current, constraint solvers and it enhances constraint propagation. Experiments show the benefits of this novel approach.
this paper presents a global constraintthat enforces rules written in a language based on arithmetic and first-order logic to hold among a set of objects. In a first step, the rules are rewritten to Quantifier-Free P...
详细信息
ISBN:
(纸本)9783540859574
this paper presents a global constraintthat enforces rules written in a language based on arithmetic and first-order logic to hold among a set of objects. In a first step, the rules are rewritten to Quantifier-Free Presburger Arithmetic (QFPA) formulas. Secondly. such formulas arc compiled to generators of k-dimensional forbidden sets. Such generators are a generalization of the indexicals of cc(FD). Finally, the forbidden sets generated by such indexicals are aggregated by a sweep-based algorithm and used for filtering. the business rules allow to express a great variety of packing and placement constraints, while admitting effective filtering of the domain variables of the k-dimensional object, without the need to use spatial data structures.
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 o...
详细信息
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/ constraintprogramming (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 withthe 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.
In this paper we present new techniques for improving backtracking based Quantified constraint Satisfaction Problem (QCSP) solvers. QCSP is a generalization of CSP in which variables are either universally or existent...
详细信息
ISBN:
(纸本)9783540749691
In this paper we present new techniques for improving backtracking based Quantified constraint Satisfaction Problem (QCSP) solvers. QCSP is a generalization of CSP in which variables are either universally or existentially quantified and these quantifiers can be alternated in arbitrary ways. Our main new technique is solution directed backjumping (SBJ). In analogue to conflict directed backjumping, SBJ allows the solver to backtrack out of solved sub-trees without having to find all of the distinct solutions normally required to validate the universal variables. Experiments withthe solver QCSP-Solve demonstrate that SBJ can improve its performance on random instances by orders of magnitude. In addition to this contribution, we demonstrate that performing varying levels of propagation for universal vs. existential variables can also be useful for enhancing performance. Finally, we discuss some techniques that are technically interesting but do not yet yield empirical improvements.
暂无评论