INTEGER PROGRAMMING:THE INCORPORATION OF CONSTRAINT PROGRAMMING

By -

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:

INTRODUCTION TO OPERATIONS RESEARCH-0158

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.

Comments

Post a Comment

Popular posts from this blog

DUALITY THEORY:THE ESSENCE OF DUALITY THEORY

By -
Image
THE ESSENCE OF DUALITY THEORY Given our standard form for the primal problem at the left (perhaps after conversion from another form), its dual problem has the form shown to the right. Thus, with the primal problem in maximizatio n form, the dual problem is in minimization form instead. Furthermore, the dual problem uses exactly the same pa r amete r s as the primal problem, but in different locations, as summarized below. 1. The coefficients in the objective function of the primal problem are the right-hand sides of the functional constraints in the dual problem. 2. The right-hand sides of the functional constraints in the primal problem are the coef- ficients in the objective function of the dual problem. 3. The coefficients of a variable in the functional constraints of the primal problem are the coefficients in a functional constraint of the dual problem. To highlight the comparison, now look at these same two problems in matrix notation (as introduced at the beginn...
Read more

NETWORK OPTIMIZATION MODELS:THE MINIMUM SPANNING TREE PROBLEM

By -
Image
THE MINIMUM SPANNING TREE PROBLEM The minimum spanning tree problem bears some similarities to the main version of the shortest-path problem presented in the preceding section. In both cases, an undi r ecte d and connected network is being considered, where the given information includes some mea- sure of the positive length (distance, cost, time, etc.) associated with each link. Both problems also involve choosing a set of links that have the shortest total length among all sets of links that satisfy a certain property. For the shortest-path problem, this property is that the chosen links must provide a path between the origin and the destination. For the minimum spanning tree problem, the required property is that the chosen links must provide a path between ea c h pair of nodes. The minimum spanning tree problem can be summarized as follows: 1. You are given the nodes of a network but not the links. Instead, you are given the po- tential links and the positive length for each ...
Read more

INTEGER PROGRAMMING:THE BRANCH-AND-CUT APPROACH TO SOLVING BIP PROBLEMS

By -
TH E BRANCH-AND-CUT APPROACH TO SOLVING BIP PROBLEMS Integer programming has been an especially exciting area of OR since the mid-1980s be- cause of the dramatic progress being made in its solution methodology. Background To place this progress into perspective, consider the historical background. One big break- through had come in the 1960s and early 1970s with the development and refinement of the branch-and-bound approach. But then the state of the art seemed to hit a plateau. Rel- atively small problems (well under 100 variables) could be solved very efficiently, but even a modest increase in problem size might cause an explosion in computation time be- yond feasible limits. Little progress was being made in overcoming this exponential growth in computation time as the problem size was increased. Many important problems arising in practice could not be solved. Then came the next breakthrough in the mid-1980s, with the introduction of the b r an c h- and-cu t approach to sol...
Read more