Catálogo de publicaciones - libros

Compartir en
redes sociales


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

Información sobre derechos de publicación

© Springer-Verlag Berlin Heidelberg 2006

Tabla de contenidos

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

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

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

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

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

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

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

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

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

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