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

Global Optimization of Probabilistically Constrained Linear Programs

Shabbir Ahmed

Various applications in reliability and risk management give rise to optimization problems where certain constraints involve stochastic parameters and are required to be satisfied with a pre-specified probability threshold. In this talk we address such probabilistically constrained linear programs involving stochastic right-hand-sides. These problems involve non-convex feasible sets, and are extremely difficult to optimize.

Palabras clave: Global Optimization; Convex Hull; Mixed Integer Linear Program; Global Optimal Solution; Valid Inequality.

- Invited Papers | Pp. 1-1

Algorithms and Constraint Programming

Fabrizio Grandoni; Giuseppe F. Italiano

Constraint Programming is a powerful programming paradigm with a great impact on a number of important areas such as logic programming[45], concurrent programming[42], artificial intelligence[12], and combinatorial optimization[46]. We believe that constraint programming is also a rich source of many challenging algorithmic problems, and cooperations between the constraint programming and the algorithms communities could be beneficial to both areas.

Palabras clave: Steiner Tree; Exact Algorithm; Constraint Satisfaction Problem; Binary Constraint; Constraint Satisfaction Problem Instance.

- Invited Papers | Pp. 2-14

Interval Analysis and Robotics

Jean-Pierre Merlet

Robotics is a field in which numerous linear and non linear problems are occuring. The unknowns of these problems have a physical meaning and roboticians are usually interested only in solutions within restricted bounds. Furthermore dealing with uncertainties is unavoidable as any robot is a controlled mechanical system with manufacturing and control errors. Hence interval analysis is a tool of choice for solving many problems in robotics and managing uncertainties while providing certified answers (the reliability of the result is very often a critical aspect, for example in medical robotics). In this talk we will exemplify how interval anlysis may be used to efficently solve systems of equations appearing in the geometrical modeling of robots, to check the regularity of parametrized interval matrices that is required for singularity analysis and to design robots so that their performances will meet pre-defined requirements whatever are the manufacturing errors of the real robot within reasonable ranges.

- Invited Papers | Pp. 15-15

Constraint Based Resilience Analysis

Helmut Simonis

In this paper we give an overview of applications of Constraint Programming for IP (Internet Protocol) data networks, and discuss the problem of Resilience Analysis in more detail. In this problem we try to predict the loading of a network in different failure scenarios, without knowing end-to-end flow values throughout the network; the inference is based only on observed link traffic values. The related problem of Traffic Flow Analysis aims to derive a traffic matrix from the observed link traffic data. This is a severely under-constrained problem, we can show that the obtained flow values vary widely in different, feasible solutions. Experimental results indicate that using the same data much more accurate, bounded results can be obtained for Resilience Analysis .

Palabras clave: Constraint Programming; Network Design Problem; Warehouse Location; Secondary Path; Link Load.

- Invited Papers | Pp. 16-28

Infinite Qualitative Simulations by Means of Constraint Programming

Krzysztof R. Apt; Sebastian Brand

We introduce a constraint-based framework for studying infinite qualitative simulations concerned with contingencies such as time, space, shape, size, abstracted into a finite set of qualitative relations. To define the simulations we combine constraints that formalize the background knowledge concerned with qualitative reasoning with appropriate inter-state constraints that are formulated using linear temporal logic. We implemented this approach in a constraint programming system (ECL^ i PS^ e ) by drawing on the ideas from bounded model checking. The implementation became realistic only after several rounds of optimizations and experimentation with various heuristics. The resulting system allows us to test and modify the problem specifications in a straightforward way and to combine various knowledge aspects. To demonstrate the expressiveness and simplicity of this approach we discuss in detail two examples: a navigation problem and a simulation of juggling.

Palabras clave: Temporal Logic; Constraint Program; Constraint Satisfaction Problem; Integrity Constraint; Linear Temporal Logic.

- Regular Papers | Pp. 29-43

Algorithms for Stochastic CSPs

Thanasis Balafoutis; Kostas Stergiou

The Stochastic CSP (SCSP) is a framework recently introduced by Walsh to capture combinatorial decision problems that involve uncertainty and probabilities. The SCSP extends the classical CSP by including both decision variables, that an agent can set, and stochastic variables that follow a probability distribution and can model uncertain events beyond the agent’s control. So far, two approaches to solving SCSPs have been proposed; backtracking-based procedures that extend standard methods from CSPs, and scenario-based methods that solve SCSPs by reducing them to a sequence of CSPs. In this paper we further investigate the former approach. We first identify and correct a flaw in the forward checking (FC) procedure proposed by Walsh. We also extend FC to better take advantage of probabilities and thus achieve stronger pruning. Then we define arc consistency for SCSPs and introduce an arc consistency algorithm that can handle constraints of any arity.

Palabras clave: Decision Variable; Stochastic Variable; Current Variable; Recursive Call; Chance Constraint.

- Regular Papers | Pp. 44-58

Graph Properties Based Filtering

Nicolas Beldiceanu; Mats Carlsson; Sophie Demassey; Thierry Petit

This article presents a generic filtering scheme, based on the graph description of global constraints. This description is defined by a network of binary constraints and a list of elementary graph properties: each solution of the global constraint corresponds to a subgraph of the initial network, retaining only the satisfied binary constraints, and which fulfills all the graph properties. The graph-based filtering identifies the arcs of the network that belong or not to the solution subgraphs. The objective is to build, besides a catalog of global constraints, also a list of systematic filtering rules based on a limited set of graph properties. We illustrate this principle on some common graph properties and provide computational experiments of the effective filtering on the group constraint.

Palabras clave: Constraint Programming; Global Constraint; Maximum Match; Graph Property; Graph Class.

- Regular Papers | Pp. 59-74

The ROOTS Constraint

Christian Bessiere; Emmanuel Hebrard; Brahim Hnich; Zeynep Kiziltan; Toby Walsh

A wide range of counting and occurrence constraints can be specified with just two global primitives: the Range constraint, which computes the range of values used by a sequence of variables, and the Roots constraint, which computes the variables mapping onto a set of values. We focus here on the Roots constraint. We show that propagating the Roots constraint completely is intractable. We therefore propose a decomposition which can be used to propagate the constraint in linear time. Interestingly, for all uses of the Roots constraint we have met, this decomposition does not destroy the global nature of the constraint as we still prune all possible values. In addition, even when the Roots constraint is intractable to propagate completely, we can enforce bound consistency in linear time simply by enforcing bound consistency on the decomposition. Finally, we show that specifying counting and occurrence constraints using Roots is effective and efficient in practice on two benchmark problems from CSPLib.

Palabras clave: Linear Time; Integer Variable; Global Constraint; Global Nature; Range Constraint.

- Regular Papers | Pp. 75-90

CoJava: Optimization Modeling by Nondeterministic Simulation

Alexander Brodsky; Hadon Nash

We have proposed and implemented the language CoJava, which offers both the advantages of simulation-like process modeling in Java, and the capabilities of true decision optimization. By design, the syntax of CoJava is identical to the programming language Java, extended with special constructs to (1) make a nondeterministic choice of a numeric value, (2) assert a constraint, and (3) designate a program variable as the objective to be optimized. A sequence of specific selections in nondeterministic choice statements corresponds to an execution path . We define an optimal execution path as one that (1) satisfies the range conditions in the choice statements, (2) satisfies the assert-constraint statements, and (3) produces the optimal value in a designated program variable, among all execution paths that satisfy (1) and (2). The semantics of a CoJava program amounts to first finding an optimal execution path, and then procedurally executing it. To find an optimal execution path, the implemented CoJava compiler reduces the problem to a standard optimization formulation, and then solves it on an external solver. Then, the CoJava program is run as a Java program, where the choice statements select the found optimal values, and the assert and optimization statements are ignored. We illustrate the usage and semantics of CoJava using a simple supply-chain example, in which elastic demand, a manufacturer and a supplier are modeled as Java classes.

Palabras clave: Constraint Programming; Java Program; Choice Statement; Program Variable; Execution Path.

- Regular Papers | Pp. 91-106

An Algebraic Characterisation of Complexity for Valued Constraint

David A. Cohen; Martin C. Cooper; Peter G. Jeavons

Classical constraint satisfaction is concerned with the feasibility of satisfying a collection of constraints. The extension of this framework to include optimisation is now also being investigated and a theory of so-called soft constraints is being developed. In this extended framework, tuples of values allowed by constraints are given desirability weightings, or costs, and the goal is to find the most desirable (or least cost) assignment. The complexity of any optimisation problem depends critically on the type of function which has to be minimized. For soft constraint problems this function is a sum of cost functions chosen from some fixed set of available cost functions, known as a valued constraint language. We show in this paper that when the costs are rational numbers or infinite the complexity of a soft constraint problem is determined by certain algebraic properties of the valued constraint language, which we call feasibility polymorphisms and fractional polymorphisms. As an immediate application of these results, we show that the existence of a non-trivial fractional polymorphism is a necessary condition for the tractability of a valued constraint language with rational or infinite costs over any finite domain (assuming P ≠ NP).

Palabras clave: Cost Function; Constraint Satisfaction Problem; Algebraic Property; Soft Constraint; Submodular Function.

- Regular Papers | Pp. 107-121