Rigorous solution techniques for numerical constraint satisfaction problems

A constraint satisfaction problem (e.g., a system of equations and inequalities) consists of a finite set of constraints specifying which value combinations from given variable domains are admitted. It is called numerical if its variable domains are continuous. Such problems arise in many applications, but form a difficult problem class since they are NP-hard. Solving a constraint satisfaction problem is to find one or more value combinations satisfying all its constraints. Numerical computations on floating-point numbers in computers often suffer from rounding errors. The rigorous control of rounding errors during numerical computations is highly desired in many applications because it would benefit the quality and reliability of the decisions based on the solutions found by the computations. Various aspects of rigorous numerical computations in solving constraint satisfaction problems are addressed in this thesis: search, constraint propagation, combination of inclusion techniques, and post-processing. The solution of a constraint satisfaction problem is essentially performed by a search. In this thesis, we propose a new complete search technique (i.e., it can find all solutions within a predetermined tolerance) for numerical constraint satisfaction problems. This technique is general and can be used in place of branching steps in most branch-and-prune methods. Moreover, this new technique speeds up the most recent general search strategy (often by an order of magnitude) and provides a concise representation of solutions. To make a constraint satisfaction problem easier to solve, a major approach, called constraint propagation, in the constraint programming1 field is often used to reduce the variable domains (by discarding redundant value combinations from the domains). Basing on directed acyclic graphs, we propose a new constraint propagation technique and a method for coordinating constraint propagation and search. More importantly, we propose a novel generic scheme for combining multiple inclusion techniques2 in numerical constraint propagation. This scheme allows bringing into the constraint propagation framework the strengths of various techniques coming from different fields. To illustrate the flexibility and efficiency of the generic scheme, we base on this scheme and devise several specific combination strategies for rigorous numerical constraint propagation using interval constraint propagation, interval arithmetic, affine arithmetic, and linear programming. Our experiments show that the new propagation techniques outperform previously available methods by 1 to 4 orders of magnitude or more in speed. We also propose several post-processing techniques for the representation of continuums of solutions. Based on connectedness, they allow grouping each cluster of connected solution subsets into a larger subset, thus allowing getting additional grouping information. Potentially, these techniques enable interval-based solution techniques to be alternatives to bounding-volume techniques in applications such as collision detection and interactive graphics. __________________________________________________ 1 Constraint programming is an approach to programming that relies on both reasoning and computing. 2 An inclusion technique is to include a set of interest into enclosures. It is also called an enclosure technique.

Constraint consistency techniques for continuous domains

Jamila Sam

Constraint Satisfaction Problems (CSPs) are ubiquitous in computer science. Many problems, ranging from resource allocation and scheduling to fault diagnosis and design, involve constraint satisfaction as an essential component. A CSP is given by a set of variables and constraints on small subsets of these variables. It is solved by finding assignments of values to the variables such that all constraints are satisfied. In its most general form, a CSP is combinatorial and complex. In this thesis, we consider constraint satisfaction problems with variables in continuous, numerical domains. Contrary to most existing techniques, which focus on computing a single optimal solution, we address the problem of computing a compact representation of the space of all solutions that satisfy the constraints. This has the advantage that no optimization criterion has to be formulated beforehand, and that the space of possibilities can be explored systematically. In certain applications, such as diagnosis and design, these advantages are crucial. In consistency techniques, the solution space is represented by labels assigned to individual variables or combinations of variables. When the labeling is globally consistent, each label contains only those values or combinations of values which appear in at least one solution. This kind of labeling is a compact, sound and complete representation of the solution space, and can be combined with other reasoning methods. In practice, computing a globally consistent labeling is too complex. This is usually tackled in two ways. One way is to enforce consistencies locally, using propagation algorithms. This prunes the search space and hence reduces the subsequent search effort. The other way is to identify simplifying properties which guarantee that global consistency can be enforced tractably using local propagation algorithms. When constraints are represented by mathematical expressions, implementing local consistency algorithms is difficult because it requires tools for solving arbitrary systems of equations. In this thesis, we propose to approximate feasible solution regions by 2k-trees, thus providing a means of combining constraints logically rather than numerically. This representation, commonly used in computer vision and image processing, avoids using complex mathematical tools. We propose simple and stable algorithms for computing labels of arbitrary degrees of consistency using this representation. For binary constraints, it is known that simplifying convexity properties reduces the complexity of solving a CSP. These properties guarantee that local degrees of consistency are sufficient to ensure global consistency. We show how, in continuous domains, these results can be generalized to ternary and in fact arbitrary n-ary constraints. This leads to polynomial-time algorithms for computing globally consistent labels for a large class of constraint satisfaction problems with continuous variables. We describe and justify our representation of constraints and our consistency algorithms. We also give a complete analysis of the theoretical results we present. Finally, the developed techniques are illustrated using practical examples.

EPFL1995

On the generation of locally consistent solution spaces in mixed dynamic constraint problems

Esther Gelle

The development of industrial products such as cars, mechanical tools as well as civil engineering structures includes the task of identifying components and arranging them in a product structure. This task is commonly called configuration. It can be formalized as a constraint satisfaction problem (CSP), which provides a concise mathematical model for combinatorial tasks. A CSP is defined by the variables of interest, each with a domain of possible values, and a set of constraints which restrict the allowed value combinations. The formulation of a configuration task as a CSP gives flexibility required to apply complex optimization criteria during search which often cannot be expressed by a single utility function. Solving a CSP corresponds to finding a consistent assignment to the variables that satisfies all constraints. Solution methods for CSPs encompass consistency and search techniques. Consistency techniques are preprocessing methods which remove inconsistent value combinations before search thus reducing the search space; Furthermore, a dynamic CSP model (DCSP) makes possible the introduction of new variables and constraints during problem resolution. However, CSP techniques have been weak for handling mixed (discrete-continuous) as well as dynamic problems. In this thesis, I present a new algorithm for solving DCSPs with mixed, continuous and discrete, constraints. It isolates and approximates the solution sets of a DCSP by local consistency techniques. To this purpose, local consistency techniques for continuous constraints had to be enhanced and integrated with existing discrete local consistency methods. Some advantages of this algorithm are: It can solve problems in which the existence of a variable depends on a decision taken over a continuous value domain. Different locally consistent solution spaces can be compared, thus providing additional information for decision making. Local consistency techniques are also applied to search for a single solution within the resulting locally consistent solution spaces. These techniques are particularly efficient for searching in continuous domains. The algorithm proposed is applied to a number of different problems such as conceptual bridge design, design of steel structures, configuration of trains, and industrial mixers.

EPFL1998

Collaborative design using solution spaces

Claudio Lottaz

Complex design tasks from many domains such as mechanical, electrical and civil engineering make the collaboration of many partners unavoidable for several reasons: knowledge from various experts is necessary, often more than one enterprises are involved and deadlines impose concurrent engineering. However, collaboration also leads to certain in-conveniences such as information loss and misunderstandings during communication and iterative negotiation when suggested partial solutions for sub-tasks conflict. Moreover, major problems are related to management of changes and ensuring design consistency. This thesis conjectures that many of these problems are caused by the use of single solutions during negotiation. Currently, project partners assign single values for sub-tasks and then proceed, often after tedious negotiations with other partners, to integrate these partial solutions into solutions for the whole project. While partners determine one single solution for a sub-task, much information about potential alternatives is lost and premature decisions are taken. The integration of partial solutions then often leads to artificial conflicts which are not due. to incompatible design goals but arise because information about possible compromises is no longer available. Consequently, many changes usually occur during negotiation about parameter values and much, effort must be invested in. order to keep the design consistent. Therefore, we investigate the use of solution spaces instead of single solutions. When solution. spaces are used during negotiation, more information about alternatives is avail-able, premature decisions are avoided and thus, no artificial conflicts arise. Moreover, since project partners provide formal information about project requirements, real conflicts between diverging project goals can be detected. However, the implementation of a collaboration system using solution spaces is far from trivial, since in general the computation of exact solution spaces is intractable. We employ constraint satisfaction techniques in order to calculate solution space approximations. Constraints arise naturally in many fields of engineering and are therefore suited to formally express project requirements. Using constraints on design parameters, project partners can describe large families of acceptable solutions. Moreover, descriptions using constraints can be easily adapted to changes in the project's context. When project descriptions in terms of constraints are available, constraint satisfaction techniques such as consistency can be employed to provide computational support during collaboration. Consistency algorithms use local inconsistencies to prune regions from the original search space where no solution can be expected and thus provide approximations of solution spaces. Algorithms which ensure low degrees of consistency provide a rough over-estimation of the solution space but have low complexity, while algorithms which enforce high degrees of consistency provide a tight estimation of the solution space but suffer from high complexity. Since consistency algorithms provide over-estimations of solution spaces they are suited to find real conflicts between the various project requirements. In fact, using constraint satisfaction techniques in collaboration splits negotiation into two phases: negotiation of project requirements and negotiation about parameter values. During the negotiation of requirements, expressed as constraints, partners search for a feasible set of restrictions. Given such a set of restrictions, partners can negotiate about parameter values within the corresponding solution space approximation. During negotiation about parameter values some support for decision-making can be provided by analysing the shape of the solution space approximations. In order to illustrate the use of constraint satisfaction techniques in collaborative de-sign, a prototype of an Internet-based communication platform has been implemented, which focuses on the exchange of data related to constraints and solution spaces, including the visualisation of constraints and projections of solution space approximation. It provides access to several constraint satisfaction algorithms. Moreover, some standard techniques were extended as follows: A reformulation algorithm transforms algebraic constraint satisfaction problems (CSPs) into ternary form, i.e., such that they contain exclusively constraints involving at most three variables. Thereby, few auxiliary variables are introduced and certain intermediary variables are removed in order to provide a small CSP in ternary form. In addition, the use of interval arithmetic techniques to discretise continuous constraints is proposed. Moreover, variants of 2-consistency and 3-consistency for ternary CSPs have been developed and an improvement of (3,2)-relational consistency's space efficiency. Finally, a description of search heuristics for interactive use is described. The results of this research have been evaluated in the context of the construction industry. Construction projects are suitable test cases for collaboration systems, since they always imply complex interactions between several partners from various domains. With the help of practitioners, three realistic examples have been modelled. These projects demonstrate the usefulness of constraint satisfaction techniques during negotiation and collaboration within design projects. Constraint-based support leads to better management of changes and easier implementation of least commitment decision strategies. The results of this research may therefore improve the performance of collaboration systems currently in use.

EPFL2000