Operation Research course

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

THE SHORTEST-PATH PROBLEM Although several other versions of the shortest-path problem (including some for directed networks) are mentioned at the end of the section, we shall focus on the following simple version. Consider an undi r ecte d and connected network with two special nodes called the origin and the destination. Associated with each of the links (undirected arcs) is a non- negative distance. The objective is to find the shortest path (the path with the minimum total distance) from the origin to the destination. A relatively straightforward algorithm is available for this problem. The essence of this procedure is that it fans out from the origin, successively identifying the shortest path to each of the nodes of the network in the ascending order of their (shortest) distances from the origin, thereby solving the problem when the destination node is reached. We shall first outline the method and then illustrate it by solving the shortest-path problem encountered by the See

THE TERMINOLOGY OF NETWORKS A relatively extensive terminology has been developed to describe the various kinds of networks and their components. Although we have avoided as much of this special vocabulary as we could, we still need to introduce a considerable number of terms for use throughout the chapter. We suggest that you read through this section once at the outset to understand the definitions and then plan to return to refresh your memory as the terms are used in subsequent sections. To assist you, each term is highlighted in boldface at the point where it is defined. A network consists of a set of points and a set of lines connecting certain pairs of the points. The points are called nodes (or vertices); e.g., the network in Fig. 10.1 has seven nodes designated by the seven circles. The lines are called a r c s (or links or edges or branches); e.g., the network in Fig. 10.1 has 12 arcs corresponding to the 12 roads in the road system. Arcs are labeled by naming the nodes a

PROTOTYPE EXAMPLE SEERVADA PARK has recently been set aside for a limited amount of sightseeing and backpack hiking. Cars are not allowed into the park, but there is a narrow, winding road system for trams and for jeeps driven by the park rangers. This road system is shown (without the curves) in Fig. 10.1, where location O is the entrance into the park; other letters designate the locations of ranger stations (and other limited facilities). The numbers give the distances of these winding roads in miles. The park contains a scenic wonder at station T . A small number of trams are used to transport sightseers from the park entrance to station T and back. The park management currently faces three problems. One is to determine which route from the park entrance to station T has the smallest total distance for the operation of the trams. (This is an example of the shortest-path problem to be discussed in Sec. 10.3.) A second problem is that telephone lines must be installed under

Networks arise in numerous settings and in a variety of guises. Transportation, electrical, and communication networks pervade our daily lives. Network representations also are widely used for problems in such diverse areas as production, distribution, project planning, facilities location, resource management, supply chain management and financial planning— to name just a few examples. In fact, a network representation provides such a powerful visual and conceptual aid for portraying the relationships between the components of systemsthat it is used in virtually every field of scientific, social, and economic endeavor. One of the most exciting developments in operations research (OR) in recent decades, has been the unusually rapid advance in both the methodology and application of network optimization models. A number of algorithmic breakthroughs have had a major impact, as have ideas from computer science concerning data structures and efficient data manipulation. Consequently, a

SELECTED REFERENCES 1. Achterberg, A.: “SCIP: Solving Constraint Integer Programs,” Mathematical Programming Computation , 1 (1): 1-41, July 2009. 2. Appa, G., L. Pitsoulis, and H. P. Williams (eds.): Handbook on Modelling for Discrete Opti- mization , Springer, New York, 2006. 3. Baptiste, P., C. LePape, and W. Nuijten: Constraint-Based Scheduling: Applying Constraint Pro- gramming to Scheduling Problems , Kluwer Academic Publishers (now Springer), Boston, 2001. 4. Hillier, F. S., and M. S. Hillier: Introduction to Management Science: A Modeling and Case Studies Approach with Spreadsheets, 5th ed., McGraw-Hill/Irwin, Burr Ridge, IL, 2014, chap. 7. 5. Hooker, J. N.: Integrated Methods for Optimization , 2nd ed., Springer, New York, 2012. 6. Karlof, J. K.: Integer Programming: Theory and Practice , CRC Press, Boca Raton, FL, 2006. 7. Li, D., and X. Sun: Nonlinear Integer Programming , Springer, New York, 2006. (A 2nd edition currently is being prepared with publication sch

CONCLUSIONS IP problems arise frequently because some or all of the decision variables must be restricted to integer values. There also are many applications involving yes-or-no decisions (including combinatorial relationships expressible in terms of such decisions) that can be represented by binary (0–1) variables. These factors have made integer programming one of the most widely used OR techniques. IP problems are more difficult than they would be without the integer restriction, so the algorithms available for integer programming are generally considerably less efficient than the simplex method. However, there has been tremendous progress over the past two or three decades in the ability to solve some (but not all) huge IP problems with tens or even hundreds of thousands of integer variables. This progress is due to a combination of three factors—dramatic improvements in IP algorithms, striking improvement in the linear programming algorithms used within IP algorithms, and the

Current Research Current research in integrating constraint programming and integer programming is moving along several parallel paths. For example, the most straightforward approach is to simultaneously use both a constraint programming model and an integer programming model to represent complementary parts of a problem. Thus, each relevant constraint is included in whichever model it fits or, when feasible, in both models. As a constraint programming algorithm and an integer programming algorithm are applied to the respective models, information is passed back and forth to focus the search on the feasible solutions (those that satisfy the constraints of both models). This kind of double modeling scheme can be implemented with the Optimization Programming Language (OPL) that is incorporated into the OPL-CPLEX Development System. After employing the OPL modeling language, the OPL-CPLEX Development System can invoke both a constraint programming algorithm (CP Optimizer) and a math

The Element Constraint The elemen t global constraint is most commonly used to look up a cost or profit associated with an integer variable. In particular, suppose that a variable y has domain {1, 2, . . . , n } and that the cost associated with each of these values is c 1, c 2, . . . , c n , respectively. Then the constraint element ( y , [ c 1, c 2, . . . , c n ], z ) constrains the variable z to equal the y th constant in the list [ c 1, c 2, . . . , c n ]. In other words, z = c y . This variable z can now be included in the objective function to provide the cost associated with y . To illustrate the use of the element constraint, consider the assignment problem again and let c i j = cost of assigning assignee i to task j for i , j , = 1, 2, . . . , n . The complete constraint programming model (including the ob- jective function for this problem is Minimize Z = I z i , i =1 subject to element ( y i , [ c i 1, c i 2, . . . , c i n ], z i ) for i = 1, 2, . . . , n

The All-Different Constraint The all-different global constraint simply specifies that all the variables in a given set must have different values. If x 1, x 2, . . . , x n are the variables involved, the constraint can be written succinctly as all-different ( x 1, x 2, . . . , x n ) while also specifying the domains of the individual variables in the model. (These domains collectively need to include at least n different values in order to enforce the all-different constraint.) To illustrate this constraint, consider the classical assignment problem presented in Sec. 9.3. Recall that this problem involves assigning n assignees to n tasks on a one- to-one basis so as to minimize the total cost of these assignments. Although the as- signment problem is a particularly easy one to solve (as described in Sec. 9.4), it nicely illustrates how the all-different constraint can greatly simplify the formulation of the model. With the traditional formulation presented in Sec. 9.3, the dec

The Potential of Constraint Programming In the 1990s, constraint programming features, including powerful constraint-solving algorithms, were successfully incorporated into a number of general-purpose programming languages, as well as several special-purpose programming languages. This brought computer science closer and closer to the Holy Grail of computer programming, namely, allowing the user to simply state the problem and then the computer will solve it. As word of this exciting development began to spread beyond the computer science community, researchers in operations research began to realize the great potential of integrating constraint programming with the traditional techniques of integer programming (and other areas of mathematical programming as well). The much greater flexibility in expressing the constraints of the problem should greatly increase the ability to formulate valid models for complex problems. It also should lead to much more compact and straight- forward

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 proc

Generating Cutting Planes for Pure BIP A cutting plane (or cut ) for any IP problem is a new functional constraint that reduces the feasible region for the LP relaxation without eliminating any feasible solutions for the IP problem. In fact, you have just seen one way of generating cutting planes for pure BIP prob- lems, namely, apply the above procedure for tightening constraints. Thus, x 1 + x 2 ::: 1 is a cutting plane for the BIP problem considered in Fig. 12.14, which leads to the reduced fea- sible region for the LP relaxation shown in Fig. 12.15. In addition to this procedure, a number of other techniques have been developed for generating cutting planes that will tend to accelerate how quickly a branch-and-bound algorithm can find an optimal solution for a pure BIP problem. We will focus on just one of these techniques. To illustrate this technique, consider the California Manufacturing Co. pure BIP prob- lem presented in Sec. 12.1 and used to illustrate the BIP branch-an

Automatic Problem Preprocessing for Pure BIP Automatic problem preprocessing involves a “computer inspection” of the user-supplied formulation of the IP problem in order to spot reformulations that make the problem quicker to solve without eliminating any feasible solutions. These reformulations fall into three categories: 1. F ixing variables: Identify variables that can be fixed at one of their possible values (either 0 or 1) because the other value cannot possibly be part of a solution that is both feasible and optimal. 2. Eliminating redundant constraints: Identify and eliminate redundant constraints (constraints that automatically are satisfied by solutions that satisfy all the other constraints). 3. T ightenin g constraints: Tighten some constraints in a way that reduces the feasible region for the LP relaxation without eliminating any feasible solutions for the BIP problem. These categories are described in turn. Fixin g Variables. One general principle for fixing va