Constraint Programming

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.

Technical

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.

Applications

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).

Scheduling: Many of the original applications developed by the CHIP team at ECRC were scheduling related. This remains one of the strongest application areas, and the incorporation of powerful OR techniques in CHIP and Ilog Scheduler has taken the field far beyond the early simple CSP approaches [Duncan 90]. Constraints have been used in a wide variety of scheduling applications, including vehicle scheduling [Duncan 95], workforce scheduling [Kusumoto 96], container port planning [Parrett 91], and frequency assignment problems [Carlsson 93].
Configuration: Configuration involves selecting and arranging parts to achieve particular goals while respecting particular constraints. Examples of configuration problems include design, manufacturing, and sales (e.g. Digital's R1/XCON expert system for configuring computer systems). See the configuration problems website for further examples.
Natural language: Current linguistics theories often describe syntactic relations as constraints on linguistic structures. See [Blanche 92].
Graphics: Constraints are sometimes used to describe properties of graphical systems, for example in the Amulet toolkit.

Suitability

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.

Tools

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 Solver/Scheduler: The Ilog optimization suite consists of three C++ libraries:
1. Ilog Solver is a basic CSP solver
2. Ilog Scheduler is built on top of Solver. It facilitates modelling activities and various resource types, and provides sophisticated algorithms to enforce capacity constraints
3. Ilog Planner uses a Simplex-like solver to facilitate production planning.
Ilog offer a free demo CD on request, see their website.
CHIP v5: Developed by the original Chip team. Prolog version or C library, C++ version available soon. No website, contact: COSYTEC, Parc Club Orsay Universit\'{e}, 4 rue Jean--Rostand, 91893 Orsay Cedex, France, Tel: +33-1-60-19-37-38, Fax: +33-1-60-19-36-20, or email.
IF/Prolog: Developed from Siemens SNI-Prolog, hence another from the CHIP family.
Prolog IV: Constraint solvers for rationals, lists, and intervals. Unlike Prolog III which used the non-standard Marseille dialect of Prolog, Prolog IV is ISO compliant.

Websites

AIAI: A Review of Commercial Constraint-based Programming Tools (with sets of examples).
List of constraint links.
CIRL Constraints Archive. Contains the FAQ for the comp.constraints newsgroup, notes on constraint related topics, and various links.
CCC -- Constraints FTP Archive. Contains bibliographies, papers, code for standard CSP algorithms, and a directory of people interested in constraints.
Ilog website also mirrored in USA (look for ``ILOG Optimization Suite'' under ``Products''). Contains descriptions of their products, application success stories, and proceedings of a users' conference.

References

[Tsang 93]. Edward Tsang. Foundations of Constraint Satisfaction. Academic Press, 1993. Edward Tsang's book provides the best coverage of CSP algorithms, and includes descriptions in pseudo-code and first-order predicate calculus. The book is unfortunately out of print, but is available from the author.
[Fron 94]. Annick Fron. Programmation par Contraintes. Editions Addison-Wesley France, 1994. Annick Fron's book provides a much gentler introduction to programming with constraints (in French). Jean-Yves Cras gives an overview of several constraint solving tools, including several non-commercial systems.
[Blache 92]. Philippe Blache. Using Active Constraints to Parse GPSGs. Proceedings of COLING'92, 1992.
[Carlsson & Grindal 93]. Mats Carlsson and Mats Grindal. Automatic frequency assignment for cellular telephones using constraint satisfaction techniques. In ICLP'93: Proceedings 10th International Conference on Logic Programming, Budapest, June 1993.
[Cras 93]. Jean-Yves Cras. A Review of Industrial Constraint Solving Tools. AI Intelligence, PO Box 95, Oxford OX2 7XL, Tel: 01865 59872, Fax: 01865 310760, 1993. ISBN: 1-898804-00-1.
[Duncan 90] Tim Duncan. Scheduling Problems and Constraint Logic Programming: A Simple Example and its Solution. Technical Report AIAI-TR-120, Artificial Intelligence Applications Institute, University of Edinburgh, 1990.
[Duncan 95]. Tim Duncan. Schedule-IT: An Intelligent Vehicle Scheduling System. In Proceedings of the First Ilog Solver and Ilog Schedule International Users' Meeting, Abbaye des Vaux de Cernay, France, July 10-11 1995. Also available as AIAI-TR-180.
[Hyvonen 92]. Eero Hyvonen. Constraint Reasoning Based on Interval Arithmetic. The Tolerance Propagation Approach. Artificial Intelligence, 58(1-3):71--112, December 1992.
[Kusumoto 96]. Sachio Kusumoto. Nurse Scheduling System Using Ilog Solver. In Proceedings of Ilog Solver and Ilog Schedule Second International Users' Conference, Paris, July 1996.
[Lassez 87]. Catherine Lassez, Ken McAloon, and Roland Yap. Constraint Logic Programming and Options Trading. IEEE Expert, Special Issue on Financial Software, 2(3):42--50, August 1987.
[Parrett 91]. M. Parrett. Using constraint logic programming techniques in container port planning. ICL Technical Journal, 7(3):537--545, May 1991.
[Van Hentenryck 88]. Pascal Van Hentenryck and J-P. Carillon. Generality versus Specificity: An Experience with AI and OR Techniques. In AAAI-88: Proceedings National Conference on Artificial Intelligence, pages 660--664, St. Paul, Minnesota, August 1988.

Last updated 4th June 1997
by Ian Harrison