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.
the shift-scheduling problem was originally introduced by Edie in 1954 [8] in the context of scheduling highway toll booth operators. It was solved a short time later, by Georges Dantzig [6], using a set covering form...
ISBN:
(纸本)9783319104287;9783319104270
the shift-scheduling problem was originally introduced by Edie in 1954 [8] in the context of scheduling highway toll booth operators. It was solved a short time later, by Georges Dantzig [6], using a set covering formulation. However, the Multi-Activity Shift Scheduling (MASSP) version of that problem, where one not only needs to schedule when employees are working or resting, but more precisely, what activity they are performing, still remains a challenge. During this invited lecture, we will recall the turning points of this 60-year journey, focusing particularly on the efforts of the last decade to solve MASSPs.
In constraint Satisfaction, basic inferences rely oil some properties of constraint networks, called consistencies, that allow the identification of inconsistent instantiations (also called nogoods). Two main families...
详细信息
ISBN:
(纸本)9783642042430
In constraint Satisfaction, basic inferences rely oil some properties of constraint networks, called consistencies, that allow the identification of inconsistent instantiations (also called nogoods). Two main families of consistencies have been introduced so far: those that permit LIS to reason from variables Such as (i, j)-consistency and those that permit us to reason from constraints Such as relational (i, j)-consistency. this paper introduces a new family of consistencies based on the concept of flailed value (a value pruned during search). this family is orthogonal to previous ones.
this paper introduces SolverCheck, a property-based testing (PBT) library specifically designed to test cp solvers. In particular, SolverCheck provides a declarative language to express a propagator's expected beh...
详细信息
ISBN:
(纸本)9783030300487
this paper introduces SolverCheck, a property-based testing (PBT) library specifically designed to test cp solvers. In particular, SolverCheck provides a declarative language to express a propagator's expected behavior and test it automatically. that language is easily extended with new constraints and flexible enough to precisely describe a propagator's consistency. Experiments carried out using Choco [41], JaCoP [27] and Minicp [35] revealed the presence of numerous non-trivial bugs, no matter how carefully the test suites of these solvers have been engineered. Beyond the remarkable effectiveness of our technique to assess the correctness and robustness of a solver, our experiments also demonstrated the practical usability of SolverCheck to test actual cp-solvers.
this paper introduces propagator groups as an abstraction for controlling the execution of propagators as implementations of constraints. Propagator groups enable users of a constraintprogramming system to program ho...
详细信息
ISBN:
(纸本)9783642042430
this paper introduces propagator groups as an abstraction for controlling the execution of propagators as implementations of constraints. Propagator groups enable users of a constraintprogramming system to program how propagators within a group are executed. the paper exemplifies propagator groups for controlling both propagation order and propagator interaction. Controlling propagation order is applied to debugging constraint propagation and optimal constraint propagation for Berge-acyclic propagator graphs. Controlling propagator interaction by encapsulating failure and entailment is applied to general reification and constructive disjunction. the paper describes an implementation of propagator groups (based on Gecode) that is applicable to any propagator-centered constraintprogramming system. Experiments show that groups incur little to no overhead and that the applications of groups axe practically usable and efficient.
Many real world discrete optimization problems are expressible as nested problems where we solve one optimization or satisfaction problem as a subproblem of a larger meta problem. Nested problems include many importan...
详细信息
ISBN:
(纸本)9783319104287;9783319104270
Many real world discrete optimization problems are expressible as nested problems where we solve one optimization or satisfaction problem as a subproblem of a larger meta problem. Nested problems include many important problem classes such as: stochastic constraint satisfaction/optimization, quantified constraint satisfaction/optimization and minimax problems. In this paper we define a new class of problems called nested constraint programs (Ncp) which include the previously mentioned problem classes as special cases, and describe a search-based cp solver for solving Ncp's. We briefly discuss how nogood learning can be used to significantly speedup such an Ncp solver. We show that the new solver can be significantly faster than existing solvers for the special cases of stochastic/quantified CSP/COP's, and that it can solve new types of problems which cannot be solved with existing solvers.
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.
We introduce a new method for solving systems of linear inequalities over the rationals-the conflict resolution method. the method successively refines an initial assignment withthe help of newly derived constraints ...
详细信息
ISBN:
(纸本)9783642042430
We introduce a new method for solving systems of linear inequalities over the rationals-the conflict resolution method. the method successively refines an initial assignment withthe help of newly derived constraints until either the assignment becomes a solution of the system or a trivially unsatisfiable constraint is derived. We show that this method is correct and terminating. Our experimental results show that conflict resolution outperforms the Fourier-Motzkin method and the Chernikov algorithm, in some cases by orders of magnitude.
In this paper we consider the consistency problem for qualitative constraint networks representing temporal or spatial information. the most efficient method for solving this problem consists in a search algorithm usi...
详细信息
ISBN:
(纸本)9783540749691
In this paper we consider the consistency problem for qualitative constraint networks representing temporal or spatial information. the most efficient method for solving this problem consists in a search algorithm using, on the one hand, the weak composition closure method as a local propagation method, and on the other hand, a decomposition of the constraints into subrelations of a tractable set. We extend this algorithm withthe notion of eligibility and the notion of frozen constraints. the first concept allows to characterise constraints which will not be considered during the search. the second one allows to freeze constraints in order to avoid unnecessary updates.
this paper presents the first;experimental evaluation of the length-lex domain for set variables. the implementation is based on bound-consistency algorithms proposed in earlier work and two novel technical contributi...
详细信息
ISBN:
(纸本)9783642042430
this paper presents the first;experimental evaluation of the length-lex domain for set variables. the implementation is based on bound-consistency algorithms proposed in earlier work and two novel technical contributions: a generic filtering algorithm which automatically pushes ordering constraints into symmetric binary constraints with only a logarithmic overhead and an adaptation of symmetry-breaking constraints from 0/1 matrices to the length-lex ordering. the experimental results indicate that the length-lex representation for set variables is very effective and robust on traditional set-CSPs benchmarks.
暂无评论