Catálogo de publicaciones - libros
Principle and Practice of Constraint Programming: CP 2006: 12th International Conference, CP 2006, Nantes, France, September 25-29, 2006, Proceedings
Frédéric Benhamou (eds.)
En conferencia: 12º International Conference on Principles and Practice of Constraint Programming (CP) . Nantes, France . September 25, 2006 - September 29, 2006
Resumen/Descripción – provisto por la editorial
No disponible.
Palabras clave – provistas por la editorial
No disponibles.
Disponibilidad
Institución detectada | Año de publicación | Navegá | Descargá | Solicitá |
---|---|---|---|---|
No detectada | 2006 | SpringerLink |
Información
Tipo de recurso:
libros
ISBN impreso
978-3-540-46267-5
ISBN electrónico
978-3-540-46268-2
Editor responsable
Springer Nature
País de edición
Reino Unido
Fecha de publicación
2006
Información sobre derechos de publicación
© Springer-Verlag Berlin Heidelberg 2006
Tabla de contenidos
doi: 10.1007/11889205_41
Generating Propagators for Finite Set Constraints
Guido Tack; Christian Schulte; Gert Smolka
Ideally, programming propagators as implementations of constraints should be an entirely declarative specification process for a large class of constraints: a high-level declarative specification is automatically translated into an efficient propagator. This paper introduces the use of existential monadic second-order logic as declarative specification language for finite set propagators. The approach taken in the paper is to automatically derive projection propagators (involving a single variable only) implementing constraints described by formulas. By this, the paper transfers the ideas of indexicals to finite set constraints while considerably increasing the level of abstraction available with indexicals. The paper proves soundness and completeness of the derived propagators and presents a run-time analysis, including techniques for efficiently executing projectors for n -ary constraints.
Palabras clave: Boolean Function; Constraint Satisfaction Problem; Conjunctive Normal Form; Binary Decision Diagram; Generate Propagator.
- Regular Papers | Pp. 575-589
doi: 10.1007/11889205_42
Compiling Finite Linear CSP into SAT
Naoyuki Tamura; Akiko Taga; Satoshi Kitagawa; Mutsunori Banbara
In this paper, we propose a method to encode Constraint Satisfaction Problems (CSP) and Constraint Optimization Problems (COP) with integer linear constraints into Boolean Satisfiability Testing Problems (SAT) . The encoding method is basically the same with the one used to encode Job-Shop Scheduling Problems by Crawford and Baker. Comparison x ≤ a is encoded by a different Boolean variable for each integer variable x and integer value a . To evaluate the effectiveness of this approach, we applied the method to Open-Shop Scheduling Problems (OSS) . All 192 instances in three OSS benchmark sets are examined, and our program found and proved the optimal results for all instances including three previously undecided problems.
- Regular Papers | Pp. 590-603
doi: 10.1007/11889205_43
Differentiable Invariants
Pascal Van Hentenryck; Laurent Michel
Invariants that incrementally maintain the value of expressions under assignments to their variables are a natural abstraction to build high-level local search algorithms. But their functionalities are not sufficient to allow arbitrary expressions as constraints or objective functions as in constraint programming. Differentiable invariants bridge this expressiveness gap. A differentiable invariant maintains the value of an expression and its variable gradients, it supports differentiation to evaluate the effect of local moves. The benefits of differentiable invariants are illustrated on a number of applications which feature complex, possibly reified, expressions and whose models are essentially similar to their CP counterparts. Experimental results demonstrate their practicability.
Palabras clave: Objective Function; Local Search; Local Move; Constraint Programming; Local Search Algorithm.
- Regular Papers | Pp. 604-619
doi: 10.1007/11889205_44
Revisiting the Sequence Constraint
Willem-Jan van Hoeve; Gilles Pesant; Louis-Martin Rousseau; Ashish Sabharwal
Many 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 width. To date, none of the filtering algorithms proposed guaranteed domain consistency. In this paper, we present three filtering algorithms for the sequence constraint, with 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. Our customized algorithm does so in polynomial time, and can even be applied to a generalized sequence constraint for subsequences of variable widths. Experimental results show the practical usefulness of each.
Palabras clave: Cardinality Constraint; Local Graph; Sequence Constraint; Knapsack Constraint; Goal Vertex.
- Regular Papers | Pp. 620-634
doi: 10.1007/11889205_45
BlockSolve: A Bottom-Up Approach for Solving Quantified CSPs
Guillaume Verger; Christian Bessiere
Thanks to its extended expressiveness, the quantified constraint satisfaction problem (QCSP) can be used to model problems that are difficult to express in the standard CSP formalism. This is only recently that the constraint community got interested in QCSP and proposed algorithms to solve it. In this paper we propose BlockSolve , an algorithm for solving QCSPs that factorizes computations made in branches of the search tree. Instead of following the order of the variables in the quantification sequence, our technique searches for combinations of values for existential variables at the bottom of the tree that will work for (several) values of universal variables earlier in the sequence. An experimental study shows the good performance of BlockSolve compared to a state of the art QCSP solver.
- Regular Papers | Pp. 635-649
doi: 10.1007/11889205_46
General Symmetry Breaking Constraints
Toby Walsh
We describe some new propagators for breaking symmetries in constraint satisfaction problems. We also introduce symmetry breaking constraints to deal with symmetries acting simultaneously on variables and values, conditional symmetries, as well as symmeties acting on set and other types of variables.
Palabras clave: Symmetry Breaking; Constraint Programming; Constraint Satisfaction Problem; General Symmetry; Variable Symmetry.
- Regular Papers | Pp. 650-664
doi: 10.1007/11889205_47
Inferring Variable Conflicts for Local Search
Magnus Ågren; Pierre Flener; Justin Pearson
For efficiency reasons, neighbourhoods in local search are often shrunk by only considering moves modifying variables that actually contribute to the overall penalty. These are known as conflicting variables. We propose a new definition for measuring the conflict of a variable in a model and apply it to the set variables of models expressed in existential second-order logic extended with counting (∃ SOL^ + ). Such a variable conflict can be automatically and incrementally evaluated. Furthermore, this measure is lower-bounded by an intuitive conflict measure, and upper-bounded by the penalty of the model. We also demonstrate the usefulness of the approach by replacing a built-in global constraint by an ∃ SOL^ + version thereof, while still obtaining competitive results.
- Poster Papers | Pp. 665-669
doi: 10.1007/11889205_48
Reasoning by Dominance in Not-Equals Binary Constraint Networks
Belaïd Benhamou; Mohamed Réda Saïdi
In this paper, we extend the principle of symmetry to dominance in Not-Equals Constraint Networks and show how dominated values are detected and eliminated efficiently at each node of the search tree.
Palabras clave: Search Tree; Constraint Satisfaction Problem; Graph Coloring; Constraint Network; Graph Coloring Problem.
- Poster Papers | Pp. 670-674
doi: 10.1007/11889205_49
Distributed Stable Matching Problems with Ties and Incomplete Lists
Ismel Brito; Pedro Meseguer
We consider the Stable Marriage Problem and the Stable Roommates Problem in presence of ties and incomplete preference lists. They can be solved by centralized algorithms, but this requires to make public preference lists, something that members would prefer to avoid for privacy reasons. This motivates a distributed formulation to keep privacy. We propose a distributed constraint approach that solves all the considered problems, keeping privacy.
- Poster Papers | Pp. 675-679
doi: 10.1007/11889205_50
Soft Arc Consistency Applied to Optimal Planning
Martin Cooper; Sylvain Cussat-Blanc; Marie de Roquemaurel; Pierre Régnier
We show in this article how the Weighted CSP framework can be used to solve an optimisation version of numerical planning. The WCSP finds an optimal plan in the planning graph containing all solution plans of minimum length. Experimental trials were performed to study the impact of soft arc consistency techniques (FDAC and EDAC) on the efficiency of the search for an optimal plan in this graph. We conclude by giving a possible theoretical explanation for the fact that we were able to solve optimisation problems involving several hundred variables.
- Poster Papers | Pp. 680-684