INTEGER PROGRAMMING:THE INCORPORATION OF CONSTRAINT PROGRAMMING

THE INCORPORATION OF CONSTRAINT PROGRAMMING

No presentation of the basic ideas of integer programming is complete these days without introducing an exciting relatively recent development––the incorporation of the techniques of constraint programming––that is promising to greatly expand our ability to formulate and solve integer programming models. (These same techniques also are beginning to be used in related areas of mathematical programming, especially combinatorial optimiza- tion, but we will limit our discussion to their central use in integer programming.)

The Nature of Constraint Programming

In the mid-1980s, researchers in the computer science community began to develop con- straint programming by combining ideas in artificial intelligence with the development of computer programming languages. The goal was to have a flexible computer program- ming system that would include both variables and constraints on their values, while also allowing the description of search procedures that would generate feasible values of the variables. Each variable has a domain of possible values, e.g., {2, 4, 6, 8, 10}. Rather than being limited to the types of mathematical constraints used in mathematical programming, there is great flexibility in how to state the constraints. In particular, the constraints can be any of the following types:

lists the only feasible solutions for the problem. This kind of feasibility reasoning based on alternating between the application of domain reduction and constraint propagation algorithms is a key part of constraint programming.

After the application of the constraint propagation and domain reduction algo- rithms to a problem, a search procedure is used to find complete feasible solutions. In

the example above, since the domains of all the variables have been reduced to a sin- gle value except for x4, the search procedure would simply try the values x4 = 4 and x4 = 5 to determine the complete feasible solutions for that problem. However, for a problem with many constraints and variables, the constraint propagation and domain reduction algorithms typically do not reduce the domain of each variable to a single value. It is therefore necessary to write a search procedure that will try different as- signments of values to the variables. As these assignments are tried, the constraint prop- agation algorithm is triggered and further domain reduction occurs. The process creates a search tree, which is similar to the branching tree when applying the branch-and-bound technique to integer programming.

The overall process of applying constraint programming to complicated IP problems (or related problems) involves the following three steps:

1. Formulate a compact model for the problem by using a variety of constraint types (most of which do not fit the format of integer programming).

2. Efficiently find feasible solutions that satisfy all these constraints.

3. Search among these feasible solutions for an optimal solution.

The power of constraint programming lies in its great ability to perform the first two steps rather than the third, whereas the main strength of integer programming and its algorithms lie in performing the third step. Thus, constraint programming is ideally suited for a highly constrained problem that has no objective function, so the only goal is to find a feasible solution. However, it also can be extended to the third step. One method of doing so is to enumerate the feasible solutions and calculate the value of the objec- tive function for each one. However, this would be extremely inefficient for problems where there are numerous feasible solutions. To circumvent this drawback, the common approach is to add a constraint that tightly bounds the objective function to values that are very near to what is anticipated for an optimal solution. For example, if the objec- tive is to maximize the objective function and its value Z is anticipated to be approxi- mately Z = 10 for an optimal solution, one might add the constraint that Z ::: 9 so that the only remaining feasible solutions to be enumerated are those that are very close to being optimal. Each time that a new best solution then is found during the search, the bound on Z can be further tightened to consider only feasible solutions that are at least as good as the current best solution.

Although this is a reasonable approach to the third step, a more attractive approach would be to integrate constraint programming and integer programming so that each is mainly used where it is strongest—steps 1 and 2 with constraint programming and step 3 with integer programming. This is part of the potential of constraint programming de- scribed next.