Keywords: Constraint satisfaction problems (CSPs), numerical constraints, convex approximations, distributed CSPs Contact Person: Marius C. Silaghi Phone: (+41 21) 693-5209 E-mail: Marius.Silaghi@epfl.ch
Many industrial problems can be modelled as constraint satisfaction problems (CSPs). A CSP consists of variables that may take on values from domains, and of constraints which restrict the possible value combinations between variables. A solution is a set of assignments of values to variables so that all the constraints of the problem are satisfied. Most engineering applications involve numerical variables with continuous domains defined over the reals. Constraints that bear on numerical variables are equations and inequations usually expressed using arithmetic expressions. The practical application fields involving continuous constraints are numerous and range from design in mechanical and building industries to financial or chemical engineering problems.
The existing techniques for solving problems with general continuous constraints, such as quasi-Newton, conjugate gradient or sequential quadratic programming techniques are incomplete. This means that they cannot reliably enumerate all solutions of a problem, nor are they guaranteed to converge. In practice, incompleteness of solving procedures means that important decision can be taken on the basis of incorrect information and that possible better alternatives can be missed. Moreover, most existing solvers directly work with the arithmetic expressions given as input. As a result they are highly dependent on the form of input expressions which does not necessarily reflect the real complexity of the problem. In effect, complex input expressions can perfectly to express very simple problems.
The general objective of the research undertaken in this project is primarily to devise new techniques for continuous CSPs that: a) are complete and able to compactly describe the entire set of solutions, b) handle search space representations which are more closely related to the true complexity of the problem.
The technique implemented reformulates numerical CSPs into disjunctions of convex approximations and explores the reformulation by systematic search. We are particularly interested in numerical problems involved in areas such as design or diagnosis. These problems are often under-constrained with many inequalities and do not lend themselves easily to optimisation techniques. These features pose challenging problems for both deriving and representing the set of solutions. The second objective is to investigate the transference and extension of the current results, to distributed CSPs.