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.
constraint Violation Minimization Problems arise when dealing with over-constrained CSPs. Unfortunately, experiments and practice show that they quickly become too large and too difficult to be optimally solved. In th...
详细信息
ISBN:
(纸本)3540652248
constraint Violation Minimization Problems arise when dealing with over-constrained CSPs. Unfortunately, experiments and practice show that they quickly become too large and too difficult to be optimally solved. In this context, multiple methods (limited tree search, heuristic or stochastic local search) are available to produce non-optimal, but good quality solutions, and thus to provide the user with anytime upper bounds of the problem optimum. On the other hand, few methods are available to produce anytime lower bounds of this optimum. In this paper, we explore some ways of producing such bounds. All of them are algorithmic variants of a Branch and Bound search. More specifically, we show that a new algorithm, resulting from a combination of the Russian Doll Search and Iterative Deepening algorithms, clearly outperforms five known algorithms and allows high lower bounds to be rapidly produced.
Relational consistency algorithms are instrumental for solving difficult instances of constraint Satisfaction Problems (CSPs), often allowing backtrack-free search. In this paper, we improve an algorithm for enforcing...
详细信息
ISBN:
(纸本)9783319104287;9783319104270
Relational consistency algorithms are instrumental for solving difficult instances of constraint Satisfaction Problems (CSPs), often allowing backtrack-free search. In this paper, we improve an algorithm for enforcing relational consistency by exploiting the property that the constraints of the dual encoding of a CSP are piecewise functional. this property allows us to partition a CSP relation into blocks of equivalent tuples at varying levels of granularity. Our new algorithm dynamically exploits those partitions. Our experiments show a significant improvement of the processing time for enforcing relational consistency.
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.
Tractability results for structural subproblems have generally been considered for explicit relations listing the allowed assignments. In this paper we define a representation which allows us to express constraint rel...
详细信息
ISBN:
(纸本)3540462678
Tractability results for structural subproblems have generally been considered for explicit relations listing the allowed assignments. In this paper we define a representation which allows us to express constraint relations as either an explicit set of allowed labelings, or an explicit set of disallowed labelings, whichever is smaller. We demonstrate a new structural width parameter, which we call the interaction width, that when bounded allows us to carry over well known structural decompositions to this more concise representation. Our results naturally derive new structurally tractable classes for SAT.
Several combinatorial problems, such as car sequencing and rostering, feature sequence constraints, restricting the number of occurrences of certain values in every subsequence of a given length. We present three new ...
详细信息
Several combinatorial problems, such as car sequencing and rostering, feature sequence constraints, restricting the number of occurrences of certain values in every subsequence of a given length. We present three new filtering algorithms for the sequence constraint, including the first that establishes domain consistency in polynomial time. the filtering algorithms have complementary strengths: One borrows ideas from dynamic programming;another reformulates it as a regular constraint;the last is customized. the last two algorithms establish domain consistency, and the customized one does so in polynomial time. We provide experimental results that demonstrate the practical usefulness of each. We also show that the customized algorithm applies naturally to a generalized version of the sequence constraintthat allows subsequences of varied lengths. the significant computational advantage of using a single generalized sequence constraint over a semantically equivalent collection of among or sequence constraints is demonstrated empirically.
Cost based filtering is a novel approach that combines techniques from Operations Research and constraintprogramming to filter from decision variable domains values that, do not lead to better solutions [7]. Stochast...
详细信息
ISBN:
(纸本)9783540859574
Cost based filtering is a novel approach that combines techniques from Operations Research and constraintprogramming to filter from decision variable domains values that, do not lead to better solutions [7]. Stochastic: constraintprogramming is a. framework for modeling combinatorial optimization problems that, involve uncertainty [19]. In this work;we show how to perform cost;based filtering for certain classes of stochastic constraint, programs. Our approach is based oil a set of known inequalities borrowed from Stochastic programming - a branch of OR. concerned with modeling and solving problems involving. uncertainty. We discuss bound generation and cost-based domain filtering procedures for a well-known problem in the Stochastic. programming literature, the static stochastic knapsack problem. We also apply our technique to a stochastic sequencing problem. Our results clearly show the value of the proposed approach over;I pure scenario-based Stochastic constraintprogramming formulation both in terms of explored nodes and run times.
Dual Consistency (DC) is a property of constraint Networks (CNs) which is equivalent, in its unrestricted form, to Path Consistency (PC). the principle is to perform successive singleton checks (i.e. enforcing arc con...
详细信息
ISBN:
(纸本)9783540749691
Dual Consistency (DC) is a property of constraint Networks (CNs) which is equivalent, in its unrestricted form, to Path Consistency (PC). the principle is to perform successive singleton checks (i.e. enforcing arc consistency after the assignment of a value to a variable) in order to identify inconsistent pairs of values, until a fixpoint is reached. In this paper, we propose two new algorithms, denoted by sDC2 and sDC3, to enforce (strong) PC following the DC approach. these algorithms can be seen as refinements of Mac Gregor's algorithm as they partially and totally exploit the incrementality of the underlying Arc Consistency algorithm. While sDC3 admits the same interesting worst-case complexities as PC8, sDC2 appears to be the most robust algorithm in practice. Indeed, compared to PC8 and the optimal PC2001, sDC2 is usually around one order of magnitude faster on large instances.
We introduce a propagator for abstract pairs of Sum constraints, where the expressions in the sums respect a form of convexity. this propagator is parametric and can be instantiated for various concrete pairs, includi...
详细信息
ISBN:
(纸本)9783642406263;9783642406270
We introduce a propagator for abstract pairs of Sum constraints, where the expressions in the sums respect a form of convexity. this propagator is parametric and can be instantiated for various concrete pairs, including Deviation, Spread, and the conjunction of Sum and Count. We show that despite its generality, our propagator is competitive in theory and practice with state-of-the-art propagators.
constraint models contain a number of common patterns. For example, many constraint models involve an array of decision variables with symmetric rows and/or columns. By documenting such constraint patterns, we can sha...
详细信息
ISBN:
(纸本)3540202021
constraint models contain a number of common patterns. For example, many constraint models involve an array of decision variables with symmetric rows and/or columns. By documenting such constraint patterns, we can share modelling expertise. constraint solvers can also be extended to exploit such patterns. For example, we can develop specialized methods like the global lexicographical ordering constraint for breaking such row and column symmetry.
暂无评论