By introducing the Regular Membership constraint, Gilles Pesant pioneered the idea of basing constraints on formal languages. the paper presented here is highly motivated by this work, taking the obvious next step, na...
详细信息
ISBN:
(纸本)3540462678
By introducing the Regular Membership constraint, Gilles Pesant pioneered the idea of basing constraints on formal languages. the paper presented here is highly motivated by this work, taking the obvious next step, namely to investigate constraints based on grammars higher up in the Chomsky hierarchy. We devise an arc-consistency algorithm for context-free grammars, investigate when logic combinations of grammar constraints are tractable, show how to exploit non-constant size grammars and reorderings of languages, and study where the boundaries run between regular, context-free, and context-sensitive grammar filtering.
Consider a constraint on a sequence of variables functionally determining a result variable that is unchanged under reversal of the sequence. Most such constraints have a compact encoding via an automaton augmented wi...
详细信息
ISBN:
(纸本)9783319104287;9783319104270
Consider a constraint on a sequence of variables functionally determining a result variable that is unchanged under reversal of the sequence. Most such constraints have a compact encoding via an automaton augmented with accumulators, but it is unknown how to maintain domain consistency efficiently for most of them. Using such an automaton for such a constraint, we derive an implied constraint between the result variables for a sequence, a prefix thereof, and the corresponding suffix. We show the usefulness of this implied constraint in constraint solving, both by local search and by propagation-based systematic search.
While the efficiency and scalability of modern SARI technology offers an intriguing alternative approach to constraint Solving via translation to SAT, previous work has mostly focused of the translation of specific ty...
详细信息
ISBN:
(纸本)9783540859574
While the efficiency and scalability of modern SARI technology offers an intriguing alternative approach to constraint Solving via translation to SAT, previous work has mostly focused of the translation of specific types of constraints, such as pseudo Boolean constraints;finite integer linear constraints, and constraints given as explicit listings of allowed triples. BY contrast, we present a translation of constraint models to SAT at language level, using the recently proposed constraint modeling language MiniZine, such that any satisfaction or optimization problem written in the language (not involving floats) can be automatically Booleanized and solved by one or more calls to a SAT solver. We discuss the strengths and weaknesses of such a universal constraint solver, Mid report oil a large-scale empirical evaluation of it against two existing solvers for MiniZinc: the finite domain solver distributed with MiniZinc and one based on the Gecode constraint;programming platform. our results indicate that, Booleanization indeed offers a competitive alternative, exhibiting superior performance on some classes of problems involving large numbers of constraints and complex integer arithmetic, ill addition to, naturally, problems dial arc already largely Boolean.
In this report weintroduce a new hybrid class for which arcconsistency is a decision procedure. this new hybrid class includes infinitely many instances whose tractability is not assured by any tractable language or s...
详细信息
this paper deals with methods exploiting tree-decomposition approaches for solving constraint networks. We consider here the practical efficiency of these approaches by defining five classes of variable orders more an...
详细信息
ISBN:
(纸本)3540462678
this paper deals with methods exploiting tree-decomposition approaches for solving constraint networks. We consider here the practical efficiency of these approaches by defining five classes of variable orders more and more dynamic which guarantee time complexity bounds from O(exp(w+1)) to O(exp(2(w+k))), with w the "tree-width" of a CSP and k a constant. Finally, we assess practically their relevance.
We present an incomplete filtering algorithm for the circuit constraint. the filter removes redundant values by eliminating nonhamiltonian edges from the associated graph. We identify nonhamiltonian edges by analyzing...
详细信息
ISBN:
(纸本)3540462678
We present an incomplete filtering algorithm for the circuit constraint. the filter removes redundant values by eliminating nonhamiltonian edges from the associated graph. We identify nonhamiltonian edges by analyzing a smaller graph with labeled edges that is defined on a separator of the original graph. the complexity of the procedure for each separator S is approximately O(vertical bar S vertical bar(5)). We found that it identified all infeasible instances and eliminated about one-third of the redundant domain elements in feasible instances.
Symmetries are one of the difficulties constraintprogramming users have to deal with. One way to get rid of symmetries is to add lex constraints. However, it can adversely affect the efficiency of a tree search metho...
详细信息
ISBN:
(纸本)3540462678
Symmetries are one of the difficulties constraintprogramming users have to deal with. One way to get rid of symmetries is to add lex constraints. However, it can adversely affect the efficiency of a tree search method if the lex constraints remove the solution that would have been found at the first place. We propose to use an alternative filtering algorithm which does not exclude the first solution. We present both a theoretical analysis and some experimental evidence that it is as efficient as lex constraints. We also show that its efficiency does not depend much on the variable ordering used in the tree search. Last, we show that it can prune more nodes than the SBDS method.
this paper presents a robust approach to solve Hoist Scheduling Problems (HSPs) based on an integration of constraint Logic programming (CLP) and Mixed Integer programming (MIP). By contrast with previous dedicated mo...
详细信息
ISBN:
(纸本)3540652248
this paper presents a robust approach to solve Hoist Scheduling Problems (HSPs) based on an integration of constraint Logic programming (CLP) and Mixed Integer programming (MIP). By contrast with previous dedicated models and algorithms for solving classes of HSPs, we define only one model and run different solvers. the robust approach is achieved by using a CLP formalism. We show that our models for different classes of industrial HSPs are all based on the same generic model. In our hybrid algorithm search is separated from the handling of constraints. constraint handling is performed by constraint propagation and linear constraint solving. Search is applied by labelling of boolean and integer variables. Computational experience shows that the hybrid algorithm, combining CLP and MIP salvers, solves classes of HSPs which cannot be handled by previous dedicated algorithms. For example, the hybrid algorithm derives an optimal solution, and proves its optimality, for multiple-hoists scheduling problems.
In this paper we compare the performance of three constraint weighting schemes with one of the latest and fastest WSAT heuristics: novelty. We extend previous results from satisfiability testing by looking at the broa...
详细信息
ISBN:
(纸本)3540666265
In this paper we compare the performance of three constraint weighting schemes with one of the latest and fastest WSAT heuristics: novelty. We extend previous results from satisfiability testing by looking at the broader domain of constraint satisfaction and test for differences in performance using randomly generated problems and problems based on realistic situations and assumptions. We find constraint weighting produces fairly consistent behaviour within problem domains, and is more influenced by the number and interconnectedness of constraints than the realism or randomness of a problem. We conclude that constraint weighting is better suited to smaller structured problems, where it is can clearly distinguish between different constraint groups.
We present tin incremental refinement algorithm for approximate compilation of constraint satisfaction models into multivalued decision diagrams (MDDs). the algorithm uses a vertex splitting operation that relies on t...
详细信息
ISBN:
(纸本)9783540859574
We present tin incremental refinement algorithm for approximate compilation of constraint satisfaction models into multivalued decision diagrams (MDDs). the algorithm uses a vertex splitting operation that relies on the detection of equivalent paths in the MDD. Although the algorithm is quite general, it can be adapted to exploit constraint structure by specializing the equivalence tests for partial assignments to particular constraints. We show how to modify the algorithm in a principled way to obtain an approximate MDD when the exact MDD is too large for practical purposes. this is done by replacing the equivalence test with a constraint-specific measure of distance. We demonstrate the value of the approach for approximate and exact MDD compilation and evaluate its benefits in one of the main MDD application domains, interactive configuration.
暂无评论