|Introduction | Technical | Applications | Suitability | Tools | Websites | References|
Constraint programming is a rapidly maturing technology, and several commercial tools are available. The techniques are applicable to a wide range of scheduling and resource allocation problems, and there are already a number of successfully fielded applications.
The field has developed out of Constraint Logic Programming (CLP), which sought to extend Prolog with constraint solvers. There are two main types of system: those based on the Simplex algorithm; and those based on Constraint Satisfaction Problem (CSP) techniques. Much of the original work was done by a research team at the European Computer-Industry Research Centre (ECRC) in Munich. Their research system, CHIP, was developed into commercial products by ECRC's shareholder companies: ICL, Siemens, and Bull. The team later left to set up their own company, Cosytec, and continue to develop CHIP. Ilog Solver/Scheduler were developed separately by Ilog, a spin-off company from INRIA, the French National Research Institute for AI.
The rational solvers in CHIP-derived systems, Ilog Planner, and Prolog IV are based on an incremental form of the Simplex algorithm with Gaussian elimination, and are used to check the consistency of a set of constraints over rational numbers.
CHIP and some of its derived systems also contain a boolean constraint solver. This was primarily of interest to Siemens; Siemens has used this for circuit verification applications. Prolog IV contains a solver for constraints on lists (intended for natural language processing), and one for internal arithmetic [Hyvonen 92].
However, the work that has attracted the most attention relates to the integration of CSP solving algorithms into these tools. The CSP paradigm consists of a set of variables, each of which have a discrete and finite set of possible values (their domain); and a set of constraints between the variables which specify which combinations of values are allowed and which are not. For this reason, this type of system is sometimes referred to as a finite domain constraint solver. Variables may have integer or symbolic domains. A solution to a CSP is a set of variable-value assignments which satisfies all the constraints. The basic mechanism underlying these tools interleaves network consistency checking algorithms [Tsang 93], constraint propagation, and backtracking search. In essence, the algorithms increase the efficiency of the search by looking ahead, and actively using the constraints to prune the search space, thus minimizing backtracking.
Optimization is based on a form of branch and bound. That is, as soon as a solution is found, a further constraint is added to the effect that the value of the optimizing criterion must be less than the value just found. This causes the system to backtrack until a better solution is found. When no further solutions can be found the optimum value is known.
As the commercial tools have matured, the tool developers have integrated various sophisticated operations research~(OR) algorithms which allow their constraint solvers to make more powerful inferences, and thus find solutions more efficiently.
The published applications for CSP type systems have typically been scheduling related, while Simplex-based systems have mostly been used for financial [Lassez 87] or engineering applications. However, it is also possible to apply constraints to a wide variety of other areas (e.g. natural language, graphics).
Constraint-based systems are generally quite expressive and are thus good for modelling complex problems. Other techniques such as Genetic Algorithms (GAs) usually require more massaging to get the problem to fit. As a result constraint-based systems are usually easier to modify and maintain. Van Hentenryck compares constraints with some other techniques. Optimisation in these tools is based on a modified branch-and-bound, i.e. complete search. Although the use of constraints makes search more efficient, combinatorial explosion is still a problem. To appreciate this, consider the search space for a job-shop scheduling problem: where there are n jobs on m machines, (n!) to the power m solutions must be considered. For a n=4, m=4 problem this means 331,776 solutions, but add one more job (i.e. n=5) and this rises to 210,000,000. If the main characteristic of the problem is optimisation, rather than its constraints, then a stochastic technique (e.g. GAs) may be better.
One thing that constraint-based systems may handle better than GAs is soft constraints or preferences. In a GA these would simply be part of the evaluation function, but in a constraint system one at least has the possibility of directly modelling preferences as soft constraints, and of controlling which ones are relaxed.
The main contenders are Ilog Solver and CHIP. Ilog has a larger market share, probably because Cosytec were slow to offer CHIP as a \CPP/ library. ICL offer their CHIP-derived system, DecisionPower, to customers only as part of a consultancy package. IF/Prolog is also derived from CHIP, and both offer boolean, rational, and finite domain (i.e. CSP) solvers. Both CHIP v5 and Ilog benefit from the addition of various sophisticated OR algorithms which allow powerful new symbolic constraints to be offered.
Ilog offer a free demo CD on request, see their website.
About AIAI |
Last updated 4th June 1997
by Ian Harrison