Content area
Arising from research in the computer science community, constraint programming is a fairly new technique for solving optimization problems. For those familiar with mathematical programming, a number of language barriers make it difficult to understand the concepts of constraint programming. In this short tutorial, an explanation is given of how it relates to familiar mathematical programming concepts and how constraint programming and mathematical programming technologies are complimentary. A minimal background in linear and integer programming is assumed.
Full text
Arising from research in the computer science community, constraint programming is a fairly new technique for solving optimization problems. For those familiar with mathematical programming, a number of language barriers make it difficult to understand the concepts of constraint programming. In this short tutorial on constraint programming, we explain how it relates to familiar mathematical programming concepts and how constraint programming and mathematical programming technologies are complementary. We assume a minimal back-- ground in linear and integer programming.
George Dantzig [1963] invented the simplex method for linear programming in 1947 and first described it in a paper entitled "Programming in a linear structure" [Dantzig 1948, 1949]. Fifty years later, linear programming is now a strategic technique used by thousands of businesses trying to optimize their global operations. In the mid-1980s, researchers developed constraint programming as a computer science technique by combining developments in the artificial intelligence community with the development of new computer programming languages. Fifteen years later, constraint programming is now being seen as an important technique that complements traditional mathematical programming technologies as businesses continue to look for ways to optimize their business operations.
Developed independently as a technique within the computer science literature, constraint programming is now getting attention from the operations research community as a new and sometimes better way of solving certain kinds of optimization problems. We provide an introduction to constraint programming for those familiar with traditional mathematical programming.
The Word Programming
For those familiar with mathematical programming, one of the confusions with regard to understanding constraint programming is the fact that the names of both areas share the word programming. In fact, the two disciplines use this word differently.
The field of mathematical programming arose from its roots in linear programming. In his seminal textbook, Dantzig [1963, p. 1-21 introduces linear programming by describing a few different planning problems:
Nevertheless, it is possible to abstract the underlying essential similarities in the management of these seemingly disparate systems. To do this entails a look at the structure and state of the system, and at the objective to be fulfilled, in order to construct a statement of the actions to be performed, their timing, and their quantity (called a "program" or "schedule"), which will permit the system to move from a given status toward the defined objective.
The problems that Dantzig studied while developing the simplex algorithm were "programming problems," because the United States Defense Department in the post-World War II era was supporting research to devise programs of activities for future conflicts. T. C. Koopmans suggested that Dantzig use the term linear programming as opposed to programming in a linear structure, and Al Tucker then suggested that Dantzig call the linear programming problem a linear program [Dantzig and Thapa 1997]. Therefore, the term program, previously used to describe a plan of activities, became associated with a specific mathematical problem in the operations research literature.
Constraint programming is often called constraint logic programming, and it originates in the artificial intelligence literature in the computer science community. Here, the word programming refers to computer programming. Knuth [1968, p. 51 defines a computer program as "an expression of a computational method in a computer language." A computer program can be viewed as a plan of action for the operations of a computer, and hence the common concept of a plan is shared with the planning problems studied in the development of the simplex method. Constraint programming is a computer programming technique, with a name that is in the spirit of other programming techniques, such as object-oriented programming, functional programming, and structured programming. Logic programming is a declarative, relational style of programming based on first-order logic, where simple resolution algorithms are used to resolve the logical statements of a problem. Constraint logic programming extends this concept by using more powerful algorithms to resolve these statements. Van Hentenryck [1999, p. 41 writes:
The essence of constraint programming is a two-level architecture integrating a constraint and a programming component. The constraint component provides the basic operations of the architecture and consists of a system reasoning about fundamental properties of constraint systems such as satisfiability and entailment. The constraint component is often called the constraint store, by analogy to the memory store of traditional programming languages.... Operating around the constraint store is a programming-language component that specifies how to combine the basic operations, often in non-deterministic ways.
Hence, a constraint program is not a statement of a problem as in mathematical programming, but is rather a computer program that indicates a method for solving a particular problem. It is important to emphasize the two-level architecture of a constraint programming system. Because it is first and foremost a computer programming system, the system contains representations of programming variables, which are representations of memory cells in a computer that can be manipulated within the system. The first level of the constraint programming architecture allows users to state constraints over these programming variables. The second level of this architecture allows users to write a computer program that indicates how the variables should be modified so as to find values of the variables that satisfy the constraints.
The roots of constraint programming can be traced back to the work on constraint satisfaction problems in the 1970s, with arc-consistency techniques [Mackworth 1977] on the one hand and the language ALICE [Lauriere 1978] that was designed for stating and solving combinatorial problems on the other hand. In the 1980s, work in the logic programming community showed that the Prolog language could be extended by replacing the fundamental logic programming algorithms with more powerful constraint solving algorithms. For instance, in 1980, Prolog II used a constraint solver to solve equations and disequations on terms. This idea was further generalized in the constraint logic programming scheme and implemented in several languages [Colmerauer 1990; Jaffar and Lassez 1987; Van Hentenryck 1989; and Wallace et al. 1997]. Van Hentenryck [1989] used the arcconsistency techniques developed in the constraint satisfaction problem framework as the algorithm for the basic constraint solving. This concept was termed finite domain constraints.
In the 1990s, researchers transformed constraint logic programming based on Prolog to constraint programming by providing constraint programming features in general-purpose programming languages. Examples includes Pecos for Lisp [Puget 1992], ILOG Solver for C++ [ILOG 1999], and Screamer for Common Lisp [Siskind and McAllester 1993]. This development made possible powerful constraint solving algorithms in the context of mainstream programming languages [Puget and Leconte 1995]. Another rich area of research in constraint programming has been the development of special-purpose programming languages to allow people to apply the techniques of constraint programming to different classes of problems. Examples include Oz [Smolka 1993] and CLAIRE [Caseau and Laburthe 1995]. In designing such languages, their developers have sought to provide complete languages for doing computer programming and hence the languages allow users to implement constraint solving algorithms. Departing from this approach, Van Hentenryck [1999] designed OPL (Optimization Programming Language) to make it easy to solve optimization problems by supporting constraint programming and mathematical programming techniques. He did not deem the completeness of the language for computer programming or the ability to program constraint solving algorithms as important. Instead, he designed the language to support the declarative representation of optimization problems, providing the facilities to use an underlying constraint programming engine combined with the ability to describe, via computer programming techniques, a search strategy for finding solutions to problems. The OPL language is not a complete computer programming language, but rather a language that is designed to allow people to solve optimization problems using either constraint programming or mathematical programming techniques. An advantage of OPL is that the same language is used to unify the representations of decision variables from traditional mathematical programming with programming variables from traditional constraint programming. Some of the examples we present are related to those Van Hentenryck [1999] presents.
Van Hentenryck was motivated to design OPL by the increased interest in mathematical programming modeling languages, such as AMPL [Fourer, Gay, and Kernighan 1993] and GAMS [Bisschop and Meeraus 1982], and the recent use of constraint programming to solve combinatorial optimization problems. These NP-hard problems include feasibility problems as well as optimization problems. Constraint programming is often used when people want a quick feasible solution to a problem rather than a provably optimal solution. Because a constraint programming system provides a rich declarative language for stating problems combined with a programming language for describing a procedural strategy to find a solution, constraint programming is an alternative to integer programming for solving a variety of combinatorial optimization problems.
Van Hentenryck [1989], Marriott and Stuckey [1999], and Hooker [2000] describe some of the underlying theory of constraint programming. In his book about OPL, Van Hentenryck [1999] gives a number of examples of how constraint programming can be applied to real problems. Unfortunately, we have yet to find a good book that gives the techniques for applying constraint programming to solve optimization problems and is written in the spirit of the book by Williams [1999] for mathematical programming. Williams demonstrates a wide variety of modeling techniques for solving problems using mathematical programming.
Constraint Programming Formulations
To explain the constraint programming framework, we will first characterize the ways that constraint programming can be applied to solve combinatorial optimization problems by developing a notation to describe these problems. Then we will show formulations of feasibility problems and optimization problems using the OPL language.
Acknowledgments
We would like to acknowledge the comments of the two anonymous referees as well as the copyeditor. Their comments greatly improved the presentation of this paper.
References
Bisschop, Johannes and Meeraus, Alexander 1982, "On the development of a general algebraic modeling system in a strategic planning environment," Mathematical Programming Study 20, pp. 1-29.
Brearley, A. L.; Mitra, Gautam; and Williams, H. P. 1975, "Analysis of mathematical programming problems prior to applying the simplex algorithm," Mathematical Programming, Vol. 8, No. 1, pp. 54-83.
Caseau, Yves and Laburthe, F. 1995, "The Claire documentation," LIENS Report 96-15, Ecole Normale Superieure, Paris.
Colmerauer, Alain 1990, "An introduction to PROLOG III," Communications of the ACM, Vol. 33, No. 7, pp. 70-90.
Dantzig, George B. 1948, "Programming in a linear structure," Comptroller, USAF, Washington, DC, February.
Dantzig, George B. 1949, "Programming of interdependent activities, II, mathematical model," Econometrica, Vol. 17, Nos. 3 and 4 (July-October), pp. 200-211.
Dantzig, George B. 1963, Linear Programming and Extensions, Princeton University Press, Princeton, New Jersey.
Dantzig, George B. and Thapa, Mukund N. 1997, Linear Programming 1: Introduction, Springer, New York.
Dash Associates 2000, XPRESS-MP Optimiser Subroutine Library XOSL Reference Manual (Release 12), Dash Associates, Blisworth, United Kingdom.
Dincbas, Mehmet; Van Hentenryck, Pascal; Simonis, Helmut; Aggoun, Abderrahmane; Graf, T.; and Berthier, F. 1988, "The constraint logic programming language CHIP," Proceedings of the International Conference on Fifth Generation Computer Systems, Tokyo, Japan, December.
Fourer, Robert; Gay, David M.; and Kernighan, Brian W. 1993, AMPL: A Modeling Language for Mathematical Programming, Scientific Press, San Francisco, California.
Garfinkel, Robert S. and Nemhauser, George L. 1972, Integer Programming, John Wiley and
Sons, New York.
Gusfield, Dan and Irving, Robert W. 1989, The Stable Marriage Problem: Structure and Algorithms, MIT Press, Cambridge, Massachusetts.
Harvey, William D. and Ginsberg, Matthew L. 1995, "Limited discrepancy search," Proceedings of the International Joint Conference on Artificial Intelligence (IJCAI), Vol. 1, pp. 607-613.
Hooker, John 2000, Logic-Based Methods for Optimization: Combining Optimization and Constraint Satisfaction, John Wiley and Sons, New York.
IBM 1990, Optimization Subroutine Library Guide and Reference (Release 1), IBM, Kingston, New York.
ILOG 1999, ILOG Solver 4.4 Users Manual, ILOG, Gentilly, France.
ILOG 2000, ILOG CPLEX 7.0 Reference Manual, ILOG, Gentilly, France.
Jaffar, Joxan and Lassez, Jean-Louis 1987, "Constraint logic programming," Conference Record of the Fourteenth Annual ACM Symposium on Principles of Programming Languages, Munich, Germany, pp. 111-119.
Jain, Vipul and Grossman, Ignacio 2000, "Algorithms for hybrid MILP/CP models for a class of optimization problems," working paper, Department of Chemical Engineering, Carnegie Mellon University.
Knuth, Donald E. 1968, Fundamental Algorithms, The Art of Computer Programming, Vol. 1, second edition, Addison-Wesley, Reading, Massachusetts.
Lauriere, Jean-Louis 1978, "A language and a program for stating and solving combinatorial problems," Artificial Intelligence, Vol. 10, No. 1, pp. 29-127.
Lawler, Eugene L. and Wood, D. E. 1966, "Branch-and-bound methods: A survey," Operations Research, Vol. 14, No. 4, pp. 699-- 719.
Mackworth, Alan K. 1977, "Consistency in networks of relations," Artificial Intelligence, Vol. 8, No. 1, pp. 99-118.
Marriott, Kim and Stuckey, Peter J. 1999, Programming with Constraints: An Introduction, MIT Press, Cambridge, Massachusetts.
Meseguer, Pedro 1997, "Interleaved depth-first search," Proceedings of the International Joint Conference on Artificial Intelligence (IJCAI), Vol. 2, pp. 1382-1387.
Nemhauser, George W. and Wolsey, Laurence A. 1988, Integer Programming, John Wiley and Sons, New York.
Nemhauser, George W.; Savelsbergh, Martin W. P.; and Sigismondi, Gabriele C. 1994, "MINTO, a Mixed INTeger Optimizer," Operations Research Letters, Vol. 15, No. 1, pp. 47-58.
Nilsson, Nils J. 1971, Problem Solving Methods in Artificial Intelligence, McGraw-Hill, New York.
Puget, Jean-Frangois 1992, "Pecos: A high level constraint programming language," Proceedings of the Singapore International Conference on Intelligent Systems (SPICIS), Singapore, pp. 137-142.
Puget, Jean-Francois and Leconte, Michel 1995, "Beyond the glass box: Constraints as objects," Logic Programming: Proceedings of the 1995 International Symposium, ed. John Lloyd, MIT Press, Cambridge, Massachusetts, pp. 513-527.
Siskind, Jeffrey M. and McAllester, David A. 1993, "Nondeterministic Lisp as a substrait for constraint logic programming," Proceedings of the Twelfth National Conference on Artificial Intelligence (AAAI-93), pp. 133-138.
Smolka, G. 1993, "Survey of Oz: A higher-order concurrent constraint language," Proceedings of ICLP '93: Post-Conference Workshop of Concurrent Constraint Programming, Budapest, Hungary, June 24-25, 1993.
Van Hentenryck, Pascal 1989, Constraint Satisfaction in Logic Programming, MIT Press, Cambridge, Massachusetts.
Van Hentenryck, Pascal 1999, The OPL Optimization Programming Language, MIT Press, Cambridge, Massachusetts.
Van Hentenryck, Pascal; Deville, Yves; and Teng, C. M. 1992, "A generic arc-consistency algorithm and its specializations," Artificial Intelligence, Vol. 57, No. 2, pp. 291-321.
Wallace, Mark; Novello, Stefano; and Schimpf, Joachim 1997, "ECLiPSe: A platform for constraint logic programming," ICL Systems Journal, Vol. 12, No. 1, pp. 159-200.
Walsh, Toby 1997, "Depth-bounded discrepancy search," Proceedings of the International Joint Conference on Artificial Intelligence (IJCAI), Vol. 2, pp. 1388-1393.
Williams, H. P. 1999, Model Building in Mathematical Programming, fourth edition, John Wiley and Sons, New York.
IRVIN J. LUSTIG
ILOG
1080 Linda Vista Avenue
Mountain View, California 94043
JEAN-FRANCOIS PUGET
ILOG
9 rue Verdun
BP 85
Gentilly Cedex, France
Irvin J. Lustig is the optimization evangelist at ILOG, delivering messages to the marketplace about ILOG's optimization products. Previously he was a developer of ILOG CPLEX and a faculty member at Princeton. Since 1997, he has concentrated on explaining constraint programming to OR professionals.
Jean-Francois Puget is vice president of optimization R and D at ILOG. He was the principal developer of ILOG Solver. His main research interests are in the cooperation between math programming and constraint programming techniques and the develop
ment of easier-to-use optimization software.
Copyright Institute for Operations Research and the Management Sciences Nov/Dec 2001