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

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

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

DECISION SUPPORT SYSTEMS:DIALOG GENERATION AND MANAGEMENT SYSTEMS

By -
Image
DIALOG GENERATION AND MANAGEMENT SYSTEMS In our efforts in this chapter, we envision a basic DSS structure of the form shown in Figure 12. This figure also shows many of the operational functions of the database management system (DBMS) and the model base management system (MBMS). The primary purpose of the dialog generation and management system (DGMS) is to enhance the propensity and ability of the system user to use and benefit from the DSS. There are doubtless few users of a DSS who use it because of necessity. Most uses of a DSS are optional, and the decision maker must have some motivation and desire to use a DSS or it will likely remain unused. DSS use can occur in a variety of ways. In all uses of a DGMS, it is the DGMS that the user interacts with. In an early seminal text, Bennett (1983) posed three questions to indicate this centrality: 1. What presentations is the user able to see at the DSS display terminal? 2. What must the user know about what is seen at the display
Read more