Content area
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...