CHAPTER 6 Network Models There is a multitude of operations research situations that can be modeled and solved as networks (nodes connected by branches). Some recent surveys report that as much as 70% of the real-world mathematical programming problems can be represented by network-related models. The following list illustrates possible applications of networks. 1. Design of an offshore natural gas pipeline network connecting wellheads in the Gulf of Mexico to an inshore delivery point. The objective of the model is to minimize the cost of constructing the pipeline. 2. Determination of the shortest route between two cities in a network of roads. 3. Determination of the maximum capacity (in tons per year) of a coal slurry pipeline network joining the coal mines in Wyoming with the power plants in Houston. (Slurry pipelines transport coal by pumping water through specially designed pipes.) 4. Determination of the minimum-cost flow schedule from oil fields to refineries through a pipeline network. 5. Determination of the time schedule (start and completion dates) for the activities of a construction project. The solution of these situations, and others like it, is accomplished through a variety of network optimization algorithms. This chapter will present five of these algorithms. 1. Minimal spanning tree (situation 1) 2. Shortest-route algorithm (situation 2) 3. Maximum flow algorithm (situation 3) 4. Minimum-cost capacitated network algorithm (situation 4) 5. Critical path (CPM) algorithm (situation 5) 213 214 Chapter 6 Network Models The situations for which these algorithms apply can also be formulated and solved as explicit linear programs. However, the proposed network-based algorithms are more efficient than the simplex method. 6.1 NETWORK DEFINITIONS A network consists of a set of nodes linked by arcs (or branches). The notation for describing a network is (N, A), where N is the set of nodes, and A is the set of arcs. As an illustration, the network in Figure 6.1 is described as N = {1,2,3,4,5} A = {(1,2),(1,3),(2,3),(2,5),(3,4),(3,5),(4.2),(4,5)} FIGURE 6.1 Example of (N,A) network Associated with each network is some type of flow (e.g., oil products flow in a pipeline and automobile traffic flows on highways). In general, the flow in a network is limited by the capacity of its arcs, which may be finite or infinite. An arc is said to be directed or oriented if it allows positive flow in one direction and zero flow in the opposite direction. A directed network has all directed arcs. A path is a sequence of distinct arcs that join two nodes through other nodes regardless of the direction of flow in each arc. A path forms a cycle if it connects a node to itself through other nodes. For example, in Figure 6.1, arcs (2,3), (3,5), and (5,2) form a loop. A cycle is directed if it consists of a directed path; e.g., (2,3), (3,4), and (4,2) in Figure 6.1. A connected network is such that every two distinct nodes arc linked by at least one path. The network in Figure 6.1 demonstrates this type of network. A tree is a connected network that may involve only a subset of all the nodes of the network with no cycles allowed, and a spanning tree is a tree that links all the nodes of the network, also with no cycles allowed. Figure 6.2 provides examples of a tree and a spanning tree for the network in Figure 6.1. FIGURE 6.2 Examples of a tree and a spanning tree given the network in Figure 6.1 Tree Spanning tree 6.2 Minimal Spanning Tree Algorithm 215 PROBLEM SET 6.1A 1. For each network in Figure 6.3 determine (a) a path, (b) a cycle, (c) a directed cycle, (d) a tree, and (e) a spanning tree. FIGURE 6.3 Networks for Problem 1, Set 6.1a 2. Determine the sets jV and A for the networks in Figure 6.3. 3. Draw the network defined by N = {1,2,3,4,5,6} A = {(ls2), (1,5), (2,3), (2,4), (3,5), (3,4), (4,3), (4,6), (5,2), (5,6)} 4. Consider eight equal squares arranged in three rows, with two squares in the first row, four in the second, and two in the third. The squares of each row are arranged symmetrically about the vertical axis. It is desired to fill the squares with distinct numbers in the range 1, 2,..., and 8 so that no two adjacent vertical, horizontal, or diagonal squares hold consecutive numbers. Use network representation as a vehicle to find the solution in a systematic way. 5. Three inmates escorted by 3 guards must be transported by boat from San Francisco to the Alcatraz penitentiary island to serve their sentences. The boat cannot transfer more than two persons in either direction. The inmates are certain to overpower the guards if they outnumber them at any time. Develop a network model that designs the boat trips in a manner that ensures a safe transfer of the inmates. Assume that the inmates will not flee if given a chance. MINIMAL SPANNING TREE ALGORITHM The minimal spanning tree algorithm deals with linking the nodes of a network, directly or indirectly, using the shortest length of connecting branches. A typical application occurs in the construction of paved roads that link several towns. The road between two towns may pass through one or more other towns. The most economical design of the road system calls for minimizing the total miles of paved roads, a result that is achieved by implementing the minimal spanning tree algorithm. The steps of the procedure are given as follows. Let N = {1,2, ...,«} be the set of nodes of the network and define Ck = Set of nodes that have been permanently connected at iterations Ck = Set of nodes as yet to be connected permanently 216 Chapter 6 Network Models Step 0. Set C0 = 0 and C„ = N. Step 1. Start with any node, i, in the unconnected set C0 and set C\ = {;'}, which renders Cx = N - {/}. Set k - 2. General Step k. Select a node, /, in the unconnected set Ck-l that yields the shortest arc to a node in the connected set Q.-,. Link / permanently to and remove it from C4_l5 that is, ck = Cfc_, + {j\Ck = Ckl- {/} If the set of unconnected nodes, Ck, is empty, stop. Otherwise, set k — k + 1 and repeat the step. Example 6.2-1 Midwest TV Cable Company is in the process of providing cable service to five new housing development areas. Figure 6.4 depicts possible TV linkages among the five areas. The cable miles are shown on each arc. Determine the most economical cable network. The algorithm starts at node 1 (any other node will do as well), which gives C, = {l},Ci = {2,3,4,5,6} The iterations of the algorithm are summarized in Figure 6.5. The thin arcs provide all the candidate links between C and C. The thick branches represent the permanent links among the nodes of the connected set C, and the dashed branch represents the new (permanent) link added at each iteration. For example, in iteration 1, branch (1,2) is the shortest link ( = 1 mile) among ah the candidate branches from node 1 to nodes 2, 3, 4, and 5 of the unconnected set Cx. Hence, link (1,2) is made permanent and / = 2, which yields C2 = {1,2}, C2 = {3,4,5,6} The solution is given by the minimal spanning tree shown in iteration 6 of Figure 6.5. The resulting minimum cable miles needed to provide the desired cable service are 1 + 3 + 4 + 3 + 5 = 16 miles. FIGURE 6.4 Cable connections for Midwest TV Cable Company 2 3 (miles) 6 5 6.2 Minimal Spanning Tree Algorithm 217 Iteration 1 Iteration 2 Iteration 3 Iteration 4 FIGURE 6.5 Solution iterations Iteration 5 Iteration 6 for Midwest TV (Minimal spanning tree) Cable Company You can use TORA to generate the iterations of the minimal spanning tree. From Main menu, select Ketwork models Minimal spanning tree. Next,from S0LVE/K0DX7Y menu, select Solve problem =>• Go ~o oatpac screen. In the output screen, select a starting node and then use Next iteration or aii iterat ions to generate the successive iterations. You can restart the iterations by selecting a new stalling node. Figure 6.6 gives TORA output for Example 6.2-1 (file ch6ToraMinSpanEx6-2-l.txt). 218 Chapter 6 Network Models FIGURE 6.6 Output of the minimal spanning tree of Example 6.2-1 PROBLEM SET 6.2A 1. Solve Example 6.2-1 starting at node 5 (instead of node 1), and show that the algorithm produces the same solution. 2. Determine the minimal spanning tree of the network of Example 6.2-1 under each of the following separate conditions: (a) Nodes 5 and 6 are linked by a 2-mile cable. (b) Nodes 2 and 5 cannot be linked. (c) Nodes 2 and 6 are linked by a 4-mile cable. (d) The cable between nodes 1 and 2 is 8 miles long. (e) Nodes 3 and 5 are linked by a 2-mile cable. (f) Node 2 cannot be linked directly to nodes 3 and 5. 3. In intermodal transportation, loaded truck trailers are shipped between railroad terminals by placing the trailer on special flatbed carts. Figure 6.7 shows the location of the main railroad terminals in the United States and the existing railroad tracks. The objective is to decide which tracks should be "revitalized" to handle the intermodal traffic. In particular, the Los Angeles (LA) terminal must be linked directly to Chicago (CH) to accommodate expected heavy traffic. Other than that, all the remaining terminals can be linked, directly or indirectly, such that the total length (in miles) of the selected tracks is minimized. Determine the segments of the railroad tracks that must be included in the revitalization program. 6.2 Minimal Spanning Tree Algorithm 219 FIGURE 6.7 Network for Problem 3, Set 6.2a 4. Figure 6.8 gives the mileage of the feasible links connecting nine offshore natural gas wellheads with an inshore delivery point. Because the location of wellhead 1 is the closest to shore, it is equipped with sufficient pumping and storage capacity to pump the output of the remaining eight wells to the delivery point. Determine the minimum pipeline network that links the wellheads to the delivery point. FIGURE 6.8 Network for Problem 4, Set 6.2a 5. In Figure 6.8 of Problem 4, suppose that the wellheads can be divided into two groups depending on gas pressure: a high-pressure group that includes wells 2,3,4, and 6; and a low-pressure group that includes wells 5,7,8, and 9. Because of pressure difference, wellheads from the two groups cannot be linked. At the same time, both groups must be connected to the delivery point through wellhead 1. Determine the minimum pipeline network for this situation. 6. Electro produces 15 electronic parts on 10 machines. The company wants to group the machines into cells designed to minimize the "dissimilarities" among the parts processed 220 Chapter 6 Network Models in each cell. A measure of "dissimilarity," dy, among the parts processed on machines i and / can be expressed as 4 = 1---r— where n:j is the number of parts shared between machines i and and w,, is the number of parts that are used by either machine i or ; only. Tire following table assigns the parts to machines: Machine Assigned parts 1 1,6 2 2,3,7,8,9,12,13,15 3 3,5,10,14 4 2,7,8,11,12,13 5 3,5.10,11,14 6 1,4,5,9,10 7 2,5.7,8,9.10 8 3,4,15 9 4,10 10 3,8,10,14,15 (a) Express the problem as a network model. (b) Show that the determination of the cells can be based on the minimal spanning tree solution. (c) For the data given in the preceding table, construct the two- and three-cell solutions. 6.3 SHORTEST-ROUTE PROBLEM The shortest-route problem determines the shortest route between a source and destination in a transportation network. Other situations can be represented by the same model as illustrated by the following examples. 6.3.1 Examples of the Shortest-Route Applications Example 6.3-1 (Equipment Replacement) RentCar is developing a replacement plan for its car fleet for a 4-year planning horizon that starts January 1,2001, and terminates December 31,2004. At the start of each year, a decision is made as to whether a car should be kept in operation or replaced. A car must be in service a minimum of 1 year and a maximum of 3 years. The following table provides the replacement cost as a function of the year a car is acquired and the number of years in operation. Equipment acquired at start of Replacement cost ($) tor given years in operation 1 2 3 2001 4000 5400 9800 2002 4300 6200 8700 2003 4800 7100 - 2004 4900 — — 6.3 Shortest-Route Problem 221 98(10 FIGURE 6.9 Equipment replacement problem as a shortest-route model The problem can be formulated as a network in which nodes 1 to 5 represent the start of years 2001 to 2005. Arcs from node 1 (year 2001) can reach only nodes 2,3, and 4 because a car must be in operation between 1 and 3 years. The arcs from the other nodes can be interpreted similarly. The length of each arc equals the replacement cost. The solution of the problem is equivalent to finding the shortest route between nodes 1 and 5. Figure 6.9 shows the resulting network. Using TORA,1 the shortest route (shown by the thick path) is 1 —>• 3 —^ 5. The solution means that a car acquired at the start of 2001 (node 1) must be replaced after 2 years at the start of 2003 (node 3). The replacement car will then be kept in service until the end of 2004. The total cost of this replacement policy is $ 12,500 (= $5400 + $7100). Example 6.3-2 (Most Reliable Route) I. Q. Smart drives daily to work. Having just completed a course in network analysis, Smart is able to determine the shortest route to work. Unfortunately, the selected route is heavily patrolled by police, and with all the fines paid for speeding, the shortest route may not be the best choice. Smart has thus decided to choose a route that maximizes the probability of not being stopped by police. The network in Figure 6.10 shows the possible routes between home and work, and the associated probabilities of not being stopped on each segment. The probability of not being stopped on the way to work is the product of the probabilities associated with the successive segments of the selected route. For example, the probability of not FIGURE 6.10 Most-reliablc-route network model 'From Kai:: menu, select Vhrek ircdelc => Shr.rt.est route. From solve/modify menu, select Solve problem =S- Shortest routes. 222 Chapter 6 Network Models receiving a fine on the route 1 -> 3 -> 5 —> 7 is .9 X .3 X .25 = .0675. Smart's objective is to select the route that maximizes the probability of not being fined. The problem can be formulated as a shortest-route model by using a logarithmic transformation that converts the product probability into the sum of the logarithms of probabilities—that is, if plk = px X p2 X ... X pk is the probability of not being stopped, then logplk = logpi + logp2 + •-• + logPt- Mathematically, the maximization of plk is equivalent to the maximization of logpu. Because logplk < 0, the maximization of logp[k is, in turn, equivalent to the minimization of - log plk. Using this transformation, the individual probabilities pj in Figure 6.10 are replaced with - log/?; for all ; in the network, thus yielding the shortest-route network in Figure 6.11. Using TORA, nodes 1, 3, 5, and 7 define the shortest route in Figure 6.11 with a corresponding "length" of 1.1707 (= -log p17). Thus, the maximum probability of not being stopped is p17 = .0675. Example 6.3-3 (Three-Jug Puzzle) An 8-gallon jug is filled with fluid. Given two empty 5- and 3-gallon jugs, we want to divide the 8 gallons of fluid into two equal parts using the three jugs. No other measuring devices are allowed. What is the smallest number of pourings needed to achieve this result? You probably can guess the solution of this puzzle. Nevertheless, the solution process can be systematized by representing the problem as a shortest-route problem. A node is defined to represent the amount of fluid in the 8-, 5-, and 3-gallon jugs, respectively. This means that the network starts with node (8,0,0) and terminates with the desired solution node (4,4,0). A new node is generated from the current node by pouring fluid from one jug into another. Figure 6.12 shows different routes that lead from start node (8.0,0) to end node (4. 4,0).The arc between two successive nodes represents a single pouring, and hence can be assumed to have a length of 1 unit. The problem reduces to determining the shortest route between node (8,0,0) and node (4,4,0). The optimal solution, given by the bottom path in Figure 6.12, requires 7 pourings. 6.3 Shortest-Route Problem 223 FIGURE 6.12 Three-jug puzzle representation as a shortest-route model PROBLEM SET 6.3A 1. Reconstruct the equipment replacement model of Example 6.3-1, assuming that a car must be kept in service at least 2 years, with a maximum service life of 4 years.The planning horizon is from the start of 2001 to the end of 2005. The following table provides the necessary data. Replacement cost (S) for given years in operation Year acquired 2 3 4 2001 3800 4100 6800 2002 4000 4800 7000 2003 4200 5300 7200 2004 4800 5700 — 2005 5300 — — 2. Figure 6.13 provides the communication network between two stations, 1 and 7. The probability that a link in the network will operate without failure is shown on each arc. Messages are sent from station 1 to station 7, and the objective is to determine the route that will maximize the probability of a successful transmission. Formulate the situation as a shortest-route model, and solve withTORA. 3. An old-fashioned electric toaster has two spring-loaded base-hinged doors. The two doors open outward in opposite directions away from the heating element. A slice of bread is toasted one side at a time by pushing open one of the doors with one hand and placing the slice with the other hand. After one side is toasted, the slice is turned over to get the other side toasted. It is desired to determine the sequence of operations (placing, toasting, turning, and removing) needed to toast three slices of bread in the shortest possible 224 Chapter 6 Network Models FIGURE 6.13 Network for Problem 2, Set 6.3a time. Formulate the problem as a shortest-route model using the following elemental times for the different operations: Operation Time (seconds) Place one slice in either side 3 Toast one side 30 Turn slice already in toaster 1 Remove slice from either side 3 4. Production Planning. DirectCo sells an item whose demand over the next 4 months is 100,140,210, and 180 units, respectively. The company can stock just enough supply to meet each month's demand, or it can overstock to meet the demand for two or more successive and consecutive months. In the latter case, a holding cost of $1.20 is charged per overstocked unit per month. DirectCo estimates the unit purchase prices for the next 4 months to be $15, $12, $10, and $14. respectively. A setup cost of $200 is incurred each time a purchase order is placed. The company wants to develop a purchasing plan that will minimize the total costs of ordering, purchasing, and holding the item in stock. Formulate the problem as a shortest-route model, and use TORA to find the optimum solution. 5. Knapsack Problem. A hiker has a 5-ft3 backpack and needs to decide on the most valuable items to take on the hiking trip. There are three items from which to choose.Their volumes are 2,3, and 4 ft3, and the hiker estimates their associated values on a scale from 0 to 100 as 30,50, and 70, respectively. Express the problem as a longest-route network, and find the optimal solution. (Hint: A node in the network may be defined as [i, v], where i is the item number considered for packing, and v is the volume remaining immediately before the decision is made on i.) 6.3.2 Shortest-Route Algorithms This section presents two algorithms for solving both cyclic (i.e., containing loops) and acyclic networks: 1. Dijkstra's algorithm 2. Floyd's algorithm 6.3 Shortest-Route Problem 225 Dijkstra's algorithm is designed to determine the shortest routes between the source node and every other node in the network. Floyd's algorithm is general because it allows the determination of the shortest route between any two nodes in the network. Dijkstra's Algorithm. Let m, be the shortest distance from source node 1 to node i, and define dy 0) as the length of arc (i, j). Then the algorithm defines the label for an immediately succeeding node / as [Uj,i] = [u, + d,j,i], dy ^ 0 The label for the starting node is [0, —], indicating that the node has no predecessor. Node labels in Dijkstra's algorithm are of two types: temporary and permanent. A temporary label is modified if a shorter route to a node can be found. At the point when no better routes can be found, the status of the temporary label is changed to permanent. Step 0. Label the source node (node 1) with the permanent label [0,—]. Set i = 1. Step i. (a) Compute the temporary labels [it, + dip i] for each node / that can be reached from node i, provided j is not permanently labeled. If node; is already labeled with [up k] through another node k and if m, + (/„■ < m„ replace [ui, k] with [w, + dy, i]. (b) If all the nodes have permanent labels, stop. Otherwise, select the label [un s] having the shortest distance (=«,.) among all the temporary labels (break ties arbitrarily). Set i = r and repeat step i. Example 6.3-4 The network in Figure 6.14 gives the routes and their lengths in miles between city 1 (node 1) and four other cities (nodes 2 to 5). Determine the shortest routes between city 1 and each of the remaining four cities. Iteration 0. Assign the permanent label [0,—] to node 1. Iteration 1. Nodes 2 and 3 can be reached from (the last permanently labeled) node l.Thus, the list of labeled nodes (temporary and permanent) becomes Node Label Status 1 [0-1 Permanent 2 [0 + 100, 1] = [100. 11 Temporary 3 [0 + 30, 1] = [30. 1] Temporary FIGURE 6.14 Network example for Dijkstra's shortest-route algorithm 226 Chapter 6 Network Models For the two temporary labels [100,1] and [30.1], node 3 yields the smaller distance (u3 = 30). Thus, the status of node 3 is changed to permanent. Iteration 2. Nodes 4 and 5 can be reached from node 3, and the list of labeled nodes becomes Node Label Status 1 [0-] Permanent 2 [100,1] Temporary 3 [30,1] Permanent 4 [30 + 10, 3] = [40, 3] Temporary 5 [30 + 60, 3] = [90, 3] Temporary The status of the temporary label [40,3] at node 4 is changed to permanent (m4 = 40). Iteration 3. Nodes 2 and 5 can be reached from node 4. Thus, the list of labeled nodes is updated as Node Label Status 1 [0,-1 Permanent 2 [40 + 15, 4] = [55, 4] Temporary 3 [30,1] Permanent 4 [40,3] Permanent 5 [90,3] or [40 + 50, 4] = [90, 4] Temporal"}' Node 2's temporary label [100,1] in iteration 2 is changed to [55,4] in iteration 3 to indicate that a shorter route has been found through node 4. Also, in iteration 3, node 5 has two alternative labels with the same distance u5 = 90. The list for iteration 3 shows that the label for node 2 is now permanent. Iteration 4. Only node 3 can be reached from node 2. However, node 3 has a permanent label and cannot be relabeled. The new list of labels remains the same as in iteration 3 except that the label at node 2 is now permanent. This leaves node 5 as the only temporary label. Because node 5 docs not lead to other nodes, its status is converted to permanent, and the process ends. The computations of the algorithm can be carried out more easily on the network as Figure 6.15 demonstrates. The shortest route between nodes 1 and any other node in the network is determined by starting at the desired destination node and backtracking through the nodes using the information given by the permanent labels. For example, the following sequence determines the shortest route from node 1 to node 2: (2) -> [55.4] -> (4) -> [40,3] -> (3) [30,1] -> (1) Thus, the desired route isl—»3—»4—>2 with a total length of 55 miles. 6.3 Shortest-Route Problem 227 TORA can be used to generate Dijkstra's iterations. From the solve/modify menu, select Solve problem Iterations Dijkstra's algorithm. Figure 6.16 provides TORA's iterations output for Example 6.3-4 (file ch6ToraDijkstraEx6-3-4.txt). FIGURE 6.16 TORA Dijkstra iterations for Example 6.3-4 228 Chapter 6 Network Models PROBLEM SET 6.3B 1. The network in Figure 6.17 gives the distances in miles between pairs of cities 1,2,..., and 8. Use Dijkstra's algorithm to find the shortest route between the following cities: (a) Cities land 8 (b) Cities land 6 (c) Cities 4 and 8 (d) Cities 2 and 6 FIGURE 6.17 Network for Problem t, Set 6.3b 2. Use Dijkstra's algorithm to find the shortest route between node 1 and every other node in the network of Figure 6.18. FIGURE 6.18 6 Network for Problem 2, Set 6.3b 3. Use Dijkstra's algorithm to determine the optimal solution of each of the following problems: (a) Problem 1, Set 6.3a (b) Problem 2, Set 6.3a (c) Problem 4, Set 6.3a Floyd's Algorithm. Floyd's algorithm is more general than Dijkstra's because it determines the shortest route between any two nodes in the network. The algorithm represents an n-node network as a square matrix with n rows and n columns. Entry (/,/) of the matrix gives the distance dtj from node i to node j, which is finite if i is linked directly to;, and infinite otherwise. 6.3 Shortest-Route Problem 229 FIGURE 6.19 Floyd's triple operation The idea of Floyd's algorithm is straightforward. Given three nodes i, j, and k in Figure 6.19 with the connecting distances shown on the three arcs, it is shorter to reach k from i passing through j if d,j + djk < dik In this case, it is optimal to replace the direct route from I —> k with the indirect route i—tj—tk. This triple operation exchange is applied systematically to the network using the following steps: Step 0. Define the starting distance matrix D0 and node sequence matrix S0 as given below. The diagonal elements are marked with (—) to indicates that they are blocked. Set A: = 1. 1 2 ... /' ... n — dij dt„ da — dy da d„ din d„2 dnj — 1 2 ... ; ... n — 2 ; n 1 — / n 1 2 i n 1 2 i — General Step k. Define row k and column k as pivot row and pivot column. Apply the triple operation to each element d,j in Dk-V for all i and/. If the condition dik + dkj < dy, (i ^ k, j ¥= k, and i ¥= j) is satisfied, make the following changes: (a) Create Dk by replacing du in Dk _, with dik + dkj. (b) Create Sk by replacing s% in Sk_t with k. Set k = k + 1, and repeat step k. 230 Chapter 6 Network Models Pivot Column column Column j k q Rowi Pivot row k FIGURE 6.20 RowP Implementation of triple operation in matrix form Step k of the algorithm can be explained by representing Dk^1 as shown in Figure 6.20. Here, row k and column k define the current pivot row and column. Row i represents any of the rows 1,2,..., and k — 1, and row p represents any of the rows k + 1, k + 2, ..., and n. Similarly, column ; represents any of the columns 1, 2, ..., and k — 1, and column q represents any of the columns k + 1, k + 2, and n. With the triple operation, if the sum of the elements on the pivot row and the pivot column (shown by squares) is smaller than the associated intersection element (shown by a circle), then it is optimal to replace the intersection distance by the sum of the pivot distances. After n steps, we can determine the shortest route between nodes i and ;' from the matrices D„ and S„ using the following rules: 1. From £),„ d„ gives the shortest distance between nodes i and /. 2. From S„, determine the intermediate node k = stj that yields the route i -> If s,k = k and sk) = j, stop; all the intermediate nodes of the route have been found. Otherwise, repeat the procedure between nodes i and k, and between nodes k and/. Example 6.3-5 For the network in Figure 6.21, find the shortest routes between every two nodes. The distances (in miles) are given on the arcs. Arc (3,5) is directional so that no traffic is allowed from node 5 to node 3. All the other arcs allow traffic in both directions. FIGURE 6.21 Network for Example 6.3-5 6.3 Shortest-Route Problem 231 Iteration 0. The matrices D0 and SQ give the initial representation of the network. D0 is symmetrical except that d53 = cc because no traffic is allowed from node 5 to node 3. D0 s0 1 2 3 4 5 1 2 3 4 5 1 3 10 oc oo 1 _ 2 3 4 5 2 3 — oo 5 oo 2 1 _ 4 5 3 10 op — 6 15 3 1 4 5 4 oo 5 6 — 4 4 1 7 3 — 5 5 oo oc 00 4 — 5 1 2 3 4 — Iteration 1. Set k = 1. The pivot row and column are shown by the lightly shaded first row and first column in the Z)()-matrix. The darker cells, d23 and di,2 are the only ones that can be improved by the triple operation. Thus, D and Si are obtained from Z)0 and S0 in the following manner: 1. Replace d2j with d2l + du = 3 + 10 = 13andsetj23 = 1. 2. Replace d?2 with d31 + dn = 10 + 3 = 13 and set s32 = 1. These changes are shown in bold in matrices D, and Sp 0i S, 1 2 3 4 5 1 2 3 4 5 1 _ 3 10 r OC' 1 _ 2 3 .4, 5 2 3 — 13 5 OC' 2 1 — 1 4 5 3 10 13 — 6 15 3 1 1 — 4 5 4 5 6 — 4 4 1 2 3 — 5 5 oo 00 oc 4 — 5 1 2 3 4 — Iteration 2. Set k = 2, as shown by the lightly shaded row and column in D,.The triple operation is applied to the darker cells in D{ and Sj.The resulting changes are shown in bold in D2 and S2. D, 52 1 2 3 4 5 1 2 3 4 5 1 — 3 10 8 '6c 1 _ 2 3 2 5'~' 2 3 — 13 5 DC 2 1 — 1 4 5 3 10 13 — 6 15 3 1 1 — 4 5 4 8 5 — 4 4 2 2 3 — 5 5 OO 00 CO 4 5 1 2 3 4 — 232 Chapter 6 Network Models Iteration 3. Set k = 3, as shown by the shaded row and column in D2- The new matrices are given by D} and S3. D3 S3 1 2 3 4 5 1 2 3 4 5 1 _ 3 10 8 25 1 — 2 3 2 3 2 3 — 13 5 ■■■ ■ 28 2 1 1 4 3 3 10 — 6 15 3 1 1 — 4 5 4 8 5 6 — 4 4 2 3 — 5 5 oe 8-K 4 — 5 l 2 3 4 — Iteration 4. Set k = 4, as shown by the lightly-shaded row and column in D3. The new matrices are given by D4 and S4. D4 S4 1 2 3 4 5 1 2 3 4 5 1 _ 3 10 8 12 1 _ 2 3 2 4 2 3 — 11 5 9 2 1 — 4 4 4 3 10 11 — 6 10 3 1 4 — 4 4 4 8 5 6 — 4 4 2 2 3 — 5 5 12 9 10 4 — 5 4 4 4 4 — Iteration 5. Set k = 5, as shown by the shaded row and column in D4. No further improvements are possible in this iteration. Hence, D5 and 55 are the same as D4 and S4. The final matrices D5 and 55 contain all the information needed to determine the shortest route between any two nodes in the network. For example, consider determining the shortest route from node 1 to node 5. First, the associated shortest distance is given by d15 = 12 miles. To determine the associated route, recall that a segment represents a direct link only if s« = /. Otherwise, i and / are linked through at least one other intermediate node. Because s15 = 4, the route is initially given as 1 —> 4 —> 5. Now, because s14 = 2 ^ 4, the segment (1,4) is not a direct link, and 1 —» 4 must be replaced with 1 —> 2 —> 4. and the route 1 —> 4 —» 5 now becomes 1 —> 2 —> 4 —> 5. Next, because s12 = 2, s24 = 4, and .V45 = 5, the route 1 —> 2 —> 4 —> 5 needs no further "dissecting" and the process ends. As in Dijkstra's algorithm, TORA can be used to generate Floyd's iterations. From the SOLVR/MODIFY menu, select Solve problem => Iterations => Floyd'd algoH thn. Figure 6.22 illustrates TORA's output for Floyd's Example 6.3-5 (file ch6ToraFloydEx6-3-5.txt). 6.3 Shortest-Route Problem 233 FIGURE 6.22 TORA Floyd iterations for Example 6.3-5 PROBLEM SET 6.3C 1. In Example 6.3-5, use Floyd's algorithm to determine the shortest routes between each of the following pairs of nodes: (a) From node 5 to node 1 (b) From node 3 to node 5 (c) From node 5 to node 3 (d) From node 5 to node 2 2. Apply Floyd's algorithm to the network in Figure 6.23. Arcs (7,6) and (6,4) are unidirectional, and all the distances are in miles. Determine the shortest route between the following pairs of nodes: (a) From node 1 to node 7 (b) From node 7 to node 1 (c) From node 6 to node 7 3. The Tell-All mobile phone company services six geographical areas. The satellite distances (in miles) among the six areas are given in Figure 6.24. Tell-All needs to determine the most efficient message routes that should be established between each two areas in the network. 4. Six kids—Joe, Kay, Jim, Bob, Rae, and Kim—play a variation of the game of hide and seek. The hiding place of a child is known only to a select few of the other children. A 234 Chapter 6 Network Models Network for Problem 2, Set 6.3c FIGURE 6.23 FIGURE 6.24 Network for Problem 3, Set 6.3c W v—J child is then paired with another with the objective of finding his or her hiding place. This may be achieved through a chain of other kids who eventually will lead to discovering where the designated child is hiding. For example, suppose that Joe needs to find Kim and that Joe knows where Jim is hiding, who in turn knows where Kim is. Thus, Joe can find Kim by first finding Jim, who in turn will lead Joe to Kim.The following list provides the whereabouts of the children: Joe knows the hiding places of Bob and Kim. Kay knows the hiding places of Bob, Jim, and Rae. Jim and Bob know the hiding place of Kay only. Rae knows where Kim is hiding. Kim knows where Joe and Bob are hiding. Devise a plan for each child to find every other child through the smallest number of contacts. What is the largest number of contacts? 6.3.3 Linear Programming Formulation of the Shortest-Route Problem This section provides two LP formulations for the shortest-route problem. The formulations are general in the sense that they can be used to find the shortest route between any two nodes in the network. In this regard, the LP formulations are equivalent to Floyd's algorithm. Suppose that the shortest-route network includes n nodes and that we desire to determine the shortest route between any two nodes s and t in the network. Formulation 1: This formulation assumes that an external one unit of flow enters the network at node s and leaves it at node t, where s and t are the two target nodes between which we seek to determine the shortest route. 6.3 Shortest-Route Problem 235 Define x(j = amount of flow in arc (i, J), for all feasible i and /' Cij = length of arc (i, y), for all feasible i and j Because only one unit of flow can be in any arc at any one time, the variable xVj must assume binary values (0 or 1) only. Thus, the objective function of the linear program becomes Minimize z = 2 caxij all defined arcs(i. f) There is one constraint that represents the conservation of flow at each node—that is, for any node j, Total input flow = Total output flow Formulation 2: The second formulation is actually the dual problem of the LP in Formulation 1. Because the number of constraints in Formulation 1 equals the number of nodes, the dual problem will have as many variables as the number of nodes in the network. Also, all the dual variables must be unrestricted because all the constraints in Formulation 1 are equations. Let y, = dual constraint associated with node y Given s and t are the start and terminal nodes of the network, the dual problem is defined as Maximize z = y, - ys subject to yf - y, s cy, for all feasible /' and j all y-, and y; unrestricted in sign Example 6.3-6 Consider the shortest route network of Example 6.3-4. Suppose that we want to determine the shortest route from node 1 to node 2; that is, s = 1 and f = 2. Figure 6.25 shows how the unit of flow enters at node 1 and leaves at node 2. FIGURE 6.25 Insertion of unit flow to determine shortest route between node s = 1 and node ( = 2 236 Chapter 6 Network Models Using Formulation 1, the associated LP is listed below. *23 X35 jc42 *45 Minimize z = too 30 20 10 60 15 50 Node 1 -1 -1 = -1 Node 2 1 -1 1 = 1 Node 3 1 i -1 -1 = 0 Node 4 1 -1 -1 = 0 Node 5 1 1 = 0 The constraints represent flow conservation at each node. For example, at node 2, "input flow = output flow" yields xn + xn = 1 + x23. Note that one of the constraints is always redundant. For example, adding the last four constraints simultaneously yields xn + xl3 = 1, which is the same as constraint 1. The optimal solution (obtained by TORA)2 is z = 55, x13 = 1, x34 = 1, x42 = 1 This solution gives the shortest route from node 1 to node 2asl-4-3—»4—»2 and the associated distance is z = 55 (miles). To use Formulation 2, the dual problem associated with the LP above is given as Maximize z = v2 — y\ subject to y2 - >'i < 100 (Route 1-2) - >'i < 30 (Route 1-3) V2 - yi < 20 (Route 2-3) - y3 < 10 (Route 3-4) y$ - J3 < 60 (Route 3-5) yi - y4 < 15 (Route 4-2) y5 < 50 (Route 4-5) yi, yi, ■ y5 unrestricted Although the dual problem given above is a pure mathematical definition derived from the primal problem, we actually can interpret the problem in a logical manner. Define y, = Distance to node i :TORA does not accept a negative right-hand side. You can get around this inconvenience by selecting the redundant constraint as the one having the negative right-hand side, then make it redundant by changing = to £ and setting the right-hand side to a very large value. Another trick is to add a new variable whose upper and lower bounds equal 1, effectively forcing it to equal 1 in any solution. The constraint coefficients of the new variable equal those of the current right-hand side, but with opposite sign. The right-hand side of the "new" problem must be changed to zero for all the constraints (see file ch6ToraLpShortRout; Ex6-3-6.txt). 6.3 Shortest-Route Problem 237 With this definition, the shortest distance from the start node 1 to the terminal node 2 is determined by maximizing y2 - y\. The constraint associated with route (i, j) says that the distance from node i to node cannot exceed the direct length of that route. It can be less if node / can be reached from node i through other nodes that provide a shorter path. For example, the distance from node 1 to node 2 is at most 100. With the definition of y, as the distance to node i, we can assume that all the variables are non-negative (instead of being unrestricted). We can also assume that y, = 0 as the distance to node 1. Based on the discussion above, and assuming that all the variables are nonnega-tive, the optimum solution is given as z = 55, yx = 0, y2 = 55, y3 = 30, y4 = 40, y5 = 0 The value of z = 55 gives the shortest distance from node 1 to node 2, which also equals y2 - y± = 55 - 0 = 55. The determination of the route itself from this solution is somewhat tricky. We note that the solution satisfies in equation form the constraints of routes 1 -3, 3-4, and 4-2 because their slacks equal zero—that is, y3 - yt = 30, y4 - y3 = 10, and y2 — y4 = 15. This result identifies the shortest route as 1 —> 3 —> 4 —> 2. Another way for identifying the constraints that are satisfied in equation form is to consult the dual solution of the LP of Formulation 2. Any constraint that has a nonzero dual value must be satisfied in equation form (see Section 4.2.4). The following table pairs the routes (constraints) with their associated dual values. Route (constraint) 1-2 1-3 2-3 3-4 3-5 4-2 4-5 Associated dual value 0 1 0 1 0 1 0 PROBLEM SET 6.3D 1. In Example 6.3-6, use the two LP formulations to determine the shortest routes between the following pairs of nodes: (a) Node 1 to node 5. (b) Node 2 to node 5. 6.3.4 Excel Spreadsheet Solution of the Shortest-Route Problem The Excel spreadsheet developed for the general transportation model (Section 5.3.3) can be modified readily to find the shortest route between two nodes. The spreadsheet is based on Formulation 1, Section 6.3.3, and is designed for problems with a maximum of 10 nodes. Figure 6.26 shows the application of the spreadsheet to Example 6.3-4 (file ch6SolverShortestRoutc.xls). The distance matrix resides in cells B6:K15.3 An infinite distance (= 9999, or any relatively large value) is entered for nonexisting arcs. Because we are seeking the shortest route between nodes 1 and 2, the supply amount for node 1 and the demand amount for node 2 is 1 unit. A zero amount is entered for the remaining supply and demand entries. -'In Figure 6.26, rows 11 through 15 and column K are hidden to conserve space. 238 Chapter 6 Network Models FIGURE 6.26 Excel Solver solution of the shortest route between nodes 1 and 2 in Example 6.3-4 ;-5Jdi6Sp|w:r5horCestKoii.. ; ^______ 'C]EE_J 5« - ärgtl: Ceti Eqadi Tu: ' r M,, Syft «et tothc-Coostw 3 $F*19:$Ft2 Once the unit cost and supply/demand data are entered, the remainder of the spreadsheet (intermediate calculations and optimum solution sections) is generated automatically. Solver parameters must correspond to the input data of the problem as shown in highlighted columns B, C, F, and G. Column B specifies the changing cells (arcs flow) of the problem (cells B20:B39). Column C specifies the capacities of the arcs of the network (cells C20:C39). Tn the shortest-route model, these capacities do not play a role in the computations and hence are infinite (=999999). The constraints of the model represent the balance equation for each node. Cells F19:F23 define the left-hand side and cells G19:G23 represent the right-hand side of the flow equations. As explained in Section 5.3.3, SUMIF is used to generate the proper net flow in each node using the information in columns I and J. These calculations are automated by the 6.4 Maximal Flow Model 239 spreadsheet. Thus, all you need to do after entering the input data is to update Changing Cells and Constraints specifications of Solver to match the input data. The Target Cell remains the same for all input data. In Example 6.3-4, we have Changing Cells: 320:B39 Constraints: F19:F23=G19:G23 The output in Figure 6.26 yields the solution (N1-N3 = 1, N3-N4 = 1, N4-N2 = 1) with a total distance of 55 miles. This means that the optimal route is 1 _> 3 4 2, PROBLEM SET 6.3E 1. Modify spreadsheet ch6SolverShortestRoute.xls (applied to Example 6.3-4) to find the shortest route between the following pairs of nodes: (a) Node f to node 5 (b) Node 4 to node 3 2. Adapt spreadsheet ch6SolverShortestRoute.xls for Problem 2, Set 6.3a, to find the shortest routes between node 4 and node 7. 6.4 MAXIMAL FLOW MODEL Consider a network of pipelines that transports crude oil from oil wells to refineries. Intermediate booster and pumping stations arc installed at appropriate design distances to move the crude in the network. Each pipe segment has a finite maximum rate of crude flow (or capacity). A pipe segment may be unidirectional or bidirectional, depending on its design. A unidirectional segment has a finite capacity in one direction and a zero capacity in the opposite direction. Figure 6.27 demonstrates a typical pipeline network. How can we determine the maximum capacity of the network between the wells and the refineries? The solution of the proposed problem requires converting the network into one with a single source and a single sink. This requirement can be accomplished by using unidirectional infinite capacity arcs as shown by dashed arcs in Figure 6.27. 240 Chapter 6 Network Models Given arc (i, j) with i < j, we use the notation (C^, C„) to represent the flow capacities in the two directions i —> j and ; —> i, respectively. To eliminate ambiguity, we place Qj on the arc next to node i with C;, placed next to node j, as shown in Figure 6.28. FIGURE 6.28 Arc flows Ci, from i —> j and C,7 from / —> 6.4.1 Enumeration of Cuts A cut defines a set of arcs which when deleted from the network will cause a complete disruption of flow between the source and sink nodes. The cut capacity equals the sum of the capacities of the associated arcs. Among all possible cuts in the network, the cut with the smallest capacity gives the maximum flow in the network. Example 6.4-1 Consider the network in Figure 6.29. The bidirectional capacities are shown on the respective arcs using the convention in Figure 6.28. For example, for arc (3,4), the flow limit is 10 units from 3 to 4 and 5 units from 4 to 3. Figure 6.29 illustrates three cuts whose capacities are computed in the following table. Cut Associated arcs Capacity 1 (1,2), (1,3), (1,4) 20 + 3Ü + 10 = 60 2 (1,3), (1,4), (2,3), (2,5) 30 + 10 + 40 + 30 = 110 3 (2,5), (3,5),(4,5) 30 + 20 + 20 = 70 6.4 Maximal Flow Model 241 We cannot tell what the maximal flow in the network is unless we exhaustively enumerate all possible cuts. The only piece of information we can get from the partial enumeration of three cuts is that the maximum flow in the network cannot exceed 60 units. Unfortunately, exhaustive enumeration of all cuts is not a simple task, thus making it necessary to develop the efficient algorithm in Section 6.4.2. PROBLEM SET 6.4A 1. For the network in Figure 6.29, determine two additional cuts, and find their capacities. 6.4.2 Maximal Flow Algorithm The maximal flow algorithm is based on finding breakthrough paths with net positive flow between the source and sink nodes. Each path commits part or all the capacities of its arcs to the total flow in the network. Consider arc (ij) with (initial) capacities (C,y, Cj7). As portions of these capacities are committed to the flow in the arc, the residuals (or remaining capacities) of the arc are updated. The network with the updated residuals is referred to as the residue network. We use the notation (c,y, c„) to represent these residuals. For a node j that receives flow from node i, we define a label \ap i], where a, is the flow from node i to node ;. The steps of the algorithm are summarized as follows. Step 1. For all arcs (i, j), set the residual capacity equal to the initial capacity—that is (c,,, c/7) = (Cip Cy,). Let a{ = oo and label source node 1 with [oo, - ]. Set i = 1, and go to step 2. Step 2. Determine 5, as the set of unlabeled nodes that can be reached directly from node i by arcs with positive residuals (that is, c,( > 0 for alle S,). If Sj ¥= 0, go to step 3. Otherwise, go to step 4. Step 3. Determine k e 5, such that cik = max {c;/} Set ak = cik and label node k with [ak, i]. If k = n, the sink node has been labeled, and a breakthrough path is found, go to step 5. Otherwise, set i = k, and go to step 2. Step 4. (Backtracking). If i = 1, no further breakthroughs arc possible; go to step 6. Otherwise, let r be the node that has been labeled immediately before the current node i and remove i from the set of nodes that are adjacent to r. Set i - r, and go to step 2. Step 5. (Determination of Residue Network). LetNp = (1, kY, k2,..., n) define the nodes of the pth breakthrough path from source node 1 to sink node n. Then the maximum flow along the path is computed as fp = minjrt,, ak„ a^,,.., a,,} The residual capacity of each arc along the breakthrough path is decreased by fp in the direction of the flow and increased by fp in the reverse 242 Chapter 6 Network Models direction—that is, for nodes /' andj on the path, the residual flow is changed from the current (c7/, c,,) to (a) (qj - fp, Cji + fp) if the flow is from (' to j (b) (cjj + fp, Cfl - fp) if the flow is from;' to i Reinstate any nodes that were removed in step 4, Set i = 1, and return to step 2 to attempt a new breakthrough path. Step 6. (Solution) (a) Given that m breakthrough paths have been determined, the maximal flow in the network is F = f]+f2+ ... +fm (b) Given that the initial and final residuals of arc (/, /) are given by (C,y, C,,) and (c,y, c/;), respectively, the optimal flow in arc (i, j) is computed as follows: Let (a, (J) = (C,:/ - c,j, C]t - c;i). If a > 0, the optimal flow from i to; is a. Otherwise, if p > 0, the optimal flow from;' to i is p. (It is impossible to have both a and (3 positive.) The backtracking process of step 4 is invoked when the algorithm becomes inadvertently "dead-ended" at an intermediate node before a breakthrough can be realized. The flow adjustment in step 5 can be explained via the simple flow network in Figure 6.30. Network (a) gives the first breakthrough path Nx = {1, 2, 3, 4} with its maximum flow fv = 5. Thus, the residuals of each of arcs (1,2), (2,3), and (3,4) are changed from (5,0) to (0,5), per step 5. Network (b) now gives the second breakthrough pathA'2 = {1, 3, 2, 4} with f2 = 5. After making the necessary flow adjustments, we get network (c), where no further breakthroughs are possible. What happened in the transition from (b) to (c) is nothing but a cancellation of a previously committed flow in the direction 2 —>• 3. The algorithm is able to "remember" that a flow from 2 to 3 has been committed previously only because we have increased the capacity in the reverse direction from 0 to 5 (per step 5). 6.4 Maximal Flow Model 243 Example 6.4-2 Determine the maximal flow in the network of Example 6.4-1 (Figure 6.29). Figure 6.31 provides a graphical summary of the iterations of the algorithm. You will find it helpful to compare the description of the iterations with the graphical summary. (e)/s = 10 FIGURE 6.31 Iterations of the maximum flow algorithm of Example 6.4-2 (f) No breakthrough 244 Chapter 6 Network Models Iteration 1. Set the initial residuals {ctj, cy7) equal to the initial capacities (Q, C(I). Step 1. Set 8j = oc and label node 1 with [oo, —]. Set 1 = 1. Step 2. Si = {2, 3, 4}(^ 0). Step 3. k = 3 because c13 = max{c12, c13, c14} = max {20, 30, 10} = 30. Set a3 = c13 = 30, and label node 3 with [30,1], Set i = 3, and repeat step 2. Step 2. S3 = (4, 5). Step 3. k = 5 and a5 = c35 = max {10, 20} = 20. Label node 5 with [20,3]. Breakthrough is achieved. Go to step 5. Step 5. Breakthrough path is determined from the labels starting at node 5 and ending at node 1—that is, (5) -> [20, 3] -> (3) -> [30, 1] -> (1). Thus, AT, ={1,3,5} and/j = min{flb a3, a5} = { c>o , 30, 20} = 20. The residual capacities along path Ni are (c13, c31) = (30 - 20, 0 + 20) = (10, 20) (c35, c53) = (20 - 20, 0 + 20) = (0, 20) Iteration 2. Step 1. Set A] = oo, and label node 1 with [oo, —]. Set i = 1. Step 2. SL = {2, 3, 4}. Step 3. k = 2 and a2 = c12 = max {20, 10, 10} = 20. Set j = 2, and repeat step 2. Step 2. 52 = {3, 5}. Step 3. k = 3 and a3 = c23 = 40. Label node 3 with [40,2]. Set i = 3, and repeat step 2. Step 2. 53 = {4} (note that c35 = 0—hence, node 5 cannot be included in S3). Step 3. k = 4 and a4 = c34 = 10. Label node 4 with [10,3]. Set i = 4, and repeat step 2. Step 2. 54 = {5} (note that nodes 1 and 3 are already labeled—hence, they cannot be included in S4). Step 3. k = 5 and a5 = c45 = 20. Label node 5 with [20,4]. Breakthrough has been achieved. Go to step 5. Step 5. JV2 = {1, 2, 3, 4, 5} and f2 = min {oo, 20, 40, 10, 20} = 10. The residuals along the path of N2 are (^12, c2i) (C23, C32) (c34, C43) (c45, c54) Iteration 3. Step 1. Set= 00 and label node 1 with [00, —]. Set i = 1. Step 2. Si = {2, 3, 4}. Step 3. k = 2 and a2 = c]2 = max{10, 10, 10} = 10 (though ties are broken arbitrarily, TORA always selects the tied node with the smallest index; we will = (20 - 10, 0 + 10) = (10, 10) = (40 - 10, 0 + 10) = (30. 10) = (10 - 10, 5 + 10) = (0, 15) = (20 - 10. 0 + 10) = (10, 10) 6.4 Maximal Flow Model 245 use this convention throughout the example). Label node 2 with [10,1]. Set i = 2, and repeat step 2. Step 2. S2 = {3, 5}. Step 3. k = 3 and a3 = cv? = 30. Label node 3 with [30,2]. Set i = 3, and repeat step 2. Step 2. S3 = 0 (because c34 = c35 = 0). Go to step 4 to backtrack. Step 4. The label [30,2] at node 3 gives the immediately preceding node r = 2. Remove node 3 from further consideration in this iteration by crossing it out. Set i = r = 2, and repeat step 2. Step 2. S2 = {5} (note that node 3 has been removed in the backtracking step). Step 3. k = 5 and a5 = c2S = 30. Label node 5 with [30,2]. Breakthrough has been achieved; go to step 5. Step 5. JV3 = {1, 2, 5}andc5 = min{oo, 10, 30} = 10. The residuals along the path of Ar3 are (c12, c21) = (10 - 10, 10 + 10) = (0, 20) (fts. c52) = (30 - 10, 0 + 10) = (20, 10) Iteration 4. This iteration yields N4 = {1, 3, 2, 5} with /4 = 10 (verify!). Iteration 5. This iteration yields N5 = {1, 4, 5} with /, = 10 (verify!). Iteration 6. All the arcs out of node 1 have zero residuals. Hence, no further breakthroughs are possible. We turn to step 6 to determine the solution. Step6. Maximal flow in the network is F = fx + f2 + ... + f5 = 20 + 10 + 10 + 10 + 10 = 60 units. The flow in the different arcs is computed by subtracting the last residuals (cip c„) in iterations 6 from the initial capacities (C„, CA as the following table shows. Arc (C„, C7) - (c,y, c,;)6 Flow amount Direction (1.2) (20, 0) - (0, 20) = (20, -20) 20 1 ^2 (1.3) (30, 0) - (0, 30) = (30, -30) 30 1 ^3 (1.4) (10. 0) - (0. 10) =(10,-10) 10 l-*4 (2.3) (40, 0) - (40, 0) = (0, 0) 0 — (2.5) (30, 0) - (10, 20) = (20, -20) 20 2 5 (3.4) (10, 5) - (0, 15) =(10,-10) 10 3^4 (3.5) (20, 0) - (0, 20) = (20, -20) 20 3 -> 5 (4,5) (20, 0) - (0, 20) =(20,-20) 20 4-^5 You can use TORA to solve the maximum flow model in an automated mode or to produce the iterations outlined above. From the solvs/modify menu select solve Problem. After specifying the output format, go to output screen and select either Maximum Flows or iterations. Figure 6.32 illustrates the first two iterations of Example 6.4-2 (file ch6ToraMaxFlowEx6-4-2.txt). 246 Chapter 6 Network Models FIGURE 6.32 TORA's maximum flow iterations for Example 6.4-2 PROBLEM SET 6.4B 1. In Example 6.4-2, (a) Determine the surplus capacities for all the arcs. (b) Determine the amount of flow through nodes 2,3, and 4. (c) Can the network flow be increased by increasing the capacities in the directions 3-»5and4-»5? 2. Determine the maximal flow and the optimum flow in each arc for the network in Figure 6.33. 3. Three refineries send a gasoline product to two distribution terminals through a pipeline network. Any demand that cannot be satisfied through the network is acquired from other sources. The pipeline network is served by three pumping stations as shown in Figure 6.34. The product flows in the network in the direction shown by the arrows. The capacity of each pipe segment (shown directly on the arcs) is in million bbl per day. Determine the following: (a) The daily production at each refinery that matches the maximum capacity of the network. (b) The daily demand at each terminal that matches the maximum capacity of the network. (c) The daily capacity of each pump that matches the maximum capacity of the network. 6.4 Maximal Flow Model 247 FIGURE 6.33 Network for Problem 2, Set 6.4b 4. Suppose that the maximum daily capacity of pump 6 in the network of Figure 6.34 is limited to 60 million bbl per day. Remodel the network to include this restriction. Then determine the maximum capacity of the network. 5. Chicken feed is transported by trucks from three silos to four chicken farms. Some of the silos cannot ship directly to some of the farms. The capacities of the other routes are limited by the number of trucks available and the number of trips made daily. The following table shows the daily amounts of supply at the silos and demand at the farms (in thousands of pounds). The cell entries of the table specify the daily capacities of the associated routes. Farm 1 2 3 4 1 30 5 0 40 20 Silo 2 0 0 5 90 20 3 100 40 30 40 200 200 10 60 20 248 Chapter 6 Network Models (a) Determine the schedule that satisfies the most demand. (b) Will the proposed schedule satisfy all the demand at the farms? 6. In Problem 5, suppose that transshipping is allowed between silos 1 and 2 and silos 2 and 3. Suppose also that transshipping is allowed between farms 1 and 2,2 and 3, and 3 and 4. The maximum two-way daily capacity on the proposed transshipping routes is 50 (thousand) lb. What is the effect of transshipping on the unsatisfied demands at the farms? 7. A parent has five (teenage) children and five household chores to assign to them. Past experience has shown that forcing chores on a child is counterproductive. With this in mind, the children are asked to list their preferences among the five chores, as the following table shows: Child Preferred chore Rif 3,4, or 5 Mai 1 Ben lor 2 Kim 1,2, or 5 Ken 2 The parent's modest goal now is to finish as many chores as possible while abiding by the children's preferences. Determine the maximum number of chores that can be completed and the assignment of chores to children. 8. Four factories arc engaged in the production of four types of toys. The following table lists the toys that can be produced by each factory. Factory Toy productions mix 1 1,2,3 2 2.3 3 1,4 4 3,4 All toys require the same per unit labor and material. The daily capacities of the four factories are 250,180,300, and 100 toys, respectively. The daily demands for the four toys are 200,150,350, and 100 units, respectively. Determine the production schedules that will most satisfy the demands for the four toys. 9. The academic council at the U of A is seeking representation from among six students who are affiliated with four honor societies. The academic council representation includes three areas: mathematics, art, and engineering. At most two students in each area can be on the council. The following table shows the membership of the six students in the four honor societies: Society Affiliated students 1 1,2,3 2 1,3,5 3 3.4,5 4 1,2,4,6 The students who are skilled in the areas of mathematics, art, and engineering are shown in the following table: 6.4 Maximal Flow Model 249 Area Skilled students Mathematics 1,2,4 Art 3,4 Engineering 4,5,6 A student who is skilled in more than one area must be assigned exclusively to one area only. Can all four honor societies be represented on the council? 10. Maximal/Minimal Flow in Networks with Lower Bounds. The maximal flow algorithm given in this section assumes that all the arcs have zero lower bounds. In some models, the lower bounds may be strictly positive, and we may be interested in finding the maximal or minimal flow in the network (sec Comprehensive Problem 6-3). The presence of the lower bound poses difficulty because the network may not have a feasible flow at all.The objective of this exercise is to show that any maximal and minimal flow model with positive lower bounds can be solved using two steps. Step 1. Find an initial feasible solution for the network with positive lower bounds. Step 2. Using the feasible solution in step 1, find the maximal or minimal flow in the original network. (a) Show that an arc (/', /) with flow limited by /,; < < m,; can be represented equivalent^' by a sink with demand l;j at node i and a source with supply L at node ; with flow limited by ÖSt< u:j - (b) Show that finding a feasible solution for the original network is equivalent to finding the maximal flow xi} in the network after (1) modifying the bounds on Xn to 0 < Xjj Ujj - Ijj, (2) "lumping" all the resulting sources into one supersource with outgoing arc capacities lVp (3) "lumping" all the resulting sinks into one supersink with incoming arc capacities /,,, and (4) connecting the terminal node / to the source node j in the original network by a return infinite capacity arc. A feasible solution exists if the maximal flow in the new network equals the sum of the lower bounds in the original network. Apply the procedure to the following network and find a feasible flow solution: Arc ((,;') % ">,) (1.2) (5,20) (1,3) (0,15) (2,3) (4,10) (2,4) (3,15) (3.4) (0,20) (c) Use the feasible solution for the network in (b) together with the maximal flow algorithm to determine the minimal flow in the original network. (Hint: First compute the residue network given the initial feasible solution. Next, determine the maximum flow from the end node to the start node. This is equivalent to finding the maximum flow that should be canceled from the start node to the end node. Now, combining the feasible and maximal flow solutions yields the minimal flow in the original network.) (d) Use the feasible solution for the network in (b) together with the maximal flow model to determine the maximal flow in the original network. (Hint: As in part [c], start with the residue network. Next apply the breakthrough algorithm to the resulting residue network exactly as in the regular maximal flow model.) 250 Chapter 6 Network Models 6.4.3 Linear Programming Formulation of the Maximum Flow Model Define Xy as the amount of flow in arc (r,;') and let c,; be the capacity of the same arc. Assume that s and t are the start and terminal nodes between which we need to determine the maximum flow in the capacitated network. The constraints of the problem preserve the in-out flow at each node, with the exception of start and terminal nodes. The objective function maximizes either the total "out" flow from start node s or the total "in" flow to terminal node /. Example 6.4-3 In the maximum flow model of Figure 6.29 (Example 6.4-2), s = 1 and f = 5. The following table summarizes the associated LP with two different objective functions depending on whether we are maximizing the output from node 1 (=Zi) or the input to node 5 (=z2)- X\2 -^14 Xji X22 x34 -^43 *45 Maximize z, = 1 1 1 Maximize z2= 11 1 Node 2 1 -1 -1 Node 3 1 1 -1-11 Node 4 1 1 -1 -1 11 11 11 Capacity 20 30 10 40 30 10 20 5 20 The optimal solution using either objective function is xn = 20, x13 = 30, xl4 = 10, x25 = 20, x34 = 10, x35 = 20, x45 The associated maximum flow is Z\ = z2 — 60. = 20 PROBLEM SET 6.4C 1. Rework Problem 2, Set 6.4b using linear programming. 2. Rework Problem 5, Set 6.4b using linear programming. 6.4.4 Excel Spreadsheet Solution of the Maximum Flow Model The network-based Excel spreadsheet developed for the transportation model (Section 5.3.3) is modified to determine the maximum flow in a capacitated network. The spreadsheet is designed for problems with a maximum of 10 nodes. Figure 6.35 shows the application of the spreadsheet to Example 6.4-2 (file ch6SolverMa\ Flow.xls).The capacity flow matrix resides in cells B6:K15.4 A blank cell in the capacity matrix indicates that the associated arc has infinite capacity. A zero entry corresponds to a nonexisting flow arc. Otherwise, all the remaining arcs must have finite capacities. Once the flow capacity data have been entered, the remainder of the spreadsheet (intermediate calculations and optimum solution sections) is created automatically. All 4In Figure 6.35, rows 11 through 16 and column K are hidden to conserve space. 6.4 Maximal Flow Model 251 1 Maximum Flow Model with SolvEr i ■ Ja, {if nodes jr Ü 5 C m A/2 W3 ' m /*/< w». o 20 30 18 8 ? m b ''1 4M it.~lzti 30 ' Hi ~Y~ II ' C i ii , 20 i 1 " 8 8 c (i 70 : "7 IB 0' 6 (i "i 8 "1 1 ft -——_ ■7 ■■ Total cost = 60 Name Node > From : JnitFlov»! :- f-oti - To Flow ups: I', 1 63 1 : 1 33 Ml ■ N2 20 1: 3; if - N1 - 30 4: .....it __ ' N1"- N4 10 it N4 S t3 ""jr~ .. 'nT-'Sb II 2: 11 .."ZS N2-M" ' 0 2i 3j ol N2-N3 0 42 2; Ö "N2-N4 " 9 - ........fj" N2-N5.' 20 .......0 0 2: dl i 3 iö-kT" 0 3' 4 0| ! • M- - fji 10 t: 3; 5; 0: i -ll N3"-~N5 20 2C h [jj 112 N4 - BT 0 21 rji ! a N4 N2 0 4] 3j 0! N4 - N3 0 . .. '"" 0] N4 • I* 20 20 5! 11 Dl N5 - Nl 0 .2 1] 2; PJ ;37 N5 ■ F2 ' 0 X .. jrjj 1 3: N5 - K3 0 4; ~.....of N5-N4 a '_ ; i55s:0:$Bli:' ; Sybictf tri hb Ccr-sb arts' ' H$F$20:«22-»äJ2O:»6$2 -^-1 fegt All J kniete [ FIGURE 6.35 Excel Solver solution of the maximum flow model of Example 6.4-2 that is needed now is to update Solver parameters to match the input data. Column B specifies the changing cells (arcs flow) of the problem. The range for Changing Cells must encompass all the arcs specified in column A (make sure that you give each node a name in the input data matrix, else column A will only show a hyphen in the associated cells). In the present example, cells B20:B39 provide Changing Cells range. Column C specifies the capacities of the arcs of the network (cells C20:C39). The constraints of the model represent the flow balance equation for each node. The LP formulation in Section 6.4.3 shows that it is not necessary to construct flow equations for the first and last nodes of the network (nodes 1 and 5 in Figure 6.35). Thus, cells F20:F22 define the left-hand side and cells G20:G22 represent the right-hand side of the flow equations. 252 Chapter 6 Network Models Based on given information, Solver parameters for the example in Figure 6.26 are entered as Changing Calls: 320:B39 Constraints: B20:B39<=C20:C39 (Arc capacity) F20:F22=G20:G22 (Flow equations for nodes 2, 3, and 4) Note that Target Cell is automated and need not be changed. The Equal to parameter is Max because this is a maximization problem. The output in Figure 6.35 yields the solution (N1-N2 = 20, N1-N3 = 30, N1-N4 = 10. N2-N5 = 20, N3-N4 = 10, N3-N5 = 20, N4-N5 = 20) with a maximum flow of 60 units. PROBLEM SET 6.4D 1. Solve Problem 2, Set 6.4b using Excel Solver. 2. Solve Problem 5, Set 6.4b using Excel Solver. 6.5 MINIMUM-COST CAPACITATED FLOW PROBLEM The minimum-cost capacitated flow problem is based on the following assumptions: 1. A (nonnegative) unit flow cost is associated with each arc. 2. Arcs may have positive lower capacity limits. 3. Any node in the network may act as a source or as a sink. The new model determines the flows in the different arcs that minimize the total cost while satisfying the flow restrictions on the arcs and the supply and demand amounts at the nodes. We first present the capacitated network flow model and its equivalent linear programming formulation. The linear programming formulation is the basis for the development of a special capacitated simplex algorithm for solving the network flow model. The section ends with a presentation of a spreadsheet template of the minimum-cost capacitated network. 6.5.1 Network Representation Consider a capacitated network G = (N, A), where N is the set of nodes, and A is the set of arcs and define Xjj = amount of flow from node i to node j Ujj (/(/) = upper (lower) capacity of arc (/, /) Cji = unit flow cost from node i to node; fi = net flow at node i Figure 6.36 depicts these definitions on arc (/,/). The label [/•■] assumes a positive (negative) value when a net supply (demand) is associated with node i. 6.5 Minimum-Cost Capacitated Flow Problem 253 FIGURE 6.36 Capacitated arc with external flow Example 6.5-1 GrainCo supplies corn from three silos to three poultry farms. The supply amounts at the three silos are 100, 200, and 50 thousand bushels; and the demand at the three farms is 150,80, and 120 thousand bushels. GrainCo mostly uses railroads to transport the corn to the farms, with the exception of three routes where trucks are used. Figure 6.37 shows the available route between the silos and the farms. The silos are represented by nodes 1, 2, and 3 whose supply amounts are [100], [200], and [50], respectively. The farms are represented by nodes 4, 5, and 6 whose demand amounts are [-150], [-80], and [-120], respectively. The routes allow transshipping between the silos. Arcs (1, 4), (3, 4), and (4, 6) are truck routes with minimum and maximum capacities. For example, the capacity of route (1, 4) is between 50 and 80 thousand bushels. All other routes use trainloads, whose maximum capacity is practically unlimited. The transportation costs per bushel are indicated on the respective arcs. FIGURE 6.37 Capacitated network for Example 6.5-1 [-80] PROBLEM SET 6.5A 1. A product is manufactured to satisfy demand over a 4-period planning horizon according to the following data: Period Units of demand Unit production cost ($) Unit holding cost (S) 1 100 24 1 2 110 26 2 3 95 21 1 4 125 24 2 Given that no back-ordering is allowed, represent the problem as a network model. 2. In Problem 1, suppose that back-ordering is allowed at a penalty of $1.50 per unit per period. Formulate the problem as a network model. 254 Chapter 6 Network Models 3. In Problem 1, suppose that the production capacities of periods 1 to 4 are 110,95,125, and 100 units, respectively, in which case the given demand cannot be satisfied without back-ordering. Assuming that the penalty cost for back-ordering is $1.50 per unit per period, formulate the problem as a network model. 4. Daw Chemical owns two plants that manufacture a basic chemical compound for two customers at the rate of 660 and 800 tons per month. The monthly production capacity of plant 1 is between 400 and 800 tons and that of plant 2 is between 450 and 900 tons. The production costs per ton in plants 1 and 2 are $25 and $28, respectively. Raw material for the plants is provided by two suppliers, who are contracted to ship at least 500 and 700 tons per month for plants 1 and 2 at the costs of $200 and $210 per ton, respectively. Daw Chemical also assumes the transportation cost of both the raw material and the final compound. The costs per ton of transporting the raw material from supplier 1 to plants 1 and 2 arc $10 and $12. Similar costs from supplier 2 are $9 and $13, respectively. The transportation costs per ton from plant 1 to clients 1 and 2 are $3 and $4, and from plant 2 costs are $5 and $2, respectively. Assuming that 1 ton of raw material produces 1 ton of the final compound, formulate the problem as a network model. 5. Two nonintegrated public schools are required to change the racial balance of their enrollments by accepting minority students. Minority enrollment must be between 30% and 40% in both schools. Nonminority students live in two communities, and minority-students live in three other communities. Traveled distances, in miles, from the five communities to the two schools are summarized in the following table: Round-lrip miles from school to Minority areas Nonminority areas Maximum - School enrollment 12 3 12 1 1500 20 12 10 4 5 2 2000 15 18 8 6 5 Student population 500 450 300 1000 1000 Formulate the problem as a network model to determine the number of minority and nonminority students enrolled in each school. 6.5.2 Linear Programming Formulation The formulation of the capacitated network model as a linear program provides the foundation for the development of the capacitated simplex algorithm, which we will present in the next section. Using the notation introduced in Section 6.5.1, the linear program for the capacitated network is given as Minimize z = 2 2c'^v (i.i)sA subject to S xJk ~ 2 x*i = fp ieN hi — Xij — Uii 6.5 Minimum-Cost Capacitated Flow Problem 255 The equation for node j measures the net flow ft in node j as (Outgoing flow from node j) - (Incoming flow into node j) = ft Node / acts as a source if ft > 0 and as a sink if fj < 0. We can always remove the lower bound /,y from the constraints by using the substitution The new flow variable, x'g, has an upper limit of u» — L. Additionally, the net flow at node i becomes f, - /,y, and that at node / is ft + Figure 6.38 shows the transformation of activity (/, /) after the lower bound is substituted out. \fi\ $c U}] Ifi-hß $c [fj + hß FIGURE 6.38 _> /On _^ /On_'i f /On Removal of the lower bound in arcs Example 6.5-2 Write the linear program for the network in Figure 6.37, before and after the lower bounds are substituted out. The main constraints of the linear program relate the input-output flow at each node, which yields the following LP: % *13 xa «23 je-» «34 «35 «46 «56 Minimize 3 4 1 5 6 1 2 2 4 Node 1 1 1 1 = 100 Node 2 -1 1 1 = 200 Node 3 -1 -1 1 1 = 50 Node 4 -1 -1 1 = -150 Node 5 -1 1 1 = -80 Node 6 -1 -1 = -120 Lower bounds 0 0 50 0 0 70 0 100 0 Upper bounds 00 co 80 00 120 00 120 00 Note the arrangement of the constraints coefficients. The column associated with variable .t,, has exactly one +1 in row i and one -1 in row /. The rest of the coefficients are 0. This structure is typical of network flow models. The variables with lower bounds arc substituted as Xj4 .Vi4 "I" 50 x?4 = xM + 70 *4fi = *46 + 1°0 256 Chapter 6 Network Models The resulting linear program is xu X\3 *14 x21 x2i X34 x35 x4h %> Minimize 3 4 1 5 6 1 2 2 4 Node 1 1 1 1 = 50 Node 2 -1 1 1 = 200 Node 3 -1 -1 I 1 = -20 Node 4 -1 -1 1 = -130 Node 5 -1 -1 1 = -80 Node 6 -1 -1 = -20 Upper bounds oo oo 30 00 00 50 00 20 The corresponding network after substituting out the lower bounds is shown in Figure 6.39. Note that the lower-bound substitution can be effected directly from Figure 6.37 using the substitution in Figure 6.38, and without the need to express the problem as a linear program first. FIGURE 6.39 Network of Example 6.5-2 after substituting out lower bounds [-80] Example 6.5-3 (Employment Scheduling) This example illustrates a network model that initially does not satisfy the "node flow'' requirement (i.e., node output flow less node input flow equals node net flow), but that can be converted to this form readily through special manipulation of the constraints of the linear program. Tempo Employment Agency has a contract to provide workers over the next 4 months (January to April) according to the following schedule: Month Jan. Feb. Mar. Apr. No. of workers 100 120 80 170 Because of change in demand, it may be economical to retain more workers than needed in a given month. The cost of recruiting and maintaining a worker is a function of their employment period as the following table shows: Employment period (months) 12 3 4 Cost per worker ($) 100 130 180 220 6.5 Minimum-Cost Capacitated Flow Problem 257 Let Xjj - number of workers hired at the start of month i and terminated at the start of month / For example, x12 gives the number of workers hired in January for 1 month only. To formulate the problem as a linear program for the 4-month period, we add May as a dummy month (month 5), so that x4S defines hiring in April for April. The constraints recognize that the demand for period k can be satisfied by all xtl such that i < k < j. Letting 5, > 0 be the surplus number of workers in month i, the linear program is given as X\2 «13 xI4 *ij x2i *24 *25 xM *35 x45 i'i Sj St, s4 Minimize 100 130 180 220 100 130 180 100 130 100 Jan. 1 1 1 1 -1 = 100 Feb. 1 1 1 1 1 1 -1 = 120 Mar. 1 1 1 1 1 1 -1 = 80 Apr. 1 1 1 1 -1 =170 The preceding LP does not have the (-1, +1) special structure of the network flow model (see Example 6.5-2). Nevertheless, the given linear program can be converted into an equivalent network flow model by using the following arithmetic manipulations: 1. In an n-equation linear program, create a new equation, n + 1, by multiplying equation n by — 1. 2. Leave equation 1 unchanged. 3. For i = 2, 3, replace each equation / with (equation i) — (equation i — 1). The application of these manipulations to the employment scheduling example yields the following linear program whose structure fits the network flow model: X12 Xyi, X]4 Xi$ -^23 x24 •^25 %5 XH S l Si S;, S4 Minimize 100 130 180 220 100 130 180 100 130 100 Jan. 1111 -1 = 100 Feb. -1 1 1 1 1 -1 = 20 Mar. -1 -1 1 1 1 -1 = -40 Apr. -1 -1 -1 1 1 -1 = 90 May -1 -1 -1 -1 1 = -170 Using the preceding formulation, the employment scheduling model can be represented equivalently by the minimum-cost flow network shown in Figure 6.40. Actually, because the arcs have no upper bounds, the problem can be solved also as a transshipment model (see Section 5.5). 258 Chapter 6 Network Models x\5 FIGURE 6.40 Network representation of employment scheduling problem PROBLEM SET 6.5B 1. Write the linear program associated with the minimum-cost flow network in Figure 6.41. before and after the lower bounds are substituted out. [20] FIGURE 6.41 Network for Problem 1, Set 6.5b t 40] 2. Use inspection to find a feasible solution to the minimum-cost network model of the employment scheduling problem in Example 6.5-3 (Figure 6.40). Interpret the solution by showing the pattern of hiring and firing that satisfies the demand for each month, and compute the associated total cost. 3. Reformulate the employment scheduling model of Example 6.5-3, assuming that a worker must be hired for at least 2 months. Write the linear program, and convert it to a minimum-cost flow network. 4. Develop the linear program and the associated minimum-cost flow network for the employment scheduling model of Example 6.5-3 using the following 5-month demand data. The per worker costs of recruiting and maintaining a worker for periods of 1 to 5 months are $50, $70, $85, $100, and $130, respectively. Month 1 2 3 4 5 No. of workers 300 180 90 170 200 Month 1 2 3 4 5 No. of workers 200 220 300 50 240 6.5 Minimum-Cost Capacitated Flow Problem 259 5. Conversion of a Capacitated Network into an Uncapacitated Network. Show that an arc (i —> ;') with capacitated flow xt] £ m,7 can be replaced with two uncapacitated arcs (i —> k) and (j —> fc) with a net (output) flow of [—«,-,] at node and an additional (input) flow of [+w,,] at node The result is that the capacitated network can be converted to an uncapacitated transportation cost model (Section 5.1). Apply the resulting transformation to the network in Figure 6.42 and find the optimum solution to the original network by applying TORA to the uncapacitated transportation model. FIGURE 6.42 Network for Problem 5, Set 6.5b 6.5.3 Capacitated Network Simplex Algorithm The algorithm is based on the exact steps of the regular simplex method, but designed to exploit the special network structure of the minimum-cost flow model. Given f is the net flow at node i as defined in the linear program of Section 6.5.2, the capacitated simplex algorithm stipulates that the network must satisfy n The condition says that the total supply in the network equals the total demand. We can always satisfy this requirement by adding a balancing dummy source or destination, which we connect to all other nodes in the network by zero unit cost and infinite capacity arcs. However, the balancing of the network does not guarantee a feasible solution as this depends on the restricting capacities of the arcs. We will now present the steps of the capacitated algorithm. Familiarity with the simplex method and duality theory (Chapters 3 and 4) is essential. Also, knowledge of the upper-bounded simplex method (Section 7.3) is helpful. Step 0. Determine a starting basic feasible solution (set of arcs) for the network. Go to step 1. Step 1. Determine an entering arc (variable) using the simplex method optimality condition. If the solution is optimal, stop; otherwise, go to step 2. Step 2. Determine the leaving arc (variable) using the simplex method feasibility condition. Determine the new solution, and then go to step 1. An n-nodc network with zero net flow (i.e., /, + f2 + ... + f„ - 0) consists of n - 1 independent constraint equations. Thus, an associated basic solution must include n — 1 arcs. It can be proved that a basic solution always corresponds to a spanning tree of the network (see Section 6.2). 260 Chapter 6 Network Models The entering arc (step 1) is determined by computing Zy ~ c,-/, the objective coefficients, for all the current nonbasic arcs (i, /). If z,j - c„ 0 for all i andthe current basis is optimum. Otherwise, we select the nonbasic arc with the most positive z„ - c, to enter the basis. The computation of objective coefficients is based on duality, exactly as we did with the transportation model (see Section 5.3.4). Using the linear program defined in Section 6.5.2, let w, be the dual variable associated with the constraint of node i\ then the dual problem (excluding the upper bounds) is given as Because the original linear program (Section 6.5.2) has one redundant constraint by definition, we can assign an arbitrary value to one of the dual variables (compare with the transportation algorithm. Section 5.3). For convenience, we will set wy = 0. We then solve the (basic) equations w, - Wj = cif to determine the remaining dual values. From Section 4.2.3, Method 2, we know that the objective coefficient of nonbasic xij is the difference between the left-hand side and the right-hand side of the dual associated dual constraint—that is Zij - Cjj = W, - Wj - C,j The only remaining detail is to show how the leaving variable is determined. We do so by using a numeric example. Example 6.5-4 A network of pipelines connects two water desalinization plants to two cities. The daily supply amounts at the two plants are 40 and 50 million gallons, and the daily demand amounts at cities 1 and 2 are 30 and 60 million gallons. Nodes 1 and 2 represent plants 1 and 2, and nodes 4 and 5 represent cities 1 and 2. Node 3 is a booster station between the plants and the cities. The model is already balanced because the supply at nodes 1 and 2 equals the demand at nodes 4 and 5. Figure 6.43 gives the associated network. Maximize z = ^fiW, subject to From the theory of linear programming, we have Wj - Wj = Cjj, for basic arc (i, j) FIGURE 6.43 Unit cost Arc capacity Network for Example 6.5-4 Plant 2 [50] Plant! [40] $3 6.5 Minimum-Cost Capacitated Flow Problem 261 Iteration 0. Step 0. Determination of a Starting Basic Feasible Solution: The starting feasible spanning tree in Figure 6.44 (shown with solid arcs) is obtained by inspection. Normally, we use an artificial variable technique to find such a solution (for details, see Bazaraa et al., 1990, pp. 440-46). zP - cp = 0 - (-5) -3 = 2 Z25 - Cjs = -5 - (-15) -1=9 z45 - c4, = -5 - (-15) -4 = 6 Arc (2, 5) reaches upper bound at 30. Substitute jt25 = 30 - xS2. Reduce x%$ and jc,5 each by 30. FIGURE 6.44 Network for iteration 0 In Figure 6.44. the basic feasible solution consists of (solid) arcs (1,3), (1,4), (2,3), and (3, 5) with the feasible flows of 10, 30, 50, and 60 units, respectively. This leaves (dashed) arcs (1,2), (2,5), and (4,5) to represent the nonbasic variables. The notation x(c) shown on the arcs indicates that a flow of x units is assigned to an arc with capacity c. The default values for x and c are 0 and oo, respectively. Iteration 1. Step 1. Determination of the Entering Arc: We obtain the dual values by solving the current basic equations w, = 0 w, - Wj for basic (i, j) Arc(l, 3) : Wi — w3 — 7, hence w3 = -7 Arc (1, 4) : W] - w4 = 5, hence w4 = -5 Arc (2, 3) : w2 - w3 = 2, hence w2 = -5 Arc (3, 5) : w3 - w5 = 8, hence ws - -15 Now, we compute z« — c(y for the nonbasic variables as Arc(l, 2) : wx - w2 - cl2 = 0 - (-5) -3 = 2 Arc (2, 5):w2- w5 - c25 = (-5) - (-15) -1 = 9 Arc (4, 5) : w4 - w5 - c4S = (-5) - (-15) -4 = 6 Thus, arc (2,5) enters the basic solution. 262 Chapter 6 Network Models Step 2. Determination of the Leaving Arc: From Figure 6.44, arc (2,5) forms a loop with basic arcs (2, 3) and (3, 5). From the definition of the spanning tree, no other loop can be formed. Because the flow in the new arc (2, 5) must be increased, we adjust the flow in the arcs of the loop by an equal amount to maintain the feasibility of the new solution. To achieve this, we identify the positive (+) flow in the loop by the direction of flow of the entering arc (i.e., from 2 to 5). We then assign (+) or (—) to the remaining arcs of the loop, depending on whether the flow of each arc is with or against the direction of flow of the entering arc. These sign conventions are shown in Figure 6.44. Determination of the maximum level of flow in the entering arc (2,5) is based on two conditions: 1. New flow in current basic arcs of the loop cannot be negative. 2. New flow in the entering arc cannot exceed its capacity. The application of condition 1 shows that the flows in arcs (2,3) and (3,5) cannot be decreased by more than min {50, 60} = 50 units. Condition 2 stipulates that the flow in arc (2, 5) can be increased to at most the arc capacity (=30 units). Thus, the maximum flow change in the loop is min {30, 50} = 30 units. The new flows in the loop are thus 30 units in arc (2, 5), 50 - 30 = 20 units in arc (2,3), and 60 - 30 = 30 units in arc (3,5). Because none of the current basic arcs leave the basis at zero level, the new arc (2, 5) must remain nonbasic at the upper bound. However, to avoid dealing with nonbasic arcs that are at capacity (or upper bound) level, we implement the substitution X25 = 30 - X52, 0 :£ X52 :£ 30 This substitution is effected in the flow equations associated with nodes 2 and 5 as follows. Consider Current flow equation at node 2: 50 + x12 = x2J + x25 Current flow equation at node 5: x25 + x35 + x45 = 60 Then, the substitution x25 = 30 - x52 gives New flow equation at node 2: 20 + x12 + x52 = x23 New flow equation at node 5: x35 + xe = x52 + 30 The results of these changes are shown in Figure 6.45. The direction of flow in arc (2, 5) is now reversed to 5 —> 2 with x52 = 0, as desired. The substitution also requires changing the unit cost of arc (5, 2) to — $1. We will indicate this direction reversal on the network by tagging the arc with an asterisk. Iteration 2. Figure 6.45 summarizes the new values of z/; — ci} (verify!) and shows that arc (4,5) enters the basic solution. It also defines the loop associated with the new-entering arc and assigns the signs to its arcs. The flow in arc (4,5) can be increased by the smallest of 1. Maximum allowable increase in entering arc (4, 5) = oo 2. Maximum allowable in crease in arc (1, 4) = 35 — 30 = 5 units 6.5 Minimum-Cost Capacitated Flow Problem 263 u\ = 0 r*4 = — 5 W Q--30I5J-S® [-3°J ZB - c12 = 0 - (-5) -3 = 2 | \ . r , ] 252 " c52 = -15 -(-5) -(-1) = -9 *xf> W *45 " c45 = -5 - (-15) -4 = 6 ^N? «5 = -7 $3 j ("N ^ ' f08) ^ll'C enters at lcvel 5. I 1% I Arc (1,4) leaves at upper bound. 1 % 1 I y^V? Substitutexu = 35 -*41. X/ " _$1 ^V^n FIGURE 6.45 [20] [2J-*---------^5J [-30] Reduce x13 and x35 each by 5. Network for "'2 = ~5 "'5 = _15 iteration 1 3. Maximum allowable decrease in arc (1, 3) — 10 units 4. Maximum allowable decrease in arc (3, 5) = 30 units Thus, the flow in arc (4,5) can be increased to 5 units, which will make (4,5) basic and will force basic arc (1,4) to be nonbasic at its upper bound ( = 35). Using the substitution x14 = 35 — x41, the network is changed as shown in Figure 6.46, with arcs (1,3), (2,3), (3,5), and (4,5) forming the basic (spanning tree) solution. The reversal of flow in arc (1,4) changes its unit cost to — $5. Also, convince yourself that the substitution in the flow equations of nodes 1 and 4 will net 5 input units at each node. Iteration 3. The computations of the new ztj - c(! for the nonbasic arcs (1, 2), (4,1), and (5, 2) are summarized in Figure 6.46, which shows that arc (1, 2) enters at level 5, and arc (1,3) becomes nonbasic at level O.The new solution is depicted in Figure 6.47. Iteration 4. The new z,7 - in Figure 6.47 shows that the solution is optimum. The values of the original variables are obtained by back substitution as shown in Figure 6.47. 264 Chapter 6 Network Models FIGURE 6.47 Network for iteration 3 PROBLEM SET 6.5C 1. Solve Problem 1, Set 6.5a by the capacitated simplex algorithm, and also show that il can be solved by the transshipment model. 2. Solve Problem 2, Set 6.5a by the capacitated simplex algorithm, and also show that it can be solved by the transshipment model. 3. Solve Problem 3. Set 6.5a by the capacitated simplex algorithm. 4. Solve Problem 4, Set 6.5a by the capacitated simplex algorithm. 5. Solve Problem 5, Set 6.5a by the capacitated simplex algorithm. 6. Solve the employment scheduling problem of Example 6.5-3 by the capacitated simplex algorithm. 7. Wyoming Electric uses existing slurry pipes to transport coal (carried by pumped water) from three mining areas (1,2, and 3) to three power plants (4,5, and 6). Each pipe can transport at most 10 tons per hour.The transportation costs per ton and the supply and demand per hour are given in the following table. 4 5 6 Supply 1 S5 S8 $4 8 2 $6 $9 $12 10 3 $3 $1 $5 18 Demand 16 6 14 Determine the optimum shipping schedule. 8. The network in Figure 6.48 gives the distances among seven cities. Use the capacitated simplex algorithm to find the shortest distance between nodes 1 and 7. (Hint: Assume that nodes 1 and 7 have net flows of [+1] and [—1], respectively. All the other nodes have zero net flow.) 9. Show how the capacitated minimum-cost flow model can be specialized to represent the maximum flow model of Section 6.4. Apply the transformation to the network in Example 6.4-2. For convenience, assume that the flow capacity from 4 to 3 is zero. All the remaining data are unchanged. 6.5 Minimum-Cost Capacitated Flow Problem 265 FIGURE 6.48 Network for Problem 8, Set 6.5c .4 Excel Spreadsheet Solution of the Minimum-Cost Capacitated Flow Model As in the cases of the shortest-route and maximum flow models, the Excel spreadsheet developed for the general transportation model (Section 5.3.3) applies readily to the capacitated network flow model. Figure 6.49 shows the application of the spreadsheet to Example 6.5-4 (file ch6SolverMinCostCapacitatedNetwork.xls). The spreadsheet is designed for networks with a maximum of 10 nodes. In the capacity matrix (cells N6:W15),5 a blank entry signifies an infinite capacity arc. A nonexisting arc is represented by a zero-capacity entry. As an illustration, in Example 6.5-4, infinite capacity arc 1-2 is represented by a blank entry in cell 06, and nonexisting arc 3-4 is shown by a zero entry in cell Q8. The unit cost matrix resides in cells B6:K15. We arbitrarily assign zero unit cost to all nonexisting arcs. Once the unit cost and capacity matrices are created, the remainder of the spreadsheet (intermediate calculations and optimum solution sections) is created automatically, delineating the cells needed to update Solver parameters for Changing Cells and Constraints. Target Cell is already defined for any network (with 10 nodes or less). Specifically, for Example 6.5-4, we have, Changing cells: B20:B39 Constraints: B20:B39<=C2C:C39 (Arc capacity) F19:F23=G19:G23 (Node flow equation) Figure 6.49 provides the following solution: N1-N2 = 5,N1-N4 = 35,N2-N3 = 25, N2-N5 = 30,N3-N5 = 25,andN4-N5 = 5.The associated total cost is $490. PROBLEM SET 6.5D 1. Solve the following problem using the spreadsheet in Section 6.5.4: (a) Problem 3, Set 6.5c (b) Problem 4, Set 6.5c Tn Figure 6.49, rows 11 through 15 and column K are hidden to conserve space. 266 Chapter 6 Network Models FIGURE 6.49 Excel Solver output for Example 6.5-4 5 » ,'w. ^Qadtatod Network Model with Solver --- H ,;V,v. . - ..... Hi : » S3 : W « 1 _J» j 3 7 5 0- . « 5 is 35 8 a « ~t i i ; 1 Ti 1 "": r si n' "iT I" i i- ü « "I pQ I™ i j; |tt" ' " " 1 l" " 3 *< < ' i~ ] £ m 1 :"1 pjQjp ' 'J "i |j ' 1 i't 'l: I I ' ä ; ! fi ' ' 6 1: *t 1 ' I 0 S Ml-IB ■S (1 k N « X ~n2-n3 * s i :.-;,3« ■ N3.NI ;' :1 it II IG-Nt 8 F: m ij « : n4-n2 5 IpF -: 5 i; "¥■1 1 y ns a r • «5-1« s m P«Mämetef5 Set TargM Cell: ItESlE "~ t-.. Owen» :;efe • , j^,. m,_ ...... 5-jh.-p.-t to the OfKttwfc? (c) Problem 7, Set 6.5c (d) Problem 8, Set 6.5c 6.6 CPM AND PERT CPM (Critical Path Method) and PERT (Program Evaluation and Review Technique) are network-based methods designed to assist in the planning, scheduling, and control of projects. A project is defined as a collection of interrelated activities with each activity consuming time and resources. The objective of CPM and PERT is to provide analytic means for scheduling the activities. Figure 6.50 summarizes the steps of the techniques. First, we define the activities of the project, their precedence relationships, and their 6.6 CPM and PERT 267 Network I Project activities j Network calculation u Time schedule Jime_j FIGURE 6.50 Phases for project planning with CPM-PERT time requirements. Next, the project is translated into a network that shows the precedence relationships among the activities. The third step involves specific network computations that form the basis for the development of the time schedule for the project. During the execution of the project, the schedule may not be realized as planned, causing some of the activities to be expedited or delayed. In this case, it will be necessary to update the schedule to reflect the realities on the ground. This is the reason for including a feedback loop between the time schedule phase and the network phase as shown in Figure 6.50. The two techniques, CPM and PERT, which were developed independently, differ in that CPM assumes deterministic activity durations, whereas PERT assumes probabilistic durations. This presentation will start with CPM and then provide the details of PERT. 6.6.1 Network Representation Each activity of the project is represented by an arc pointing in the direction of progress in the project. The nodes of the network establish the precedence relationships among the different activities of the project. Two rules are available for constructing the network. Rule 1. Each activity is represented by one, and only one, arc. Rule 2. Each activity must be identified by two distinct end nodes. Figure 6.51 shows how a dummy activity can be used to represent two concurrent activities, A and B. By definition, a dummy activity, which normally is depicted by a dashed arc, consumes no time or resources. Inserting a dummy activity in one of the four ways shown in Figure 6.51, we maintain the concurrence of A and B, and also provide unique end nodes for the two activities (to satisfy rule 2). Rule 3. To maintain the correct precedence relationships, the following questions must be answered as each activity is added to the network: (a) What activities must immediately precede the current activity? (b) What activities must follow the current activity? (c) What activities must occur concurrently with the current activity? 268 Chapter 6 Network Models FIGURE 6.51 Use of dummy activity to produce unique representation of concurrent activities A and B The answers to these questions may require the use of dummy activities to ensure correct precedences among the activities. For example, consider the following segment of a project: 1. Activity C starts immediately after A and B have been completed. 2. Activity E starts after B only has been completed. Part (a) of Figure 6.52 shows the incorrect representation of the precedence relationship because it requires both A and B to be completed before E can start. In part (b). the use of a dummy activity rectifies the situation. FIGURE 6.52 Use of dummy activity to ensure correct precedence relationship (a) (b) Example 6.6-1 A publisher has a contract with an author to publish a textbook. The (simplified) activities associated with the production of the textbook are given below. Develop the associated network for the project. Activity Predecessor(s) Duration (weeks) A: Manuscript proofreading by editor 3 B: Sample pages prepared by typesetter 2 C: Book cover design — 4 D: Preparation of artwork for book figures 3 E: Author's approval of edited manuscript and sample pages A, B 2 6.6 CPM and PERT 269 F: G: H: I: J: Book typesetting E F D 2 2 1 2 4 Author checks typeset pages Author checks artwork Production of printing plates Book production and binding G, H CI Figure 6.53 provides the network describing the precedence relationships among the different activities. Dummy activity (2, 3) produces unique end nodes for concurrent activities A and B. The numbering of the nodes is done in a manner that indicates the direction of progress in the project. FIGURE 6.53 Project network for Example 6.6-1 PROBLEM SET 6.6A 1. Construct the project network comprised of activities A to L with the following precedence relationships: (a) A, B, and C, the first activities of the project, can be executed concurrently. (b) A and B precede D. (c) B precedes E, F and H. (d) F and C precede G. (e) E and H precede / and /. (f) C, D, F, and / precede K. (g) K precedes L. (h) /, G, and L are the terminal activities of the project. 2. Construct the project network comprised of activities A to P that satisfies the following precedence relationships: (a) A, B, and C, the first activities of the project, can be executed concurrently. (b) D, E, and F follow A. (c) / and G follow both B and D. (d) H follows both C and G. (e) K and L follow /. (f) / succeeds both E and H. (g) M and N succeed F, but cannot start until both E and H are completed. (h) O succeeds M and /. (i) P succeeds /, L, and O. (j) K, N, and P are the terminal activities of the project. J-4 270 Chapter 6 Network Models 3. The footings of a building can be completed in four connected sections. The activities for each section include (1) digging, (2) placing steel, and (3) pouring concrete. The digging of one section cannot start until that of the preceding section has been completed. The same restriction applies to pouring concrete. Develop the project network. 4. In Problem 3, suppose that 10% of the plumbing work can be started simultaneously with the digging of the first section. After each section of the footings is completed, an additional 5% of the plumbing can be started provided that the preceding 5% portion is completed. The remaining plumbing can be completed at the end of the project. Construct the project network. 5. An opinion survey involves designing and printing questionnaires, hiring and training personnel, selecting participants, mailing questionnaires, and analyzing the data. Construct the project network, stating all assumptions. 6. The activities in the following table describe the construction of a new house. Develop the associated project network. Activity Predcccssor(s) Duration (days) A: Clear site — 1 B: Bring utilities to site 2 C: Excavate 1 D: Pour foundation < 2 E: Outside plumbing B,C 6 F: Frame house D 10 G: Do electric wiring F 3 H: Lay floor G 1 I: Lay roof F 1 J: Inside plumbing E,H 5 K: Shingling I 2 L: Outside sheathing insulation F,J 1 M: Install windows and outside doors F 2 N: Do brick work L,M 4 O: Insulate walls and ceiling G,J 2 P: Cover walls and ceiling O 2 Q- Insulate roof IP 1 R: Finish interior P 7 S: Finish exterior I, A' 7 T: Landscape S 3 7. A company is in the process of preparing a budget for launching a new product. The following table provides the associated activities and their durations. Construct the project network. Activity Predecessor(s) Duration (days) A: Forecast sales volume — 10 B: Study competitive market — 7 C: Design item and facilities A 5 D: Prepare production schedule C 3 E: Estimate cost of production D 2 F. Set sales price B,E 1 G: Prepare budget E, F 14 6.6 CPM and PERT 271 8. The activities involved in a candlelight choir service are listed in the following table. Construct the project network. Activity Predcccssor(s) Duration (days) A: Select music _ 2 B: Learn music A 14 C: Make copies and buy books A 14 D: Tryouts B,C 3 E: Rehearsals D 70 F: Rent candelabra D 14 G: Decorate candelabra r 1 H: Set up decorations D 1 I: Order choir robe stoles D 7 /: Check out public address system D 7 K: Select music tracks J 14 L: Set up public address system K 1 M: Final rehearsal E, G, L 1 N: Choir party H, L, M I O: Final program I,N 1 9. The widening of a road section requires relocating ("reconductoring") 1700 feet of 13.8-kV overhead primary line. The following table summarizes the activities of the project. Construct the associated project network. Activity Predecessor(s) Duration (days) A: Job review — 1 B: Advise customers of temporary outage A .5 C: Requisition stores A 1 D: Scout job A .5 E: Secure poles and material CD 3 F: Distribute poles E 3.5 G: Pole location coordination D .5 H: Re-stake G .5 I: Dig holes II 3 .1: Frame and set poles F,I 4 K: Cover old conductors 1:1 1 L: Pull new conductors IK 2 M: Install remaining material L 2 N: Sag conductor L 2 O: Trim trees D 2 P: De-energize and switch lines B, M, N, O .1 Q: Energize and switch new line P .5 R-. Clean up Q 1 S: Remove old conductor Q 1 T: Remove old poles s 2 V: Return material to stores R, T 2 10. The following table gives the activities for buying a new car. Construct the project network. 272 Chapter 6 Network Models Activity Predeccssor(s) Duration (days) A: Conduct feasibility study — 3 B: Find potential buyer for present car A 14 C: List possible models A 1 D: Research all possible models C 3 E: Conduct interview with mechanic C 1 F: Collect dealer propaganda c 2 (J: Compile pertinent data D, E, F 1 H: Choose top three models G 1 I: Test-drive all three choices H 3 ./: Gather warranty and financing data II 2 K: Choose one car 1.1 2 L: Choose dealer K 2 M: Search for desired color and options L 4 N: Test-drive chosen model once again L 1 O: Purchase new car B,M,N 3 6.6.2 Critical Path (CPM) Computations The ultimate result in CPM is the construction of the time schedule for the project (see Figure 6.50). To achieve this objective conveniently, we carry out special computations that produce the following information: 1. Total duration needed to complete the project 2. Classification of the activities of the project as critical and noncritical An activity is said to be critical if there is no "leeway" in determining its start and finish times. A noncritical activity allows some scheduling slack, so that the start time of the activity may be advanced or delayed within limits without affecting the completion date of the entire project. To carry out the necessary computations, we define an event as a point in time at which activities are terminated and others are started. In terms of the network, an event corresponds to a node. Define □,■ = Earliest occurrence time of event j At = Latest occurrence time of event j Dtj = Duration of activity (i, j) The definitions of the earliest and latest occurrence times of event / are specified relative to the start and completion dates of the entire project. The critical path calculations involve two passes: The forward pass determines the earliest occurrence times of the events, and the backward pass calculates their latest occurrence times. Forward Pass (Earliest Occurrence Times, □). The computations start at node 1 and advance recursively to end node n. 6.6 CPM and PERT 273 Initial Step. Set □, = 0 to indicate that the project starts at time 0. General StepGiven that nodes p, q, ..., and v are linked directly to node j by incoming activities(p, j), (q, j),..., and (v,;') and that the earliest occurrence times of events (nodes) p, q, ..., and v have already been computed, then the earliest occurrence time of event / is computed as = max-{Dp + Dpj, □„ + Dqh ...,□, + DV)] The forward pass is complete when □„ at node n has been computed. By definition □.■ represents the longest path (duration) to node /. Backward Pass (Latest Occurrence Times, A). Following the completion of the forward pass, the backward pass computations start at node n and end at node 1. Initial Step. Set A„ = □„ to indicate that the earliest and latest occurrences of the last node of the project are the same. General Step /. Given that nodes p, ..., and v are linked directly to node j by outgoing activities (/, p\ (/', q),..., and (/', v) and that the latest occurrence times of nodes p, q,..., and v have already been computed, the latest occurrence time of node / is computed as A, = min{Ap - Djp, Aq - Djq,..., A„ - £»/v} The backward pass is complete when Aj at node 1 is computed. Based on the preceding calculations, an activity (/, j) will be critical if it satisfies three conditions. 1. = □, 2. = □, 3. A, - A, = The three conditions state that the earliest and latest occurrence times of nodes i and; are equal, and the duration Dtj fits "tightly" in the specified time span. An activity that does not satisfy all three conditions is noncritical. The critical activities of a network must constitute an uninterrupted path that spans the entire network from start to finish. Example 6.6-2 Determine the critical path for the project network in Figure 6.54. All the durations are in days. Forward Pass Node 1. Set Ux = 0 Node 2. D2 = D1 + D12 = 0 + 5 = 5 274 Chapter 6 Network Models Node 3. Qj = max-p, + D13, Q, + D23] = max {0 + 6, 5 + 3} = 8 Node 4. Q, = + Dz4 = 5 + 8 = 13 NodeS. D5 = maxjO, + D35, Q, + £>45} = max {8 + 2, 13 + 0} = 13 Node 6. □(, = max {O, + £>36, Q» + D46, D5 + Z)56} = max {8 + 11, 13 + 1, 13 + 12} = 25 The computations show that the project can be completed in 25 days. Backward Pass Node 6. Set A6 = D6 = 25 Node 5. A5 = A6 - D56 = 25 - 12 = 13 Node 4. A4 = min{A6 - £>46, A5 - £>45} = min{25 - 1, 13 - 0} = 13 Node 3. A3 = min{A6 - £»36, A5 - D35} = min{25 - 11, 13 - 2} = 11 Node 2. A2 = min{A4 - D24, A3 - D23} = min{13 - 8, 11 - 3} = 5 Node 1. A, = min{A3 - D13, A2 - Dl2} = min{ll - 6, 5 - 5} = 0 Correct computations will always end with A! = 0. The forward and backward pass computations are summarized in Figure 6.54. The rules for determining the critical activities show that the critical path is defined by 1 —»2—»4—»5—»6, which spans the network from start (node 1) to finish (node 6). The sum of the durations of the critical activities [(1,2), (2,4), (4,5), and (5,6)] equals the duration of the project (= 25 days). Observe that activity (4,6) satisfies the first two conditions for a critical activity (A4 = D4 = 13 and A5 = = 25) but not the third (pe - D4 D46). Hence, the activity is not critical. 6.6 CPM and PERT 275 PROBLEM SET 6.6B 1. Determine the critical path for the project network in Figure 6.55. FIGURE 6.55 Project network for Problem 1, Set 6.6b 2. Determine the critical path for the project networks in Figure 6.56. Project (a) FIGURE 6.56 Project network for Problem 2, Set 6.6b Project(b) 3. Determine the critical path for the project in Problem 6, Set 6.6a. 4. Determine the critical path for the project in Problem 8, Set 6.6a. 5. Determine the critical path for the project in Problem 9, Set 6.6a. 6. Determine the critical path for the project in Problem 10, Set 6.6a. 6.6.3 Construction of the Time Schedule This section shows how the information obtained from the calculations in Section 6.6.2 can be used to develop the time schedule. We recognize that for an activity (i, j), □,-represents the earliest start time, and A;- represents the latest completion time. This means that (□,-, Ay) delineates the (maximum) span during which activity (i,;') may be scheduled. Construction of Preliminary Schedule. The method for constructing a preliminary schedule is illustrated by an example. 276 Chapter 6 Network Models Example 6.6-3 Determine the time schedule for the project of Example 6.6-2 (Figure 6.54). We can get a preliminary time schedule for the different activities of the project by delineating their respective time spans as shown in Figure 6.57. Two observations are in order. 1. The critical activities (shown by solid lines) must be scheduled one right after the other to ensure that the project is completed within its specified 25-day duration. 2. The noncritical activities (shown by dashed lines) encompass spans that are larger than their respective durations, thus allowing slack (or "leeway") in scheduling them within their allotted spans. A - 5 D -8 H- 12 B-6 C - 3 I---------1 E - 2 I-------1 F- 11 h- G - 1 10 15 20 Days FIGURE 6.57 Preliminary schedule for the project of Example 6.6-2 Critical Noncritical 25 How should we schedule the noncritical activities within their respective spans? Normally, it is preferable to start each noncritical activity as early as possible. In this manner, slack periods will remain opportunely available at the end of the allotted span, where they can be used to absorb unexpected delays in the execution of the activity. It may be necessary, however, to delay the start of a noncritical activity past its earliest time. For example, in Figure 6.57, suppose that each of the noncritical activities E and F requires the use of a bulldozer, and that only one is available. Scheduling both E and F as early as possible requires two bulldozers between times 8 and 10. We can remove the overlap by starting E at time 8 and pushing the start time of F to somewhere between times 10 and 14. If all the noncritical activities can be scheduled as early as possible, the resulting schedule automatically is feasible. Otherwise, some precedence relationships may be violated if noncritical activities are delayed past their earliest time. Take, for example, activities C and E in Figure 6.57. In the project network (Figure 6.54), though C must 6.6 CPM and PERT 277 be completed before E, the spans of C and E in Figure 6.57 allow us to schedule C between times 6 and 9, and E between times 8 and 10. These spans, however, do not ensure that C will precede E. The need for a "red flag" that automatically reveals schedule conflict is thus evident. Such information is provided by computing the floats for the noncritical activities. Determination of the Floats. Floats are the slack times available within the allotted span of the noncritical activity. The two most common floats are the total float and the free float. Figure 6.58 gives a convenient summary for computing the total float (77^) and the free float (FFjj) for an activity (/', /). The total float is the excess of the time span defined from the earliest occurrence of event i to the latest occurrence of event / over the duration of (/, /')—that is, TFij = Ay - □, - Di] FIGURE 6.58 Computation of total and free floats ' 1 ©---■ crai-critica. ?ath Method from Main Menu. In the output screen, you have the option to select cpm caici i at i ois to produce step-by-step computations of the forward pass, backward pass, and the floats or cpm Bar chart to construct and experiment with the time schedule. Figure 6.59 shows TORA output for the CPM calculations of Example 6.6-2 (file ch6ToraCPMEx6-6-2.xls). If you elect to generate the output using the Mext Step option. TORA will guide you through the details of the forward and backward pass calculations. Figure 6.60 provides the TORA schedule produced by cpm Bar cnart option for the project of Example 6.6-2. The default bar chart automatically schedules all the non-critical activities as early as possible. You can study the impact of delaying the start time of a noncritical activity by using the self-explanatory drop-down lists inside the bottom left frame of the screen. The impact of a delay of a noncritical activity will be shown directly on the bar chart together with an accompanying explanation. For example, if you delay the start of activity B by more than 2 time units, the succeeding activities E and F will be delayed by an amount equal to the difference between the delay 6.6 CPM and PERT 279 FIGURE 6.59 TORA step-by-step CPM calculations of forward pass, backward pass, and floats for Example 6.6-2 and the free float of activity B. Specifically, given the free float for B is 2 time units, if B is delayed by 3 time units, then E and F must be delayed by at least 3-2 = 1 time unit. This situation is demonstrated in Figure 6.60. PROBLEM SET 6.6C 1. Given an activity (i, j) with duration £>,, and its earliest start time □, and its latest completion time A;, determine the earliest completion and the latest start times of 2. What are the total and free floats of a critical activity? 3. For each of the following activities, determine the maximum delay in the starting time relative to its earliest start time that will allow all the immediately succeeding activities to be scheduled anywhere between their earliest and latest completion times. (a) TF = 10, FF = 10, D = 4 (b) TF = 10, FF = 5, D = 4 (c) TF = 10, FF = 0, D = 4 4. In Example 6.6-4, use the floats to answer the following: (a) Suppose that activity B is started at time 1, and activity C is started at time 5, determine the earliest start times for E and F. 280 Chapter 6 Network Models (b) Suppose that activity B is started at time 3, and activity C is started at time 7, determine the earliest start times for E and E (c) If activity B starts at time 6, what effect will this have on other activities of the project? 5. In the project of Example 6.6-2 (Figure 6.54), assume that the durations of activities B and F are changed from 6 and 11 days to 20 and 25 days, respectively. (a) Determine the critical path. (b) Determine the total and free floats for the network, and identify the red-flagged activities. (c) Suppose that activity A is started at time 5, determine the earliest possible start times for activities Q D, E, and G. (d) Suppose that activities F, G, and H require the same equipment. Determine the minimum number of units needed of this equipment. 6. Compute the floats and identify the red-flagged activities for projects (a) and (b) in Figure 6.56, and then develop the time schedules under the following conditions: Project (a) (i) Activity (1,5) cannot start any earlier than time 14. (ii) Activities (5,6) and (5,7) use the same equipment, of which only one unit is available. (Hi) All other activities start as early as possible. 6.6 CPM and PERT 281 Project (b) (i) Activity (1,3) must be scheduled at its earliest start time while accounting for the requirement that (1,2), (1,3), and (1,6) use special equipment, of which 1 unit only is available. (ii) All other activities start as early as possible. 6.6.4 Linear Programming Formulation of CPM A CPM problem can be thought of as the opposite of the shortest-route problem (Section 6.3), in the sense that we are interested in finding the longest route from start to finish. We can thus apply the shortest-route LP formulation in Section 6.3.3 to CPM in the following manner. We assume that a unit flow enters the network at the start node and leaves at the finish node. Define xv = Amount of flow in activity (/,/) for all defined i and / Dij = Duration of activity (/,;') for all defined i and j Thus, the objective function of the linear program becomes Maximize z = 2 A/*/, all defined activities (i, /') (Compare with the shortest-route LP formulation in Section 6.3.3 where the objective function is minimized.) There is one constraint that represents the conservation of flow at each node—that is, for all node ;', Total input flow = Total output flow Naturally, all the variables, are nonnegative. Note that one of the constraints is redundant. Again, as in the shortest-route problem, we can use the dual of the LP to solve the CPM problem. The following example applies the two formulations to the project in Example 6.6-2. Example 6.6-5 The LP formulation of the project of Example 6.6-2 (Figure 6.54) is given below. Note that nodes 1 and 6 are the start and finish nodes, respectively. A B C D E F Dummy G II *« Maximize z = 5 6 3 8 2 11 0 1 12 Node 1 -1 -1 =-1 Node 2 1 -1 -1 = 0 Node 3 1 1 -1 -1 = 0 Node 4 1 -1 -1 = 0 Node 5 1 1 -1 = 0 Node 6 1 1 1 = 1 282 Chapter 6 Network Models TORA gives the optimum solution as z = 25, xv_{A) = 1, x24(D) = 1, jc45(Dummy) = 1, x56(H) = 1, all others = 0 The solution defines the critical path as A —> D —> Dummy —> H, and the duration of the project is 25 days. The dual problem of the LP given above is: Minimize w = y6 — yx subject to yi - y\ • 5 (A) V3 - y\ 6 (*) - yi 3 (q y4 - yi > 8 (D) ys - y3 - ■ 2 (E) >'6 - y3 -- 11 >'5 - yi 0 (Dummy) J6 - V4 > 1 (G) >6 - ys - - 12 (H) all y, unrestricted The dual formulation, though purely mathematical, reveals an interesting definition of the dual variables that is consistent with the precedence relationships of the CPM network. Specifically, consider the following definition: y; — Occurrence time of node In this case, w = y6 - y{ will represent the duration of the project. Each constraint is associated with an activity, and it specifies the precedence relationships among the different activities. For example, y2 - y\ ^ 5 is equivalent to y2 ^ y{ + 5, which says that y2, the earliest occurrence time for node 2, cannot be any earlier than time yl + 5. By-minimizing the objective function, we obtain the shortest time span in which all precedence relationships are satisfied. Also, notice that with the (new) practical meaning used to describe the dual variables, these variables can be restricted to nonnegative values. In fact, the start time, yb of the project can be set equal to zero, in which case the objective function reduces to minimizing w = y6. Setting yx = 0 is also consistent with the fact that one of the primal constraints is redundant. Under the nonnegativity restriction, the optimal dual solution (obtained by TORA) is given as w = 25, y\ = 0, y2 = 5, _v3 = 11, _y4 = 13, y5 = 13, y6 - 25 The solution shows that the duration of the project is w = 25 days. The critical activities correspond to the constraints that are satisfied as strict equations by the given solution; namely, A —> D —> Dummy —> H. These constraints are identified by their zero surplus variables or by realizing that if a constraint is satisfied in equation form in the solution, then its associated dual value must be positive. 6.6 CPM and PERT 283 Indeed, pairing the constraints with their associated dual solution (as determined by TORA) we get, Constraint A B c D E F Dummy G H Associated dual value 1 0 0 1 0 0 1 0 1 The conclusion is that the critical path is given as A —> D —> Dummy —> H. Observe that positive dual values will always equal 1 because a delay of one day in any critical activity will increase the duration of the project by one day (remember that the dual variable is interpreted as the worth per unit of a resource, see Section 4.3.1). PROBLEM SET 6.6D 1. Use LP to determine the critical path for the project network in Figure 6.55. 2. Use LP to determine the critical path for the project networks in Figure 6.56. 6.6.5 PERT Networks PERT differs from CPM in that it bases the duration of an activity on three estimates: 1. Optimistic time, a, which assumes that execution goes extremely well. 2. Most likely time, m, which assumes that execution is done under normal conditions. 3. Pessimistic time, b, which assumes that execution goes extremely poorly. The range (a, b) is assumed to enclose all possible estimates of the duration of an activity. The estimate m thus must lie somewhere in the range (a, b). Based on the estimates, the average duration time, D, and variance, v, are computed as follows: jr _ a + 4m + b 6 CPM calculations given in Sections 6.6.2 and 6.6.3 may be applied directly, with D replacing the single estimate D. It is now possible to estimate the probability that a node ;' in the network will occur by a prespecified scheduled time, 5(. Let e^ be the earliest occurrence time of nodeBecause the durations of the activities leading from the start node to node / are random variables, e-t also must be a random variable. Assuming that all the activities in the network are statistically independent, we can determine the mean, £{e,}, and variance, var {e;}, in the following manner. If there is only one path from the start node to node /, then the mean is the sum of expected durations, D, for all the activities along this path and the variance is the sum of the variances, v, of the same activities. On the other hand, if more than one path leads to node /, then it is necessary first to compute 284 Chapter 6 Network Models the statistical distribution of the duration of the longest path before the correct mean and variance can be calculated. This problem is rather difficult because it is equivalent to determining the distribution of the maximum of several random variables. A simplifying assumption thus calls for computing the mean and variance, E{ej} and var{e7}, as those of the path to node ; that has the largest sum of expected activity durations. If two or more paths have the same mean, the one with the largest variance is selected because it reflects the most uncertainty, hence leads to a more conservative estimate of probabilities. Once the mean and variance of the path to node;', E{ej\ and var{e,}, have been computed, the probability that node / will be realized by a preset time 5y is calculated using the following formula: f e, - E{e.} S, - E{e}\ I Vvarje,} Vvar-je,} > where z = Standard normal random variable _ S, - Efr} Vvar{e;} The standard normal variable z has mean 0 and standard deviation 1 (see Appendix C). Justification for the use of the normal distribution is that e, is the sum of independent random variables. According to the Central Limit Theorem (see Section 12.5.4), e, is approximately normally distributed. Example 6.6-6 Consider the project of Example 6.6-2. To avoid repeating critical path calculations, the values of a, m, and b in the table below are selected such that Dis = Dg for all i and in Example 6.6-2. Activity t-j (a, m, b) Activity H (a, m, b) A 1-2 (3,5,7) E 3-5 (1,2,3) B 1-3 (4,6,8) F 3-6 (9,11,13) C 2-3 (1,3,5) G 4-6 (1.1,1) D 2-4 (5,8,11) H 5-6 (10,12,14) The mean Dtj and variance Vq for the different activities are given in the following table. Note that for a dummy activity (a, b, m) = (0, 0, 0), hence its mean and variance also equal zero. Activity H Ay v„ Activity H D, A 1-2 5 .444 E 3-5 2 .111 B 1-3 6 .444 F 3-6 11 .444 C 2-3 3 .444 G 4-6 1 .000 D 2-4 8 1.000 II 5-6 12 .444 6.6 CPM and PERT 285 The next table gives the longest path from node 1 to the different nodes, together with their associated mean and variance. Node Longest path based on mean durations Path mean Path standard deviation 2 1-2 5.00 0.67 3 1-2-3 8.00 0.94 4 1-2-4 13.00 1.20 5 1-2-4-5 13.00 1.20 6 1-2-4-5-6 25.00 1.37 Finally, the following table computes the probability that each node is realized by a preset time, Sp specified by the analyst. Node / Longest path Path mean Path standard deviation S) Kj P{z £ if,} 2 1-2 5.00 0.67 5.00 0 .5000 3 1-2-3 8.00 0.94 11.00 3.19 .9993 4 1-2-4 13.00 1.20 12.00 -.83 .2033 5 1-2-4-5 13.00 1.20 14.00 .83 .7967 6 1-2-4-5-6 25.00 1.37 26.00 .73 .7673 TORA provides a module for carrying out PERT calculations. To use this module, select Project Planning => PERT program Evaluation and Review Verhnique from Main Menu. In the output screen, you have the option to select Activity Mean/var to compute the mean and variance for each activity or pert calcai ations to compute the mean and variance of the longest path to each node in the network. Figure 6.61 shows TORA output for the PERT calculations of Example 6.6-6 (file ch6ToraPERTEx6-6-6.txt). PROBLEM SET 6.6E 1. Consider Problem 2, Set 6.6b. The estimates (a, m, b) are listed below. Determine the probabilities that the different nodes of the project will be realized without delay. Project (a) Project (b) Activity (a, m, b) Activity (a, m, b) Activity (a, m, b) Activity (a, m, b) 1-2 (5,6,8) 3-6 (3,4,5) 1-2 (1,3.4) 3-7 (12,13,14) 1-4 (1.3,4) 4-6 (4,8,10) 1-3 (5,7,8) 4-5 (10,12,15) 1-5 (2,4,5) 4-7 (5,6,8) 1-4 (6.7,9) 4-7 (8,10,12) 2-3 (4,5,6) 5-6 (9,10,15) 1-6 (1,2,3) 5-6 (7,8,11) 2-5 (7,8.10) 5-7 (4,6,8) 2-3 (3,4.5) 5-7 (2,4,8) 2-6 (8,9,13) 6-7 (3,4,5) 2-5 (7,8,9) 6-7 (5,6,7) 3-4 (5,9,19) 3-4 (10,15,20) 286 Chapter 6 Network Models PROJECT PLANNING -pfBI/CHM FIGURE 6.61 TORA PERT calculations for Example 6.6-6 SELECTED REFERENCES Ahuja, R., T. Magnati, and J. Orlin, Network Flows: Theory, Algorithms, and Applications, Prentice Hall Upper Saddle River, NJ, 1993. Bazaraa, M., J. Jarvis, and H. Sherali, Linear Programming and Network Flow, 2nd ed., Wiley. New York, 1990. Evans, J. R., and E. Minieka, Optimization Algorithms for Networks and Graphs, 2nd ed., Marcel Dekker, New York, 1992. Murty, K., Network Programming, Prentice Hall, Upper Saddle River, NJ, 1992. COMPREHENSIVE PROBLEMS 6.1 An outdoors person who lives in San Francisco (SF) wishes to spend a 15-day vacation visiting four national parks: Yosemite (YO), Yellowstone (YE), Grand Teton (GT), and Mount Rushmore (MR). The tour, which starts and ends in San Francisco, visits the parks in the following order and includes a 2-day stay at each park: SF —> YO —> YE —> GT —> MR —> SF. Travel from one park location to another is either by air or car. Each leg of the trip takes 1/2 day if traveled by air. Travel by car takes 1/2 day from SF to YO, 3 days from YO to YE, one day from YE to GT, 2 days from GT to MR, and 3 days from MR back to SF. The trade-off is that car travel generally costs less but takes longer. Considering the fact that the individual must return to work in 15 days, the objective is to make the tour as Comprehensive Problems 287 inexpensive as possible within the 15-day limit. The following table provides the one-way cost of traveling by car and air. Determine the mode of travel on each leg of the tour. Air travel cost ($) to Car travel cost ($) to From SF YO YE GT MR SF YO YE GT MR SF _ 150 350 380 450 - 130 175 200 230 YO 150 - 400 290 340 130 - 200 145 180 YE 350 400 - 150 320 175 200 - 70 150 GT 380 290 150 - 300 200 145 70 - 100 MR 450 340 320 300 - 230 180 150 100 - 6.2'- A benefactor has donated valuable books to the Springdale Public Library. The books come in four heights: 12,10, 8, and 6 inches. The head librarian estimates that 12 feet of shelving will be needed for the 12-inch books. 18 feet for the 10-inch ones, 9 feet for the 8-inch books, and 10 feet for the 6-inch ones. The construction cost of a shelf includes both a fixed cost and a variable cost per foot length as the following table shows. Shelf height (in) Fixed cost (S) Variable cost ($/ft length) 12 25 5.50 10 25 4.50 8 22 3.50 6 22 2.50 Given that smaller books can be stored on larger shelves, how should the shelves be designed? 6.3 A shipping company wants to deliver five cargo shipments from ports A, B, and C to ports D and E. The delivery dates for the five shipments are Shipment Shipping route Delivery date 1 AXoD 10 2 AXoE 15 3 BxoD 4 4 BXoE 5 5 CxoE 18 The following table gives trip times (in days) between ports (the return trip is assumed to take less time). A B C D E A 3 4 B 3 2 C 3 5 D 2 2 2 E 3 1 4 6Based on A. Ravindran, "On Compact Storage in Libraries," Opsearch, Vol. 8, No. 3, pp. 245-52,1971. 288 Chapter 6 Network Models The company wants to determine the minimum number of ships needed to carry out the given shipping schedule. 6.47 Several individuals have set up separate brokerage firms that traded in highly speculative stocks. The brokers operated under a loose financial system that allowed extensive inter-brokerage transactions, including buying, selling, borrowing, and lending. For the group of brokers as a whole, the main source of income was the commission they received from sales to outside clients. Eventually, the risky trading in speculative stocks became unmanageable, and all the brokers declared bankruptcy. At the time the bankruptcy was declared, the financial situation was that all brokers owed money to outside clients and the interbroker financial entanglements were so complex that almost every broker owed money to every other broker in the group. The brokers whose assets could pay for their debts were declared solvent. The remaining brokers were referred to a legal body whose purpose was to resolve the debt situation in the best interest of outside clients. Because the assets and receivables of the nonsolvent brokers were less than their payables, all debts were prorated. The final effect was a complete liquidation of all the assets of the nonsolvent brokers. In resolving the financial entanglements within the group of nonsolvent brokers, it was decided that the transactions would be executed only to satisfy certain legal requirements because, in effect, none of the brokers would be keeping any of the funds owed by others. As such, the legal body requested that the number of interbroker transactions be reduced to an absolute minimum. This means that if A owed B an amount X, and B owed A an amount Y, the two "loop" transactions were reduced to one whose amount is \X - Y\. This amount would go from A to B if X > Y and from B to A if Y > X. If X = Y, the transactions were completely eliminated. The idea was to be extended to all loop transactions involving any number of brokers. How would you handle this situation? Specifically, you are required to answer two questions. 1. How should the debts be prorated? 2. How should the number of interbroker transactions be reduced to a minimum? 7Based on H. Tana,"Operations Research Analysis of a Stock Market Problem," Computers and Operations Research, Vol. 18, No. 7, pp. 597-602,1991. CHAPTER 7 Advanced Linear Programming This chapter presents a matrix version of linear programming that allows the development of a number of computationally efficient algorithms: revised simplex method, upper and lower bounding, decomposition, and parametric programming. The chapter also presents the totally different Karmarkar interior-point algorithm, which appears quite efficient in handling very large LPs. SIMPLEX METHOD FUNDAMENTALS In linear programming, the feasible solution space is said to form a convex set if the line segment joining any two distinct feasible points also falls in the set. An extreme point of the convex set is a feasible point that cannot lie on a line segment joining any two distinct feasible points in the set. Actually, extreme points are the same as corner points, the more apt name used in Chapters 2,3, and 4. Figure 7.1 illustrates two convex sets. Set (a), which is typical of the solution space of a linear program, is convex (with six extreme points), whereas set (b) is nonconvex. In the graphical LP solution given in Section 2.3, we demonstrated that the optimum solution can always be associated with a feasible extreme (corner) point of the solution space. This result makes sense intuitively because in LP every feasible point FIGURE 7.1 Examples of a convex and a nonconvex set (a) (b) 289 290 Chapter 7 Advanced Linear Programming can be determined as a function of the extreme points. For example, in convex set (a) of Figure 7.1, given the extreme points X1,X2,X3,X4,X5, and X6, a feasible point X can be expressed as a convex combination of the extreme points using X = otjXi + 0:2X2 + 0:3X3 + 0:4X4 + 0:5X5 + 0:5X5 where + a2 + 0:3 + 014 + (X5 + otg = 1 a, > 0,/ = 1,2, ...,6 This observation shows that extreme points provide all that is needed to define the solution space completely. Example 7.1-1 Show that the following set is convex: C = {{xux2)\x] < 2,x2 < 3,JCi > 0,x2 > 0} Let Xj = {x\,.xl} and X2 = {17,*?} be any two distinct points in C. If C is convex, then X = (x,,x2) = oi^Xj + a2X2 must also be in C. To show that this is true, we need to show that all the constraints of C are satisfied by the line segment X—that is, x{ = (X\x\ + a2x\ ^ 0^(2) 4- a2(2) = 2 x2 = a-\Xl2 + a2x\ :£ aj(3) + a2(3) = 3 Thus, jt] s 2 and x2 "; 3 because a! + a2 = 1. Additionally, the nonnegativity conditions are satisfied because 04 and a2 are nonnegative. PROBLEM SET 7.1A 1. Show that the set Q = {x1,x2\x{ + x2 -S l,Xj s 0,x2 ' 0} is convex. Is the nonnegativity condition essential for the proof? 2. Show that the set Q = {xx,x2 i, > 1 on, 2 2} is not convex. 3. Determine graphically the extreme points of the following convex set: Q = {x,,x2 j Xj + x2 < 2,.v, > 0,.*2 s 0} Show that the entire feasible solution space can be determined as a convex combination of its extreme points. Hence conclude that any convex (bounded) solution space is totally defined once its extreme points are known. 4. In the solution space in Figure 7.2 (drawn to scale), express the interior point (3,1) as a convex combination of the extreme points A, B, Q and D where each extreme point carries a strictly positive weight. 7.1.1 From Extreme Points to Basic Solutions It is convenient to express the general LP problem in equation form (see Section 3.1) using matrix notation. Define X as an n-vector representing the variables, A as an 7.1 Simplex Method Fundamentals 291 *2 FIGURE 7.2 Solution space for Problem 4, Set 7.1a (m X rc)-matrix representing the constraint coefficients, and C as an ^-vector representing the objective function coefficients. The LP is then written as Maximize or minimize z = CX subject to AX = b X > 0 Using the format of Chapter 3 (see also Figure 4.1), the rightmost m columns of A always can be made to represent the identity matrix I through proper arrangements of the slack/artificial variables associated with the starting basic solution. A basic solution of AX = b is determined by setting n — m variables equal to zero, and then solving the resulting m equations in the remaining m unknowns, provided that the resulting solution is unique. Given this definition, the theory of linear programming establishes the following result between the geometric definition of extreme points and the algebraic definition of basic solutions: Extreme points of {X 1 AX = b} <=> Basic solutions of AX = b The relationship means that the extreme points of the LP solution space are totally defined by the basic solutions of the system AX = b, and vice versa. Thus, we conclude that the basic solutions of AX = b contain all the information we need to determine the optimum solution of the LP problem. Furthermore, if we impose the nonnegativity restriction, XsO, the search for the optimum solution is confined to the feasible basic solutions only. To formalize the definition of a basic solution, the system AX = b can be expressed in vector form as follows: JTPjXj = b 292 Chapter 7 Advanced Linear Programming The vector P, is the jth column of A. A subset of m vectors is said to form a basis, B, if, and only if, the selected m vectors are linearly independent. In this case, the matrix B is nonsingular. If Xs is the set of m variables associated with the vectors of nonsingular B, then XB must be a basic solution. In this case, we have BX/( = b Given the inverse B 1 of B, we then get the corresponding basic solution as XB = B_1b If B_1b s 0, then XB is feasible. The definition, of course, assumes that the remaining n — m variables are nonbasic at zero level. The previous result shows that in a system of m equations and n unknowns, the maximum number of (feasible and infeasible) basic solutions is given by n\ m ~ m\(n - m)\ Example 7.1-2 Determine and classify (as feasible and infeasible) all the basic solutions of the following system of equations. The following table summarizes the results. The inverse of B is determined by using one of the methods in Section A.2.7. B BXB = b Solution Status ™ g m - © (s) ■ (111 ■ (!) ~ (P!.P3) (Not a basis) — — We can also investigate the problem by expressing it in vector form as follows: l\ . ( 3\ , I-\\ (A 2/i + {-2p+{-2p \2 Each of Pi, P2, P3, and b is a two-dimensional vector, which can be represented generi-cally as (al,a2)T. Figure 7.3 graphs these vectors on the (fl^a^-plane. For example, for b = (4,2)T,fll = 4anda2 = 2. Because we are dealing with two equations (m = 2), a basis must include exactly two vectors, selected from among Pj,P2, and P3. From Figure 7.3, the combinations (Pl5P2) and (P2,P3) form bases because their associated vectors are independent. In the combination (Pi,P3) the two vectors arc dependent, and hence do not constitute a basis. 7.1 Simplex Method Fundamentals 293 3 - FIGURE 7.3 Vector representation of LP solution space Algebraically, a combination forms a basis if its determinant is not zero (see Section A.2.5). The following computations show that the combinations (Pi,P2) and (P2, P3) are bases, and the combination (Pb P3) is not. det^P,) = det (l j£\ = (1 X -2) - (2 X 3) det(P2,P3) = det = (3 X -2) - (-2 X detfPi.Pa) = det (l "^J = (1 X -2) - (2 X -1) = 0 We can take advantage of the vector representation of the problem to discuss how the starting solution of the simplex method is determined. From the vector representation in Figure 7.3, the basis B = (P],P2) can be used to start the simplex iterations because it produces the basic feasible solution Xfl = (xhx2)T- However, in the absence of the vector representation, the only course of action available to us is to try all possible bases (3 in this example, as shown above). The difficulty with trial and error is that it is not suitable for automatic computations. In a typical LP with thousands of variables and constraints where the use of the computer is a must, trial and error simply is not a practical option because of the tremendous computational overhead. To alleviate this problem, the simplex method always uses an identity matrix, B = I, to start the iterations. Why does a starting B = I offer an advantage? The answer is that it will always provide a feasible starting basic solution (provided that the right-hand side vector of the equations is nonnegative). You can see this result in Figure 7.3 by graphing the vectors of B = I and noting that they coincide with the horizontal and vertical axes, thus always guaranteeing a starting basic feasible solution. The basis B = I automatically forms part of the LP equations if all the original constraints are s. In other cases, we simply add the unit vectors where needed. This is what the artificial variables accomplish (Section 3.4). We then penalize these extraneous variables in the objective function to force them to zero level in the final solution. = -8*0 -1) = -8*0 294 Chapter 7 Advanced Linear Programming PROBLEM SET 7.1 B 1. In the following sets of equations, (a) and (b) have unique (basic) solutions, (c) has infinity of solutions, and (d) has no solution. Show how these results can be verified using graphical vector representation. From this exercise, state the general conditions for vector dependence-independence that lead to unique solution, infinity of solutions, and no solution. lxx + 3x2 = 1 2*1 — x2 = 2 2x, - Ax2 = 2 -Xi + 2x2 = 1 2. Determine graphically (using vectors) if each of the sets of equations below has a unique solution, infinity of solutions, or no solution. For the cases of unique solutions, indicate from the vector representation (and without solving the equations algebraically) whether the values of the X\ and x2 are positive, zero, or negative. (a) (c) x, + 3x2 = 2 xx + x2 = 3 X] + 6x2 = 4 X\ + 3x2 = 2 (b) («) (a) (c) (e) (b) (d) (f) x2 Consider the following system of equations: (l\ lo\ (l\ Determine if any of the following combinations forms a basis. (a) (P„P2,P3) (b) (P!,P2,P4) (c) (P2,P3,P4) (d) (P„P2,P3,P4) True or False? (a) The system BX (b) The system BX (c) The system BX b has a unique solution if B is nonsingular. b has no solution if B is singular and b is independent of B. b has infinity of solutions if B is singular and b is dependent. 7.1.2 Generalized Simplex Tableau in Matrix Form In this section, we use matrices to develop the general simplex tableau. This representation will be the basis for subsequent developments in the chapter. Consider the LP in equation form: Maximize z = CX, subject to AX = b,X > 0 The problem can be written equivalently as 7.1 Simplex Method Fundamentals 295 Suppose that B is a feasible basis of the system AX = b, X > 0, and let XB be the corresponding set of basic variables with CB as its associated objective vector. The corresponding solution may then be computed as follows (the method for inverting partitioned matrices is given in Section A.2.7): z\ = (l -CbY(0\ = (1 CBB-l\{0\ (CfiB_1b XBJ \0 B J \bj \0 B 1 J[bJ \ B b The general simplex tableau in matrix form can be derived from the original equations as follows: 'l c„b-'Yi -cVA/i CflB-'Vo' ,0 B_1 J\0 A ){x) ~ [0 B 1 Ab. Matrix manipulations yield the following set of equations: 1 C^A - C\/z\ = /CflB-'b 0 B_1A J\x) V B"lb Given P/ is the ;th vector of A, the simplex tableau column associated with variable x> can be represented as follows: Basic Xj Solution z C«B P - C) CflB 'b x„ B 'P, B b In fact, the tableau above is the same as the one we presented in Chapter 3 (see Problem 5 of Set 7.1c). An important property of this table is that the inverse, B_1, is the only element that changes from one tableau to the next, and that the entire tableau can be generated once B_1 is known. This point is important because the computational roundoff error in any tableau can be controlled by controlling the accuracy of B-1.This result is the main reason for the development of the revised simplex method in Section 7.2. Example 7.1-3 Consider the following LP: Maximize z = X\ + 4x2 + 7x3 + 5x4 subject to 2xl + x2 + 2*3 + 4x4 = 10 3x: — x2 — 2x3 + 6x4 = 5 Generate the simplex tableau associated with the basis B = (Pi,P2). Given B = (P,,P2), then XB = [xux2)T and CB = (1,4).Thus, 296 Chapter 7 Advanced Linear Programming We then get *- 4)( s)=© To compute the constraint columns in the body of the tableau, we have (j _;)(* _i 4 J)"(J ? ° o) Next, we compute the objective row as follows: CBpr1(P1,P2,P2,P4)] - C = (l,4)(j J 2 J)-Cl.4,7,5) = (P.0,1,-3) Finally, we compute the value of the objective function as follows: z = CCB b = CfiXB = (l,4)(jj = 19 Thus, the entire tableau can be summarized as shown below. Basic Xl x2 Xj X4 Solution z 0 0 1 -3 19 Xl 1 0 2 0 3 x2 0 1 0 2 4 The main conclusion from this example is that once the inverse, B-1, is known, the entire simplex tableau can be generated from B-1 and the original data of the problem. PROBLEM SET 7.1C 1. In Example 7.1-3, consider B = (P3, P4). Show that the corresponding basic solution is feasible, and then generate the corresponding simplex tableau. 2. Consider the following LP: Maximize z = 5xt + 12x2 + 4x:, subject to Xj + 2x2 + x3 + x4 = 10 ZX] - 2x2 — x3 =2 xl,x2,x3,xi s 0 Check if each of the following vector sets forms a (feasible or infeasible) basis: (P„ P2), (P,, P.,), (P3, P4) • 3. In the following LP, compute the entire simplex tableau associated with Xn = (x{,x2,x5)T : Minimize z = 2x^ + x2 7.2 Revised Simplex Method 297 subject to 4x, + 3x2 — x4 =6 x, + 2x2 + xs = 3 x-l,x2,x3,x4,x5 > 0 4. The following is an optimal LP tableau: Basic Xi x2 x3 x4 *5 Solution z 0 0 0 3 2 7 0 0 1 1 -1 2 x2 0 1 0 1 0 6 1 0 0 -1 1 2 The variables x3,x4, and x5 are slacks in the original problem. Use matrix manipulations to reconstruct the original LP, and then compute the optimum objective value. 5. In the generalized simplex tableau, suppose that X = (X^X,,)7, where X„ corresponds to a typical starting basic solution (consisting of slack and/or artificial variables) with B = I; and let C = (Ct, Cn) and A = (D, I) be the corresponding partitions of C and A, respectively. Show that the matrix form of the simplex tableau reduces to the following form, which is exactly the form used in Chapter 3. Basic x, xu Solution z CBB D - C, CBB 1 - Cn CUB b xs B 'D B 1 B b REVISED SIMPLEX METHOD Section 7.1.1 shows that the optimum solution of a linear program is always associated with a basic (feasible) solution. The simplex method search for the optimum starts by selecting a feasible basis, B, and then moving to another feasible basis, Bnexl, that leads to a better (or, at least, no worse) value of the objective function. Continuing in this manner, the optimum feasible basis is eventually reached. The iterative steps of the revised simplex method are exactly the same as in the tableau simplex method presented in Chapter 3. The main difference is that the computations in the revised method are based on matrix algebra rather than on row operations. The use of matrix algebra reduces the adverse effect of machine roundoff error by controlling the accuracy of computing B~ . This result follows because, as Section 7.1 shows, the entire simplex tableau can be computed from the original data and the current B"1. In the tableau simplex method of Chapter 3, each tableau is generated from the immediately preceding one, which tends to worsen the problem of roundoff error. 298 Chapter 7 Advanced Linear Programming 7.2.1 Development of the Optimality and Feasibility Conditions The general LP problem can be written as follows: n n Maximize or minimize z = 2c/*/SUDJect to S^;'*/ = ^'xi " U'/ = 1.2,...,« 7 = 1 ' 7 = 1 For a given basic vector Xfl and its corresponding basis B and objective vector CB, the general simplex tableau developed in Section 7.1.2 shows that any simplex iteration can be represented by the following equations: (xB),. + Scb-^M = (B"'b> where Zj - c, = CBB - c, The notation (V), is used to represent the ;th element of the vector V. Optimality Condition. From the z-equation given above, an increase in nonbasic x, above its current zero value will improve the value of z relative to its current value. CeB~b, only if its z,- - c, is strictly negative in the case of maximization and strictly positive in the case of minimization. Otherwise, Xj cannot improve the solution and must remain nonbasic at zero level. Though any nonbasic variable satisfying the given condition can be chosen to improve the solution, the simplex method uses a rule of thumb that selects the entering variable as the one with the most negative (most positive) Zj - Cj in case of maximization (minimization). Feasibility Condition. The determination of the leaving vector is based on examining the constraint equation associated with the ith basic variable. Specifically, we have (X/;),. + 2(B 1P/),x; = (B-'b),- When the vector P; is selected by the optimality condition to enter the basis, its associated variable x} will increase above zero level. At the same time, all the remaining nonbasic variables remain at zero level. Thus, the rth constraint equation reduces to (Xfi), = (B 'b), - (B-'P,),,y,. The equation shows that if (B_1P;), > 0, an increase in x-t can cause (Xa), to become negative, which violates the nonnegativily condition, (Xw), > 0 for all i.Thus, we have (B 'b), - (B-'P^x, > 0, for all i This condition yields the maximum value of the entering variable Xj as (B-'b), (B-'P,),. > 0 The basic variable responsible for producing the minimum ratio leaves the basic solution to become nonbasic at zero level. 7.2 Revised Simplex Method 299 PROBLEM SET 7.2A 1. Consider the following LP: Maximize z = cxxx + c2x2 + c3x3 + c4x4 subject to Vxxx + P2x2 + P3x3 + P4x4 = b XX,X2,X3,X4 2: 0 The vectors P,,P2,P3, and P4 are shown in Figure 7.4. Assume that the basis B of the current iteration is comprised of P, and P2. (a) If the vector P3 enters the basis, which of the current two basic vectors must leave in order for the resulting basic solution to be feasible. (b) Can the vector P4 be part of a feasible basis? 2. Prove that, in any simplex iteration, Zi — c, = 0 lor all the associated basic variables. 3. Prove that if z, — Cy > 0 (<0) for all the nonbasic variables x-t of a maximization (minimization) LP problem, then the optimum is unique. Else, if Zj — Cj equals zero for a non-basic Xp then the problem has an alternative optimum solution. 4. In an all-slack starting basic solution, show using the matrix form of the tableau that the mechanical procedure used in Section 3.3 in which the objective equation is set as n automatically computes the proper Zj — c, for all the variables in the starting tableau. 5. Using the matrix form of the simplex tableau, show that in an all-artificial starting basic solution, the procedure employed in Section 3.4.1 that calls for substituting out the artificial variables in the objective function (using the constraint equations) actually computes the proper zi — c, for all the variables in the starting tableau. 6. Consider an LP in which the variable xk is unrestricted in sign. Prove that by substituting xk = x+k - xl, where x"k and xk are nonnegative, it is impossible that x+k and xk will replace one another in an alternative optimum solution. 7. Given the general LP in equation form with m equations and zi unknowns, determine the maximum number of adjacent extreme points that can be reached from a nondegenerate extreme point of the solution space. b FIGURE 7.4 Vector representation of Problem 1, Set 7.2a 300 Chapter 7 Advanced Linear Programming 8. In applying the feasibility condition of the simplex method, suppose that xr = 0 is a basic variable and that x, is the entering variable. Why is it necessary for the leaving variable xr to have (BMP()r > 0? What is the fallacy if (B~'P,), < 0? (Hint: Basic x, must remain non-negative.) 9. In the implementation of the feasibility condition of the simplex method, what are the conditions for encountering a degenerate solution for the first time? For continuing to obtain a degenerate solution in the next iteration? For removing degeneracy in the next iteration? Explain the answer mathematically. 10. What are the relationships between extreme points and basic solutions under degeneracy and nondegeneracy. What is the maximum number of iterations that can be performed at a given extreme point assuming no cycling? 11. Consider the LP Maximize z = CX subject to AX < b,X > 0,b > 0 Suppose that the entering vector P; is such that at least one element of B 'P, is positive. (a) If P, is replaced with cxP,-, where a is a positive scalar, and provided x, remains the entering variable, find the relationship between the values of x} corresponding to P, and aPj. (b) Answer Part (a) if, additionally, b is replaced with pb, where p is a positive scalar. 12. Consider the LP Maximize z = CX subject to AX < b,X > 0,b > 0 After obtaining the optimum solution, it is suggested that a nonbasic variable x, can be made basic (profitable) by reducing the requirements per unit of ,t, for the different resources to £ of their original values, a > 1 . Because the requirements per unit are reduced, it is expected that the profit per unit of Xj will also be reduced to - of its original value. Will these changes make Xj a profitable variable? Explain. 13. Consider the LP Maximize z = CX subject to (A,I)X = b,X > 0 Define Xa as the current basic vector with B as its associated basis and Cs as its vector of objective coefficients. Show that if CB is replaced with the new coefficients Dfl, the values of Zj — C: for the basic vector XH will remain equal to zero. What is the significance of this result? 7.2.2 Revised Simplex Algorithm Having developed the optimality and feasibility conditions in Section 7.2.1, we now present the computational steps of the revised simplex method. Step 0. Construct a starting basic feasible solution and let B and CB be its associated basis and objective coefficients vector, respectively. Step 1. Compute the inverse B 1 by using an appropriate inversion method.1 'In most LP presentations, including the first six editions of this book, the product form method for inverting a basis (see Section A.2.7) is integrated into the revised simplex algorithm because the product form lends itself neatly to the revised computations where successive bases differ in exactly one column.The author has removed this detail from this presentation because it makes the algorithm appear more complex than it really is. Moreover, the product form is rarely used in the development of LP codes because it is not designed for automatic computations where machine roundoff error can be a serious issue. Normally, some advanced numeric analysis method, such as the LU decomposition method, is used to obtain the inverse. Incidentally. TORA matrix inversion module is based on LU decomposition. 7.2 Revised Simplex Method 301 Step 2. For each nonbasic variable Xj, compute Zj - cj = - c, If Zj — Cj■ > 0 in maximization (< 0 in minimization) for all nonbasic xp stop; the optimal solution is given by XB = B'b, z = CBXB Else, apply the optimality condition and determine the entering variable x, as the nonbasic variable with the most negative (positive) z, — c} in case of maximization (minimization). Step 3. Compute B_1P;. If all the elements of B~'Py are negative or zero, stop; the problem has no bounded solution. Else, compute B'b.Then for all the strictly positive elements of B_1P,, determine the ratios defined by the feasibility condition. The basic variable xt associated with the smallest ratio is the leaving variable. Step 4. From the current basis B, form a new basis by replacing the leaving vector P-with the entering vector P(. Go to step 1 to start a new iteration. Example 7.2-1 The Reddy Mikks model (Section 2.1) is solved by the revised simplex algorithm. The same model was solved by the tableau method in Section 3.3.2. A comparison between the two methods will show that they are one and the same. The equation form of the Reddy Mikks model can be expressed in matrix form as Maximize z = (5,4,0,0,0,0)(x^,x2,x3,x4,x5,x6)T subject to / 6 4 1 0 0 0\ x2 /24\ 1 2 0 1 0 0 6 -1 1 0 0 1 V 1 \ 0 1 0 0 0 w \2/ xl,x2,...,x6 s 0 We use the notation C = (chc2, ... ,c6) to represent the objective function coefficients and (Pi,P2, ... ,Pe) to represent the column vectors of the constraint equations. The right-hand side of the constraints gives the vector b. In the computations below, we will give the algebraic formula for each step and its final numeric answer without detailing the arithmetic operations. You will find it instructive to fill in the gaps in each step. Iteration 0. XB.. = (x3,x4,x5,x6),Cb0 = (0,0,0,0) B0 = (P3,P4,P5,P6) = I, Bo1 = I Thus, Xeo = B^b = (24,6,l,2)r,; = C, X/( = 0 302 Chapter 7 Advanced Linear Programming Optimality Computations: CwBo1 = (0,0,0,0) {Zj ~ <■■}. w = CbP?(PM - (c„c2) = (-5,-4) Thus, Pj is the entering vector. Feasibility Computations: XBa = {x3,x4,x5,x6)T = (24,6,1,2)7' B^P, = (6,1,-1,0)' Hence, / 24 6 1 , . = mm ~6~'T'~'_ I = min{4,6,-,-} = 4 and P4 becomes the leaving vector. The results above can be summarized in the familiar simplex tableau format. The presentation should help convince you that the two methods are essentially the same. Basic x, *2 x3 XA *5 X(, Solution - -5 -4 0 0 0 0 0 x3 6 24 x4 1 6 x5 -1 1 *6 0 2 Iteration 1. XB| = (x„x„x5,x6),CBl = (5,0,0,0) B, = (Pj, P4, P5, P6) / 6 0 0 0\ 110 0 -10 10 \ 0 0 0 1/ By using an appropriate inversion method (see Section A.2.6, in particular the product form method), the inverse is given as B7 = 1 6 0 0 0\ 1 6 1 0 0 1 6 0 1 0 0 0 0 1/ Thus, XB] = Bl'b = (4,2,5,2)''',* = CB|Xfl| = 20 7.2 Revised Simplex Method 303 Optimality Computations: CBf1 = (|,0,0,0) {z, ~ 4=23 = CBlBr1(P2,P3) - (c2,c3) = (-|,|) Thus, P2 is the entering vector. Feasibility Computations: XBi = (Xl,x4,xs,x6)T = (4,2,5.2)'' Brlp2= (iiii)r Hence, . / 4 2 5 2\ . , 3 - 3 ;c2 = mm < T,7>y>Tf = mm {6,2,3,2} = 5 and P4 becomes the leaving vector. (You will find it helpful to summarize the results above in the simplex tableau format as we did in iteration 0.) Iteration 2. XB, = {xux2,Xi,x6)\CBi = (5,4,0.0) B2 = (P„P2,P5,P6) / 6 4 0 0\ 12 0 0 -1110 \ 0 1 0 1/ Hence, /> _1 0 0> 1 8 0 0 3 8 ~4 1 0 \ I ~ 4 0 1/ Thus, XBi = B2'b = (3,f,f,|)r,z = CBXB; = 21 Optimality Computations: Cap? = (|,|,0,0) - 4=3,4 = C„B2-1(P3,P4) - (C3,C4) = (|,|) Thus, XB, is optimal and the computations end. Summary of Optimal Solution: Xy — 3,x2 = 1.5, z = 21 304 Chapter 7 Advanced Linear Programming PROBLEM SET 7.2B 1. In Example 7.2-1, summarize the data ol iteration 1 in the tableau format of Section 3.3. 2. Solve the following LPs by the revised simplex method: (a) Maximize z = 6xx — 2x2 + 3x3 subject to 2xi — x2 + 2x3 - 2 xx + 4x3 < 4 xbx2,x3 > 0 (b) Maximize z = 2xx + x2 + 2x3 subject to Axx + 3x2 + 8x3 < 12 4x, + x2 + 12x3 < 8 4.x| - x, + 3x3 < 8 X!,X2,X3 S: 0 (c) Minimize z = 2xx + x2 subject to 3xi + x2 = 3 4x, + 3x2 > 6 Xj + 2x2 s 3 x,,x2 > 0 (d) Minimize z = 5xi — 4x2 + 6x3 + 8x4 subject to x, + 7x2 + 3x3 + 7x4 < 46 3X| - x2 + x3 + 2x4 s 20 2*1 + 3x2 - x3 + x4 > 18 X!,X2,X3,X4 > 0 3. Solve the following LP by the revised simplex method given the starting basic feasible vector XK) = (x2,x4,xs)T. Minimize z = 7x2 + llx3 - 10x4 + 26x6 subject to x2 - x3 + x< + xfi = 6 x2 ~ x3 + x4 + 3x6 = 8 X; + x2 — 3x3 + x4 + x5 = 12 X[, x2,x3, x4, x^, X5 — 0 7.3 Bounded Variables Algorithm 305 4. Solve the following using the two-phase revised simplex method: (a) Problem 2-c (b) Problem 2-d (c) Problem 3 (ignore the given starting Xfl|i) 5. Revised Dual Simplex Method. The steps of the revised dual simplex method (using matrix manipulations) can be summarized as follows: Step 0. Let B0 = I be the starting basis and that at least one of the elements of XB( is negative (infeasible). Step 1. Compute XB = B_1b, the current values of the basic variables. Select the leaving variable xr as the one having the most negative value. If all the elements of XD are nonnegative, stop; the current solution is feasible (and optimal). Step 2. (a) Compute Zj - Cj = CSB ~P; - c; for all the nonbasic variables xr (b) For all the nonbasic variables x-t, compute the constraint coefficients (B-1?,),. associated with the row of the leaving variable xr. (c) The entering variable is associated with 8 = min i ,(B-'P,)r < 0 (B-'P,),- If all (B lF.)f :' 0, no feasible solution exists. Step 3. Obtain the new basis by interchanging the entering and leaving vectors ( P; and Pr). Compute the new inverse and go to Step 1. Apply the method to the following problem: Minimize z = 2xl + x2 subject to 3jC] + i2a3 4.V, + 3x2 s 6 X] + x2 < 3 Xl,x2 s 0 BOUNDED VARIABLES ALGORITHM In LP models, variables may have explicit positive upper and lower bounds. For example, in production facilities, lower and upper bounds can represent the mhiiiiium and maximum demands for certain products. Bounded variables also arise prominently in the course of solving integer programming problems by the branch-and-bound algorithm (see Section 9.3.1). The bounded algorithm is efficient computationally because it accounts for the bounds implicitly. We consider the lower bounds first because it is simpler. Given X & L, we use the substitution X = L + X', X' > 0 and solve the problem in terms of X' (whose lower bound now equals zero). The original X is determined by back-substitution, which is legitimate because it guarantees that X = X' + L will remain nonnegative for all X' ^ 0. 306 Chapter 7 Advanced Linear Programming Next, consider the upper bounding constraints, X < U. The idea of direct substitution (i.e., X = U — X",X" > 0 ) is not correct because back-substitution, X = U - X", does not ensure that X will remain nonnegative. A different procedure is thus needed. Define the upper bounded LP model as Maximizes = {CX|(A,I)X = b,0 < X < U} The bounded algorithm uses only the constraints (A,I)X = b,X > 0 explicitly and accounts for X ^ U implicitly by modifying the simplex feasibility condition. Let XB = B *b be a current basic feasible solution of (A,I)X = b,X > 0 and suppose that, according to the (regular) optimality condition, P, is the entering vector. Then, given that all the nonbasic variables are zero, the constraint equation of the ith basic variable can be written as (XB)(- = (B1b)i-(B-1P/)/x/ When the entering variable Xj increases above zero level, (XB), will increase or decrease depending on whether (B-1?,), is negative or positive, respectively. Thus, in determining the value of the entering variable xh three conditions must be satisfied: 1. The basic variable (XB), remains nonnegative—that is, (XB), > 0 . 2. The basic variable (Xfl); does not exceed its upper bound—that is, (Xfl),- < (UB)(-, where UB comprises the ordered elements of U corresponding to XB. 3. The entering variable Xj cannot assume a value larger than its upper bound—that is, Xj ^ Uj, where m; is the jth element of U. The first condition (XB), > 0 requires that (B-'b), - (B-'P,),*, > 0 It is satisfied if (B 1b), jx = mm (B P;)j This condition is the same as the feasibility condition of the regular simplex method. Next, the condition (XB); s (UB), specifies that (B^b), - (B-'Yfrx, < (U«),- It is satisfied if J ^ H min< 1 (B-'P,), '* J Combining the three restrictions, x, enters the solution at the level that satisfies Xj = min (61,02,my) The change of basis for the next iteration depends on whether Xj enters the solution at level 61,82, or Uj. Assuming that (XB)r is the leaving variable, then we have the following rules: 7.3 Bounded Variables Algorithm 307 1. Xj = 9^ (XB), leaves the basic solution (becomes nonbasic) at level zero. The new iteration is generated in the normal simplex manner by using and (Xfl)r as the entering and the leaving variables, respectively. 2. Xj = 82: (XB),. becomes nonbasic at its upper bound. The new iteration is generated as in the case of Xj = 9i, with one modification that accounts for the fact that (Xfl), will be nonbasic at upper bound. Because the values of 6, and 92 are developed under the assumption that alt nonbasic variables are at zero level (convince yourself that this is the case!), we must convert the new non-basic (XB\ at upper bound to a nonbasic variable at zero level. This is achieved by using the substitution (XH)r = (UB)r - (XB),' , where (XB)r' as 0 . It is immaterial whether the substitution is made before or after the new basis is computed. 3. Xj = u- The basic vector Xw remains unchanged because Xj = u} stops short of forcing any of the current basic variables to reach its lower (= 0) or upper bound. This means that Xj will remain nonbasic but at upper bound. Following the argument just presented, the new iteration is generated by using the substitution Xi i/tj Xj • A tie among 91,92, and w, may be broken arbitrarily. However, it is preferable, where possible, to implement the rule for x, = w; because it entails less computations. The substitution Xi = w, — xj will change the original c,-, P(, and b to cj = -Cj,Yj = -P7, and b to b' = b - wPy. This means that if the revised simplex method is used, all the computations (e.g.,B_1,Xg, and z.} ~ cj) should be based on the updated values of C, A, and b at each iteration (see Problem 5, Set 7.3a for further details). Example 7.3-1 Solve the following LP model by the upper-bounding algorithm.2 Maximize z = 2>X\ + 5y + 2x3 subject to jCj 4- y + 2x3 < 14 2x{ + 4y + 3*3 < 43 0 < jc, < 4,7 < y < 10.0 < jc3 < 3 The lower bound on y is accounted for using the substitution y = x2 + 7. where 0 < x2 < 10 - 7 = 3 . We will not use the revised simplex method to carry out the computations, to avoid being "sidetracked" by the computational details. Instead, we will use the compact tableau form. Problems 5, 6, and 7, Set 7.3a address the revised version of the algorithm. 2You can use TORA's Linear z-roqrarirJns scl< bleti ubraic =^ Iterations ^ jcunded simplex lo produce the associated simplex iterations. 308 Chapter 7 Advanced Linear Programming Iteration 0. Basic x2 *3 x4 x5 Solution z -3 -5 -2 0 0 35 x4 1 1 2 1 0 7 *5 2 4 3 0 1 15 We have B = B"1 = I and XB = (x4,x5)T = B b = (7,15)r. Given x2 is the entering variable (z2 ~ c2 = -5), we get B P2 = (1,4)T which yields 7 151 6j = min -j J>^rf = 3-75, corresponding to x5 62 = oo (because B_1P2 > 0) Next, given the upper bound on the entering variable, x2 < 3, it follows that x2 = min {3.75,oo,3} = 3 [=u2) Because x2 enters at its upper bound (= u2 = 3),Xfl remains unchanged, and x2 becomes nonbasic at its upper bound. We use the substitution x2 = 3 — x{ to obtain the new tableau as Basic X, *2 *3 x4 X5 Solution z -3 5 -2 0 0 50 1 -1 2 1 0 4 *5 2 -4 3 0 1 3 The substitution in effect changes the original right-hand side vector from b = (7,15)r to b' = (4,3)' .This change should be considered in future computations. Iteration 1. The entering variable is xx. The basic vector XB and B~l (=1) are the same as in Iteration 0. Next, B-'Pi = (l,2)r [4 3l 0! = min < p. o f = 1-5, corresponding to basic x5 92 = oo (because B~1Vl > 0) Thus, X] = min {1.5,00,4} = 1.5 (=6,) Thus, the entering variable x1 becomes basic, and the leaving variable x5 becomes non-basic at zero level, which yields 7.3 Bounded Variables Algorithm 309 Basic x{ x3 X4 A'- Solution z 0 -1 5 0 3 1(19 x4 0 1 J 1 1 2 5 Xi 1 -2 3 0 1 2 3 Iteration 2. The new inverse is '1 B 1 Now 0 \ X„ = (x4,X])T = B b = (f,!f where b' = (4,3)r as computed at the end of Iteration 0. We select x[ as the entering variable, and, noting that P2 = -P2,weget BP, = (1, -2f Thus, 6j = min [I—| = 2.5, corresponding to basic x4 f | - 41 62 = min < —, _^ > = 1.25, corresponding to basic Xj We then have x2' = min {2.5,1.25,3} = 1.25 (=62) Because x, becomes nonbasic at its upper bound, we apply the substitution X] = 4 - x{ to obtain Basic *i *2 *3 x4 Xj Solution z 0 -1 s 0 3 109 0 -1 1 -2 1 2 1 0 1 2 i Next, the entering variable x{ becomes basic and the leaving variable x{ becomes nonbasic at zero level, which yields Basic x\ x{ *3 X4 xi Solution z 0 4 0 5 4 223 1 x4 -\ 0 4 1 1 4 1 1 x? 1 3 _4 0 1 1 s 4 310 Chapter 7 Advanced Linear Programming The last tableau is feasible and optimal. Note that the last two steps could have been reversed—meaning that we could first make xj basic and then apply the substitution x, = 4 - x{ (try it!). The sequence presented here involves less computations, however. The optimal values of xx,x2, and x3 are obtained by back-substitution as xx -ut - x[ = 4 - 0 = 4, x-z = Ui - x( = 3 - | = I, and x3 = 0. Finally, we get y = l2+ x2 = 7 + | = The associated optimal value of z is ^p. PROBLEM SET 7.3A 1. Consider the following linear program: Maximize z = 2xx + x2 subject to xi + x2 S 3 0 < Xi < 2,0 < x2 < 2 (a) Solve the problem graphically, and trace the sequence of extreme points leading to the optimal solution. (b) Solve the problem by the upper bounding algorithm and show that the method produces the same sequence of extreme points as in the graphical optimal solution (use TORA to generate the iterations). (c) How does the upper-bounding algorithm recognize the extreme points? 2. Solve the following problem by the bounded algorithm: Maximize z = 6x1 + 2x2 + 8x3 + 4x4 + 2x5 + 10xt subject to 8xl + x2 + &x3 + 2x4 + 2x5 + 4x6 < f 3 0 < X], < 1,;' = 1,2,...,6 3. Solve the following problems by the bounded algorithm: (a) Minimize z = &xx — 2x2 — 3x3 subject to 2xi + 4x2 + 2x3 < 8 x1 — 2x2 + 3x3 < 7 0 < xx < 2,0 < x2 < 2,0 < x3 < f (b) Maximize z = 3xx + 5x2 + 2x3 subject to xx + 2x2 + 2x3 < 10 2x, + 4x2 + 3x3 < 15 0 < xy < 4,0 < x2 < 3,0 < x3 < 3 7.3 Bounded Variables Algorithm 311 4. In the following problems, some of the variables have positive lower bounds. Use the bounded algorithm to solve these problems. (a) Maximize z = 3x, + 2.v- - 2x3 subject to 2x- + x2 + x3 < 8 xx + 2x2 - x3 > 3 1 < xx < 3,0 < x2 < 3,2 < x3 (b) Maximize £ = x% + 2x2 subject to -Xi + 2x2 > 0 3#! + 2x2 < 10 —Xi + x2 < 1 1 < X; < 3,0 < x2 < 1 (c) Maximize z = 4x, + 2x2 + 6x3 subject to 4% - x2 < 9 —+ x2 + 2x3 < 8 -3x, + x2 + 4x3 < 12 1 < xx < 3,0 < x2 < 5,0 < x3 < 2 5. Consider the matrix definition of the bounded variables problem. Suppose that the vector X is partitioned into (X.,XM), where X„ represents the basic and nonbasic variables that are substituted at upper bound. The problem may thus be written as \ Using X„ = U„ - X„' where U„ is a subset of U representing the upper bounds for XM, let B (and XB) be the basis of the current simplex iteration after X„ has been substituted out. Show that the associated general simplex tableau is given as Basic X! Solution z C.,,B 'D. C- ~CaB D„ + C„ C^-'b' + C„.U„ xfl B D. -B Du B b where b' = b — D„U„. 6. In Example 7.3-1, do the following: (a) In Iteration 1, verify thatXs = (x4,Xi)r = (|,|)T by using matrix manipulation. (b) In Iteration 2, show how B-1 can be computed from the original data of the problem. Then verify the given values of basic x4 and x{ using matrix manipulation. 312 Chapter 7 Advanced Linear Programming 7. Solve part (a) of Problem 3 using the revised simplex (matrix) version for upper bounded variables. 8. Bounded Dual Simplex Algorithm. The dual simplex algorithm (Section 4.4) can be modified to accommodate the bounded variables as follows. Given the upper bound constraint x.j Uj for all; (if u, is infinite, replace it with a sufficiently large upper bound M), the LP problem is converted to a dual feasible (i.e., primal optimal) form by using the substitution Xj = - x\ , where necessary. Step 1. If any of the current basic variables (XB), exceeds its upper bound, use the substitution (Xs); = (UB),- - (Xfl);. Go to step 2. Step 2. If all the basic variables are feasible, stop. Otherwise, select the leaving variable xr as the basic variable having the most negative value. Go to step 3. Step 3. Select the entering variable using the optimality condition of the regular dual simplex method. Go to step 4. Step 4. Perform a change of basis. Go to step 1. Apply the given algorithm to the following problems: (a) Minimize z = 3x, - 2x2 + 2x3 subject to 2xl + x2 + x3 £ 8 -x-i + 2x2 + x, > 13 0 < Xj < 2,0 < x2 < 3,0 17 0 < x, < 2,0 s x2 < 3,x3 > 0 7.4 DECOMPOSITION ALGORITHM Consider the situation of developing a master corporate plan for several production facilities. Although each facility has its own independent capacity and production constraints, the different facilities are tied together at the corporate level by budgetary considerations. The resulting model includes two types of constraints: common, representing the corporate budgetary constraints, and independent, representing the internal capacity and production restrictions of each facility. Figure 7.5 depicts the layout of the resulting constraints for n activities (facilities). In the absence of the common constraints, all activities operate independently. The decomposition algorithm improves the computational efficiency of the problem depicted in Figure 7.5 by breaking it down into n subproblems that can be solved almost independently. We point out, however, that the need for the decomposition algorithm was more justifiable in the past when the speed and memory of the computer were modest. Today, computers boast impressive capabilities, and the need for the decomposition algorithm may not be warranted. Nevertheless, we present the algorithm here because of its interesting theoretical contribution. 7.4 Decomposition Algorithm 313 Independent constraints Common constraints . Activity: I Activjlv Activity FIGURE 7.5 Layout of a decomposable linear program The corresponding mathematical model is given as Maximize z = + C2X2 + ... 4- C„X„ subject to AiXj + A2X2 + ... + A„X„ < b0 DA < bj D2X2 < b2 D„X„ < b„ Xj sO,j = 1,2,...,« The slack and surplus variables are added as necessary to convert all the inequalities into equations. The decomposition principle is based on representing the entire problem in terms of the extreme points of the sets D;X, < by,Xy ^ 0j = 1,2,... ,n. To do so, the solution space described by each D(X; < b^X, > 0 must be bounded. This requirement can always be satisfied for any set;' by adding the artificial restriction 1X; < M, where M is sufficiently large. Suppose that the extreme points of D(X( < b,,X; s: 0 are defined as Xjk,k = 1,2, ...,Kj .We then have K, X; = 2P;*X;t' J = 1-2....,« k-\ where By* s 0 for all k and 2 3,* = 1 We can reformulate the entire problem in terms of the extreme points to obtain the following master problem: k=l Maximize = |)cixi^i* + 2C2X2,ß2, + ... + §C„X„*ß«* k-\ 314 Chapter 7 Advanced Linear Programming subject to 2 Pi* k=l K2 k-\ k=l = 1 2p 2/, = 1 =1 $jk > 0, for all j and The new variables in the master problem are (3;/.,. Once their optimal values, $*k , are determined, we can find the optimal solution to the original problem by back-substitution as Kj X;= 2PAj = 1,2,...,« /t=1 It may appear that the solution of the master problem requires prior determination of all the extreme points X;A., a difficult task indeed! Fortunately, it is not so. To solve the master problem by the revised simplex method (Section 7.2), we need to determine the entering and the leaving variables at each iteration. Let us start first with the entering variable. Given CB and B"1 of the current basis of the master problem, then for nonbasic (3/Vt, we have cjk — CflB Vp where Cjk = Cjkjk and ¥jk A;Xy, 0 \ 0 / Now, to decide which, if any, of the variable (By7i should enter the solution, we need to determine Zfk- ~ Cfk' = min {z;k - cjk} all / and k If Zfk' ~ Cj'k' < 0, then, according to the maximization optimality condition, (4.. must enter the solution; otherwise, the optimum has been reached. 7.4 Decomposition Algorithm 315 We still have not shown how zfk' ~ cfk' is computed numerically. The idea lies in the following identity min {zjk - cjk} = min{min{z;/£ - cjk}} all / and k j k The reason we are able to establish this identity is that each convex set D;X, < b,, Xj > 0 has its independent set of extreme points. In effect, what the identity says is that we can determine Zfk' — c-jk> in two steps: Step 1. For each convex set D,-X;- < b;,X7 > 0, determine the extreme point Xy7c* that yields the smallest zjk - cjk—that is, z-jk- - cjk = mink{zjk - cjk}. Step 2. Determine ~ Cfk~ = min{z/A.' - cjk•}. / From LP theory, we know that the optimum solution, when finite, must be associated with an extreme point of the solution space. Because each of the sets D;X; s b,, X; > 0 is bounded by definition, step 1 is mathematically equivalent to solving n linear programs of the form Minimize wt = {zj - cJ|DJX/ < b;-,X; > 0} Actually, the objective function wt is a linear function in Xy (see Problem 8, Set 7.4a). The determination of the entering variable py)t> in the master problem reduces to solving n (smaller) linear programs to determine the "entering" extreme point Xf . This approach precludes the need to determine all the extreme points of all n convex sets. Once the desired extreme point is located, all the elements of the column vector Yfk' are at hand. Given that information, we can then determine the leaving variable and, subsequently, compute the next B"1 using the revised simplex method computations. Example 7.4-1 Solve the following LP by the decomposition algorithm: Maximize z = 3x, + 5.t2 + x4 + xs subject to x1 + x2 + x, + x4 < 40 5a-: + x2 < 12 x3 + xA > 5 x3 + 5x4 < 50 X]jX2lx3,x4 ^ 0 316 Chapter 7 Advanced Linear Programming The problem has two subproblems that correspond to the following sets of variables: Xj — (x^x^, X2 = (x^x^ The master problem corresponding to the problem above may thus be represented as follows: Subproblem 1 Subproblem 2 Starting basic solution ßll ßl2 ■■■ ßl£, ßll ßn ••■ ß«, x§ jCfo x-j C-iXjj Ci&a ■■■ CjXliti C2X21 C2X22 . . . Cji-2K-, 0 -M -M A A A A,Xn A,X12 ... A,X1K) 1 1 ... 1 0 0 ... 0 A A A A2X2i A2X22 ■■■ A2X2K. 0 0 ... 0 1 1 ... 1 1 0 0 =40 0 10 =1 0 0 1 =1 C, = (3,5) A, = (1,1) Solution space, £ bj: 5X| + x2 s 12 Xi,*2 — 0 C2 = (l,l) A2 = (l,l) Solution space, D2X2 £ b2: x3 + x4 a 5 x3 + 5x4 £ 50 x3,x4 a 0 Notice that x5 is the slack variable that converts the common constraint to the following equation X7 + X* + Xa + Xi 40 Recall that subproblems 1 and 2 account for variables x1,x2,x3, and x4 only. This is the reason xs must appear explicitly in the master problem. The remaining starting basic variables, x6 and x7, are artificial. Iteration 0. XB = (x5,x6,x7)T= (40,l,l)r CB = (0,-M,-M),B = B 1 = I Iteration 1. Subproblem 1 (;' = 1). We have Zi ~ ci = CRB (0, -M, -M) -(3, 5) x2 = — 3x] — 5x2 — M Thus, the corresponding LP is Minimize wx = -3x1 - 5x2 - M 7.4 Decomposition Algorithm 317 subject to 5x, + x2 < 12 Xy,X2 — 0 The solution of this problem (by the simplex method) yields X„ = ((L12)r,zl - c\ = w\ = -60 - M Subproblem 2 (j = 2). The associated linear program is given as Minimize z2 - c2 = CfiB" = (0, -M, -M) — X ^ subject to x3 + x4> 5 x3 + 5x4 < 50 x3,x4 0 The optimal solution of the problem yields X21 = (50,0)',z: - c2 = -50 "(1, 1) - M Because the master problem is of the maximization type and z\ - c\ < z2 - c2 and z\ - c[ < 0, it follows that (3U associated with extreme point Xn must enter the solution. To determine the leaving variable, 1 I 0 (1,1) 1 0 / /12\ 1 \0/ Thus, B^Pu = (12, l,0)r. Given Xfl = (x5,x6,x7)T = (40,1, l)r, it follows that x6 (an artificial variable) leaves the basic solution (permanently). The new basis is determined by replacing the vector associated with x6 with the vector Pn, which gives (verify!) /l 12 0^ B = 0 10 \0 0 1 Thus, B (1 0 318 Chapter 7 Advanced Linear Programming The new basic solution is XB = (x5, (3n,x7)7, = B-l(40,l,l)r = (28,1,1/ CB = (0,CiXu,-M) = (0,611 -M) Iteration 2. Subproblem 1 (j = /). The associated objective function is Minimize w1 = —3x, — 5x2 + 60 (verify!). The optimum solution yields z\ - c\ = wx = 0, which means that none of the remaining extreme points in subproblem 1 can improve the solution to the master problem. Subproblem 2 (/' = 2). The associated objective function is (coincidentally) the same as for / = 2 in Iteration 1 (verify!). The optimum solution yields X22 = (50,0)',^ - c2 = -50 - M Note that X22 is actually the same extreme point as X21 . We use the subscript 2 for notational convenience to represent Iteration 2. From the results of the two subproblems, z\ - c2 < 0 indicates that (322 associated with X22 enters the basic solution. To determine the leaving variable, consider / A,X22^ ^50\ 0 = = 0 I 1 / \1 \ 1 / Tnus,B_1P22 = (50,0,l)r. Because XB = (x5,pn,xv)r = (28, l,l)r,x5 leaves. The new basis and its inverse are given as (verify!) /50 12 o\ B = 0 1 0 \ 1 0 1/ / h 12 50 o\ B = 0 1 0 12 50 V XB = (P22,pn,x7)r = B-X40,l,lf = &AMY CB = (C2X22,cXi,-M) = (50,60, -M) Iteration 3. Subproblem 1 (j = 1). You should verify that the associated objective function is Minimize wx = (-5 - 2)x1 + {% - 4)x2 - + 48 The associated optimum solution is X13 = (0,0f,Z; - c\ = --f + 48 7.4 Decomposition Algorithm 319 Subproblem 2 (j = 2). The objective function can be shown to equal (verify!) Minimize w2 = $j)(x3 + x4) - M The associated optimum solution is X23 = (5.0)'.-. - c- 9,1/ " 10 Nonbasic Variable x5. From the definition of the master problem, zt - ct of xs must be computed and compared separately. Thus, z5 - c5 = CBB Ps - c5 = (1 + |,48- if, -iW)(l,0, Of -0 = 1 + 50 Thus, x5 cannot improve the solution. From the preceding information, fi-23 associated with X23 enters the basic solution. To determine the leaving variable, consider /a2xJ w 0 = = 0 I 1 I \ 1 1 I1/ Thus,B_1P23 = (p,0,^)r . Given XB = ((522, (3n,jc7)r = (i,l,i)'r, the artificial variable x7 leaves the basic solution (permanently). The new basis and its inverse are thus given as (verify!) B = B = \ _L 1? si \ 45 45 4. xB = (^22,^MT = B-'(40,i,if = (|,i,|y CB = (CjX^.CjX,,,^^) = (50,60,5) Iteration 4. Subproblem 1 (j = 1). wl = -2xx - 4x2 + 48. It yields z\ - c\ = w\ = 0. Subproblem 2 (/' = 2). w2 = 0x3 + 0x4 + 48 = 48. 1 12 -JA 45 45 0 1 0 1 12 50 45 45 45/ Nonbasic Variable xs : z5 - c5 = 1. The preceding information shows that Iteration 3 is optimal. 320 Chapter 7 Advanced Linear Programming We can compute the optimum solution of the original problem by back-substitution: XJ = (xhx2)T = BUXU = 1(0,12)T = (0,12)7 ^2 = (-^3) ^4) = P 22^22 + P 23^23 = §)(50,0f + §)(5,0f = (28,0)r The optimum value of the objective function can be obtained by direct substitution. PROBLEM SET 7.4A 1. In each of the following cases, determine the feasible extreme points graphically and express the feasible solution space as a function of these extreme points. If the solution space is unbounded, add a proper artificial constraint. (a) x, + 2x2 — 6 2x, + x2 < 8 —Xy + X2 < 1 x2 < 2 Xi,x2 ■- 0 (b) 2x, + x2 < 2 3x, + 4x2 > 12 xhx2 > 0 (c) x, - x, < 10 2*1 < 40 xux2 > 0 2. In Example 7.4-1, the feasible extreme points of subspaces D1X] = b^X! > Oand D2X2 = b2,X, 2 0 can be determined graphically. Use this information to express the associated master problem explicitly. Then show that the application of the simplex method to the master problem produces the same entering variable (3^ as that generated by solving subproblems 1 and 2. Hence, convince yourself that the determination of the entering variable p;)t is exactly equivalent to solving the two minimization subproblems. 3. Consider the following linear program: Maximize z = x, + 3x2 + 5x3 + 2x4 subject to Xj + 4x2 < 8 2xi + x2 < 9 5xj + 3x2 + 4x3 > 10 7.4 Decomposition Algorithm 321 x3 - 5x4 s 4 x3 + xx < 10 X,,X2,X3,X4 > 0 Construct the master problem explicitly by using the extreme points ol the subspaces, and then solve the resulting problem directly by the simplex method. 4. Solve Problem 3 using the decomposition algorithm and compare the two procedures. 5. Apply the decomposition algorithm to the following problem: Maximize z = 6x, + lx2 + 3x3 + 5x4 + x5 + x6 subject to Xj + x2 + x3 + x4 + xs + x6 < 50 x, + x2 < 10 x2 <8 5*3 + x4 s 12 x5 + x6 > 5 xs + 5xb < 50 6. Indicate the necessary changes for applying the decomposition algorithm to minimization LPs. Then solve the following problem: Minimize z = 5xx + 3x2 + 8x3 — 5x4 subject to Xj + X3 + Xj + I4 2 25 5x, + x2 < 20 Sxx — x2 > 5 x3 + x4 = 20 xl,x2,x3,x4 s 0 7. Solve the following problem by the decomposition algorithm: Minimize z = lOyj + 2y2 + 4y3 + 8y4 + y5 subject to y1 + 4y2 - y3 >8 2yi + y2 + y3 22 3v, + y4 + y5 > 4 Vi + 2y4 - ys > 10 vi,y2,y3,y4,vj a 0 (ffj'nC Solve the dual problem first by decomposition.) 322 Chapter 7 Advanced Linear Programming 8. In the decomposition algorithm, suppose that the number of common constraints in the original problem is r. Show that the objective function for subproblem;' can be written as Minimize w}- = Zj - c, = (CBRA; - C;)X; + CflVr+/ The vector R represents the first r columns of B"1 and Vr+, is its (r + j) th column. 7.5 DUALITY We have dealt with the dual problem at an elementary level in Chapter 4. This section presents a more rigorous treatment of duality and allows us to verify the primal-dual relationships that formed the basis for sensitivity analysis in Chapter 4. The presentation also lays the foundation for the development of parametric programming. 7.5.1 Matrix Definition of the Dual Problem Suppose that the primal problem in equation form with m constraints and n variables is defined as subject to Maximize z = CX AX = b X > 0 Letting the vector Y = (yl5v2, ... ,ym) represent the dual variables, the rules in Table 4.2 produce the following dual problem: Minimize w = Yb subject to YA > C Y unrestricted Note that some of the constraints YA > C may override unrestricted Y. PROBLEM SET 7.5A 1. Prove that the dual of the dual is the primal. 2. Suppose that the primal is given as min z = {CX| AX sponding dual problem. 7.5.2 Optimal Dual Solution b,X > 0}. Define the corre- This section establishes relationships between the primal and dual problems and shows how the optimal dual solution can be determined from the optimal primal solution. Let B be the current optimal primal basis, and define CB as the objective function coefficients associated with the optimal vector XB. 7.5 Duality 323 Theorem 7.5-1. (Weak Duality Theory). For any pair of feasible primal and dual solutions (X, Y), the value of the objective function in the minimization problem sets an upper bound on the value of the objective function in the maximization problem. For the optimal pair (X*, Y*), the values of the objective functions in the two problems are equal. Proof. The feasible pair (X, Y) satisfies all the restrictions of the two problems. Premultiplying both sides of the constraints of the maximization problem with (unrestricted) Y, we get YAX = Yb = w (1) Also, for the minimization problem, postmultiplying both sides by X(>0), we get YAX CX or YAX > CX = z (2) (The nonnegativity of the vector X is essential for maintaining the direction of the inequality.) Combining (1) and (2), we get z < tv for my feasible pair (X, Y). Note that the theorem does not depend on labeling the problems as primal or dual. What is important is the sense of optimization in each problem. Specifically, for any pair of feasible solutions, the objective value in the maximization problem does not exceed the objective value in the minimization problem. The implication of the theorem is that, given z ^ w for any feasible solutions, the maximum of z and the minimum of w are achieved when the two objective values are equal. A consequence of this result is that the "goodness" of any feasible primal and dual solutions relative to the optimum may be checked by comparing the difference (vv - z) to LJj^L. The smaller the ratio V,,7' •tne closer the two solutions are to being optimal. The suggested rule of thumb does not imply that the optimal objective value is .- - u 2 What happens if one of the two problems has an unbounded objective value? The answer is that the other problem must be infeasible. For if it is not, then both problems have feasible solutions, and the relationship z < w must hold—an impossible result because either z = + oo or w = - oo by assumption. The next question is: If one problem is infeasible, is the other problem unbounded? Not necessarily. The following counterexample shows that both the primal and the dual can be infeasible (verify graphically!): Primal. Maximize z = {xx + x2 \x-i — x2 - —l,—xl + x2 " - —l,xhx2 ^ 0} Dual. Minimize w = {—y1 — y2\y>i — y2 ^ 1,— y, + y2 > l,yi,y2 s 0} Theorem 7.5-2. Given the optimal primal basis B and its associated objective coefficient vector CB , the optimal solution of the dual problem is Proof. The proof rests on verifying two points: Y = CBB 1 is a feasible dual solution and z = w per Theorem 7.5-1. 324 Chapter 7 Advanced Linear Programming The feasibility of Y = CflB 1 is guaranteed by the optimality of the primal, Zj - c, > 0 for all /'—that is, CBB A - C > 0 (See Section 7.2.1.) Thus, YA - C > 0 or YA > C , which shows that Y = CgB"1 is a feasible dual solution. Next, we show that the associated w - z by noting that w = Yb = CsB_1b (1) Similarly, given the primal solution XB = R lb, we get z = CBXn = CaB b (2) From relations (1) and (2), we conclude z = w. The dual variables Y = CBB 1 are sometimes referred to as the simplex multipliers. They are also known as the shadow prices, a name that evolved from the economic interpretation of the dual variables (see Section 4.3.1). Given P, is the jth column of A, we note from Theorem 7.5-2 that Zj - c, = CBB P, - Cj = YP, - Cj represents the difference between the left- and right-hand sides of the dual constraints. The maximization primal starts with z, - c, < 0 for at least one ;', which means that the corresponding dual constraint, YP; s cy, is not satisfied. When the primal optimal is reached, we get Zj ~ c, > 0, for allwhich means that the corresponding dual solution Y = C/jB-1 becomes feasible. We conclude that while the primal is seeking optimality, the dual is automatically seeking feasibility. This point is the basis for the development of the dual simplex method (Section 4.4) in which the iterations start better than optimal and infeasible and remain so until feasibility is acquired at the last iteration. This is in contrast with the (primal) simplex method (Chapter 3), which remains worse than optimal but feasible until the optimal iteration is reached. Example 7.5-1 The optimal basis for the following LP is B = (PbP4). Write the dual and find its optimum solution using the optimal primal basis. Maximize z — 3xx + 5x2 subject to xt + 2x2 + *3 =5 -xl + 3x2 + x4 - 2 xl,x2,x:„xA > 0 The dual problem is given as Minimize w = 5y, + 2y2 7.5 Duality 325 subject to yi ~ y2 ^ 3 2yx + 3y2 > 5 y3,y2 s 0 We have XB = (xh x4)T; it follows that CH = (3,0). The optimal basis and its inverse are given as 1 0\ (\ 0 iJandB"1 = vi The associated primal and dual values are (xux4)T = B b = (5,7)r (yby2) = CBB 1 = (3,0) Both solutions are feasible and z = w = 15 (verify!). Thus, the two solutions are optimal. PROBLEM SET 7.5B 1. Verify that the dual problem of the numeric example given at the end of Theorem 7.5-1 is correct. Then verify graphically that both the primal and dual problems have no feasible solution. 2. Consider the following LP: Maximize z = 50x] + 3(k2 + l(k3 subject to Ixi + x2 =1 2x2 = -5 4xj + x3 = 6 xhx2,x3 2 0 (a) Write the dual. (b) Show by inspection that the primal is infeasible. (c) Show that the dual in (a) is unbounded. (d) From Problems 1 and 2, develop a general conclusion regarding the relationship between infeasibility and unboundedness in the primal and dual problems. 3. Consider the following LP: Maximize z = 5xx + 12x2 + 4x3 subject to 2xx — x2 + 3*3 = 2 X| + 2x2 + x3 + x4 = 5 xs,x2,x3,x4 > 0 326 Chapter 7 Advanced Linear Programming (a) Write the dual. (b) In each of the following cases, first verify that the given basis B is feasible for the primal. Next, using Y = CBB"' , compute the associated dual values and verify whether or not the primal solution is optimal. (i) B = (P4,P3) (iii) B = (P^P,) (u) B = (P2,P,) (iv) B = (P,,P4) 4. Consider the following LP: Maximize z = 2xx + 4x2 + 4x3 — 3x4 subject to Xj + x2 + x3 =4 Xj + 4*2 + + x4 = 8 X1,X2,X3,X4 s 0 (a) Write the dual problem. (b) Verify that B = (P2,P3) is optimal by computing Zj - c;- for all nonbasic P;. (c) Find the associated optimal dual solution. 5. An LP model includes two variables x, and x2 and three constraints of the type s.The associated slacks are x3,x4, and x5. Suppose that the optimal basis is B = (P1: P2, P3), and its inverse is (0 -1 1\ B 1= 0 1 0 \l 1 -l) The optimal primal and dual solutions arc given as Xa = (xux2,x3)T = (2,6,2)r Y = (y„y2,v3) = (0,3,2) Determine the optimal value of the objective function in two ways using the primal and dual problems. 6. Prove the following relationship for the optimal primal and dual solutions: 2™ |C,(B-'P/C); = S™iy,a* where CH = (c,,c2, ... ,cm) and Pk = (a[k,a2k, ... ,a„,k)T ,for k = 1,2, ... ,n ,and (B_1Pt),- is the (th element of B~lFk. 7. Write the dual of Maximimize z = {CX|AX = b, X unrestricted} 8. Show that the dual of Maximize z = {CX| AX 0 . The general idea of parametric analysis is to start with the optimal solution at t = 0. Then, using the optimality and feasibility conditions of the simplex method, we determine the range 0 < t < tx for which the solution at t = 0 remains optimal and feasible. In this case, t\ is referred to as a critical value. The process continues by determining successive critical values and their corresponding optimal feasible solutions. The process will terminate at f = tr when there is indication that either the last solution remains unchanged for t > tr or that no feasible solution exists beyond that critical value. 7.6.1 Parametric Changes in C Let XB,B„CB(f) be the elements that define the optimal solution associated with critical tj (the computations start at t0 = 0 with B„ as its optimal basis). Next, the critical value and its optimal basis, if one exists, is determined. Because changes in C can only affect the optimality of the problem, the current solution XB = B,'b will remain optimal for some t ^ t, so long as the following optimality condition is satisfied: The value of ti+1 equals the largest t > t; that satisfies all the optimality conditions. Note that nothing in the inequalities requires C(f) to be linear in t. Any function C(r), linear or nonlinear, is acceptable. However, with nonlinearity the numerical manipulation of the resulting inequalities may be cumbersome. (See Problem 5, Set 7.6a for an illustration of the nonlinear case.) Example 7.6-1 Zj(t) - Cj(t) = c^OBr1?/ - Cjit) > 0, for all; Maximize z (3 - 6t)x, + (2 - 2t)x2 + (5 + 5t)x3 subject to xv + 2x2 + x3 < 40 3*i + 2*3 < 60 *i + 4x2 < 30 *],*2,*3 a 0 We have (3 - 6t,2 - 2t,5 + 5t),t > 0 328 Chapter 7 Advanced Linear Programming Optimal Solution at t = t0 = 0 Basic *1 *2 *3 x4 *5 *6 Solution z 4 0 0 1 2 Ü 160 x2 l 4 1 0 1 2 i 4 0 5 x3 3 0 1 0 1 0 30 *6 2 0 f) -2 i 1 10 XBa = (x2,x3,xb)T = (5,30,10)'' CBo(0 = (2 - 2?,5 + 5f,0) / I 4 o\ B? = 0 | 0 \-2 1 1/ The optimality conditions for the current nonbasic vectors P^P^ and P5 are (C^OBo'P/ " <'.(')}..:.:..- = (4 + 14M - U + 30 ^ 0 Thus, XB(| remains optimal so long as the following conditions are satisfied: 4 + 14f > 0 1 - r > 0 2 + 3t > 0 Because f > 0, the second inequality stipulates that t s 1 and the remaining two inequalities are satisfied for all t s 0. We thus have = 1, which means that XB[ remains optimal (and feasible) for 0 < t s 1. At t = l,z4(?) - c4(r) = 1 — t equals zero and becomes negative for t > l.Thus, P4 must enter the basis for t > 1. In this case, P2 must leave the basis (see the optimal tableau at t = 0). The new basic solution XBi is the alternative solution obtained at t = 1 by letting P4 enter the basis—that is,XB = (x4,x3,x6)T and B, = (P4,P,,P6). Alternative Optimal Basis at t = t{ = 1 l\ 1 11 _1 2 0 B, = 0 2 0 0 1 2 0 lü 0 1/ [0 0 1 Thus, XBi = (x4,x„x6)T = B^b = (10,30,30)r CBl(r) = (0,5 + 5f,0) The associated nonbasic vectors are Pi,P2, and P5, and we have [c^BSPi - <•(/)}. ..... = + 2f,4^) > 0 According to these conditions, the basic solution XB remains optimal for all t > 1. Observe that the optimality condition, -2 + 2t ^ 0, automatically "remembers" that 7.6 Parametric Linear Programming 329 XB] is optimal for a range of t that starts from the last critical value tx = 1, This will always be the case in parametric programming computations. The optimal solution for the entire range of t is summarized below. The value of z is computed by direct substitution. t X, X; x3 < 0 1 0 0 30 150 H - 150r PROBLEM SET 7.6A 1. In Example 7.6-1, suppose that t is unrestricted in sign. Determine the range of t for which Xflj remains optimal. 2. Solve Example 7.6-1, assuming that the objective function is given as (a) Maximize z = (3 + 3f)x, + 2x2 + (5 - 6r)x3 (b) Maximize z = (3 - 2t)xl + (2 + t)x2 + (5 + 2f)x3 (c) Maximize z = (3 + t)x] + (2 + 2t)x2 + (5 - t)x3 3. Study the variation in the optimal solution of the following parameterized LP given / > 0. Minimize z = (4 - t)xx + (1 - 3;)x2 + (2 - 2r)x3 subject to 3X] + x2 + 2x3 = 3 4x, + 3x2 + 2x3 2: 6 X\ + 2x2 + 5x3 < 4 Xj,X2i^3 — 0 4. The analysis in this section assumes that the optimal solution of the LP at t = 0 is obtained by the (primal) simplex method. In some problems, it may be more convenient to obtain the optimal solution by the dual simplex method (Section 4.4). Show how the parametric analysis can be carried out in this case, and then analyze the LP of Example 4.4-1, assuming that the objective function is given as Minimize z = (3 + f)xl + (2 + 4r)x:. t > 0 5. In Example 7.6-1, suppose that the objective function is nonlinear in t(t s 0) and is defined as Maximize z = (3 + 2f2)x, + (2 - 2t2)x2 + (5 - r)x3 Determine the first critical value tv 7.6.2 Parametric Changes in b The parameterized right-hand side b(r) can only affect the feasibility of the problem. The critical values of t are thus determined from the following condition: XB(t) = B-'b(0 > 0 330 Chapter 7 Advanced Linear Programming Example 7.6-2 Maximize z = 3*t + 2x2 + 5x3 subject to x-i + 2x2+ x3 ^ 40 - t 3xy + 2x3 < 60 + It xx + 4x2 < 30 - It XhX2,X3 2: 0 Assume that t > 0 . At f = f„ = 0, the problem is identical with that in Example 7.6-1. We thus have XBo = (x2,.r3,x6)T = (5,30,10)7 n ~\ 0\ Bo1 = 0 | 0 1-2 1 1/ To determine the first critical value fls we apply the condition XBn(r) = Bj'b^) =s 0 which yields x2\ r7 5-f \ 0 30 + f > 0 *6/ \10 - 3f/ 0/ These inequalities are satisfied for r < y , meaning that tx = y and that the basis B0 remains feasible for the range 0 < f < y. However, the values of the basic variables x2,x3, and x6 will change with ? as given above. The value of the basic variable x6 (=10 - 3f) will equal zero at t = h = y and will become negative for / > y. Thus, at t = y , we can determine the alternative basis Bj by applying the revised dual simplex method (see Problem 5, Set 7.2b for details). The leaving variable is x6. Alternative Basis at t = ti = y Given x6 is the leaving variable, we determine the entering variable as follows: XB„ = (x2,x3,x/,CBo = (2,5,0) Thus, {z, - c}, ,.,0 = {CBoBo'Py - Cj}MA.5 = (4,1.2) Next, for nonbasic Xj,j = 1,4,5, we compute (Row ofB01 associated with x6)(P1,P4,P5) = (Third row of Bo,)(P1,P4,P5) = (-2,l,l)(Pi,P4,P5) = (2,-2,1) The entering variable is thus associated with 7.6 Parametric Linear Programming 331 Thus, P4 is the entering vector. The alternative basis is Thus. (2 1 1\ B, = (P2,P3,P4) = 0 2 0 \4 (J l° 0 $ BF1 = 0 i 0 1 1 2 -\) The aewXS| - (x2,x3,x4)r . The next critical value t2 is determined from the condition XDi(t) = fir'tyr) s 0, which yields 30 + r 10 I 3t jo\ 0 w t 30 W \ These conditions show that Bx remains feasible for ■ At t = t2 = y, an alternative basis can be obtained by the revised dual simplex method. The leaving variable is x2 because it corresponds to the condition yielding the critical value t2. Alternative Basis at t = t2 = y. Given x2 is the leaving variable, we determine the entering variable as follows: XBi = (x2,Xi,x4)TXBi = (2,5,0) Thus, fej ~ C;}jf'=l,S,6 = {Cfl.Bi'Py — Cy}y=1 36 = (5,2,2) Next, for nonbasic Xj, j = 1,5, 6, we compute (Row of B7!associated with x2)(P1,P5,P6) = (First row of B^fPi.Ps.Ps) = (0,0,i)(P„P5,P6) Because all the denominator elements, are s 0, the problem has no feasible solution for t > y and the parametric analysis ends at t = t2 = y. The optimal solution is summarized as y (No feasible solution exists) 332 Chapter 7 Advanced Linear Programming PROBLEM SET 7.6B 1. In Example 7.6-2, find the first critical value, tu and define the vectors of B, in each of the following cases: (a) b(r) = (40 + 2t,60 - 3r,30 + 6t)T (b) b(f) = (40 - r,60 + 2r,30 - 5f)r 2. Study the variation in the optimal solution of the following parameterized LP given t > 0. Minimize z = 4x, + x2 + 2x3 subject to 3xj + X[ + 2x3 = 3 + 3t 4x, + 3x2 + 2x3 s 6 + 2t X\ + 2x2 + 5x3 < 4 — r xl,x2,x3 & 0 3. The analysis in this section assumes that the optimal LP solution at t = 0 is obtained by the (primal) simplex method. In some problems, it may be more convenient to obtain the optimal solution by the dual simplex method (Section 4.4). Show how the parametric analysis can be carried out in this case, and then analyze the LP of Example 4.4-1, assuming that the right-hand-side vector is b(t) = (3 + 2t,6 - t,3 - Aif Assume t > 0. 4. Solve Problem 2 assuming that the right-hand side is changed to b(t) = (3 + 3t2,6 + 2t2,4 - t2)T Further assume that t can be positive, zero, or negative. 7.7 KARMARKAR INTERIOR-POINT METHOD The simplex method obtains the optimum solution by following a path of adjacent extreme points along the edges of the solution space. Although in practice the simplex method has served well in solving large problems, theoretically the number of iterations needed to reach the optimum solution can grow exponentially. In fact, researchers have constructed a class of LPs in which all feasible extreme points are visited before the optimum is reached. In 1984, N. Karmarkar developed a polynomial-time algorithm that cuts across the interior of the solution space. The algorithm is effective for extremely large LPs. We start by introducing the main idea of the Karmarkar method and then provide the computational details of the algorithm. 7.7.1 Basic Idea of the Interior-Point Algorithm Consider the following (trivial) example: Maximize z = xx 7.7 Karmarkar Interior-Point Method 333 subject to 0 < xx < 2 Using x2 as a slack variable, the problem can be rewritten as Maximize z = X\ subject to Xi + x2 = 2 xux2 s 0 Figure 7.6 depicts the problem. The solution space is given by the line segment AB. The direction of increase in z is in the positive direction of xv Let us start with any arbitrary interior (nonextreme) point C in the feasible space (line AB). The gradient of the objective function (maximize z = xx ) at G is the direction of fastest increase in z. If we locate an arbitrary point along the gradient and then project it perpendicularly on the feasible space (line AB), we obtain the new point D with a better objective value z. Such improvement is obtained by moving in the direction of the projected gradient CD. If we repeat the procedure at D, we will determine a new closer-to-optimum point E. Conceivably, if we move (cautiously) in the direction of the projected gradient, we will "stumble" on the optimum point B. If we are minimizing z (instead of maximizing), the projected gradient will correctly move us away from point B toward the minimum at point A (xx - 0). The given steps hardly define an algorithm in the normal sense, but the idea is intriguing! We need some modifications that will guarantee that (1) the steps generated along the projected gradient will not "overshoot" the optimum point at B, and (2) in the general ^-dimensional case, the direction created by the projected gradient will *2 FIGURE 7.6 Illustration of the general idea of Karmarkars algorithm Gradient of z Maximize 334 Chapter 7 Advanced Linear Programming not cause an "entrapment" of the algorithm at a nonoptimum point. This, basically, is what Karmarkar's interior-point algorithm accomplishes. 7.7.2 Interior-Point Algorithm Several variants of Karmarkar's algorithm are available in the literature. Our presentation follows the original algorithm. Karmarkar assumes that the LP is given as Minimize z = CX subject to AX = 0 IX = 1 X > 0 All the constraints are homogeneous equations except for the constraint IX = 2"=iJtj = 1 , which defines an ^-dimensional simplex. The validity of Karmarkar's algorithm rests on satisfying two conditions: 1. X = (1,1,...,I) satisfies AX = 0 2. min z = 0 Karmarkar provides modifications that allow solving the problem when the second condition is not satisfied. These modifications will not be presented here. The following example illustrates how a general LP may be put in the homogeneous form AX = 0 with IX = 1, which also provides X = ..,,£) as a feasible solution (condition 1). A second example shows how the transformation can be made to satisfy both conditions, albeit involving tedious computations. Example 7.7-1 Consider the problem. Maximize z = yi + y2 subject to ya + 2y2 < 2 ylsy2 ^ 0 The constraint y, + 2y2 ^ 2 is converted into an equation by augmenting a slack variable y3 > 0 to yield yx + 2y2 + y3 = 2 Now define yi + y2 + y3 ^ U where U is sufficiently large so as not to eliminate any feasible points in the original solution space. In our example, U = 5 will be adequate as can be determined from the equation yx + 2y2 + y3 = 2 . Augmenting a slack variable y4 S: 0, we obtain 7.7 Karmarkar Interior-Point Method 335 >'i + y% + b + y* = 5 We can homogenize the constraint yx + 2y2 + y3 = 2 by multiplying the right-hand side by >: j >;i + >,J because the latter fraction equals 1. This yields, after simplification, 3y, + 8y2 + 3y3 - 2y4 = 0 y. To convert y: + y2 + y3 + y4 = 5 to a simplex, we define the new variable x,- = 5, j = 1, 2, 3, 4, to obtain Maximize z = 5xj + 5x2 subject to 3x, + 8*2 + 3x3 - 2x4 = 0 X\ -H x2 ~l~ X3 "i- x4 = 1 xj s= 0,/ = 1,2,3,4 Finally, we can ensure that the center X = (-,-,...,£) of the simplex is a feasible point for homogeneous equations by subtracting from the left-hand side of each equation an artificial variable whose coefficient equals the algebraic sum of all the constraint coefficients on the left-hand side—that is, 3 + 8 + 3 - 2 = 12. The artificial variables are then added to the simplex equation and are penalized appropriately in the objective function. In our example, the artificial jc5 is augmented as follows: Maximize z = 5xx + 5x2 — Mx5 subject to 3xA + 8x2 + 3x3 — 2x4 — 12xs = 0 x1 + x2 + x3 + x4 + x5 = 1 Xj > 0,; = 1,2,...,5 For this system of equations, the new simplex center (5,|,... ,\) is feasible for the homogeneous equation. The value M in the objective function is chosen sufficiently large to drive xs to zero level (compare with the M-method, Section 3.4.1). Example 7.7-2 This example shows that any LP can satisfy conditions (1) and (2) required by Karmarkars algorithm. The transformations are tedious and, hence, not recommended in practice. Instead, a variation of the algorithm that does not require condition (2) is advisable. Consider the same LP of Example 7.8-1—namely, Maximize z = V\ + y2 subject to yx + 2y2 < 2 yi,yi s 0 336 Chapter 7 Advanced Linear Programming We start by defining the primal and dual problems of the LP: Primal Dual Maximize y0 = y] + y2 Minimize w0 = 2w, subject to subject to yhy2 a 0 wt,w2 Z 0 The primal and dual constraints can be put in equation forms as Vl + 2y2 + y3 = 2,y3 > 0 (1) tv, — w2 = l,w2 — 0 At the optimum y0 = w0 , which yields >'i + }'i ~ 2wi = 0 (2) Selecting M sufficiently large, we have Vi + y2 + y3 + tvi + vv2 < M (3) Now, converting (3) into an equation we get >'l + }'2 + V3 + Wj + VV2 + i[ = M, s 0 (4) Next, define a new variable s2 ■ From (4) the following two equations hold if, and only if, the condition s2 = 1 holds: Vi + y/i + v3 + W] + w2 + jj — Ms2 = 0 y1 + y2 + y3 + w, + w2 + sx + s2 = M + 1 (5) Now, given *2 = 1 as stipulated by (5), the primal and dual equations (1) can be written as yx + 2y2 + y3 — 2s2 = 0 K>i — W>2 — L'2 = 0 (6) Now, define y;. = (M+ l)Xj,j = 1,2,3 Wy-3 = {M + l)xp j = 4,5 51 = (M + l)x6 52 = (Af + l)x7 Substitution in equations (2), (5), and (6) will produce the following equations: X\ + x2 - 2x4 = 0 x, + x2 + x3 + x4 + xs + x6 - Mx7 — 0 Xj + x2 + x3 + x4 + x5 + x6 + x7 = 1 x{ + 2x2 + x3 — 2x7 = 0 7.7 Karmarkar Interior-Point Method 337 x4 - x5 - x1 = 0 Xj > 0,/ = 1,2,...,7 The final step calls for augmenting the artificial variable ys in the left-hand side of each equation; the new objective function will call for minimizing yg, whose minimum value must be zero (assuming the primal is feasible). Note, however, that Karmarkar's algorithm requires the solution Y _ /l 11 t 111 I\r to be feasible for AX = 0 .This will be true for the homogeneous equations (with zero right-hand side) if the associated coefficient of the artificial xs equals the (algebraic) sum of all the coefficients on the left-hand side. It thus follows that the transformed LP is given as Minimize z — xs subject to .V, + x2 - 2x4 — 0x8 = 0 •Vl + x2 + x3 + x4 + x5 + x6 - Mx7 - (6 - M>-8 = 0 x1 + 2x2 + *3 - 2x7 - 2xs = 0 x4 ~ x5 - X-, + x% = 0 *1 + x2 + *3 + x4 + Xs + xt + x7 + = 1 Xj a 0,/= 1, 2,...,8 Note that the solution of this problem automatically yields the optimum solutions of the primal and dual problems through substitution. We now present the main steps of the algorithm. Figure 7.7 (a) provides a typical illustration of the solution space in three dimensions with the homogeneous set AX = 0 consisting only of one equation. By definition, the solution space consisting of the line segment AB lies entirely in the two-dimensional simplex IX = 1 and passes through the feasible interior point (5, \,|). In a similar fashion, Figure 7.7 (b) provides an illustration of the solution space ABC in four dimensions with the homogeneous set again consisting of one constraint only. In this case, the center of the three-dimensional simplex is given by (\,\,\,\)- Karmarkar's algorithm starts from an interior point represented by the center of the simplex and then advances in the direction of the projected gradient to determine a new solution point. The new point must be strictly interior, meaning that all its coordinates must be positive. The validity of the algorithm rests on this condition. For the new solution point to be strictly interior, it must not lie on the boundaries of the simplex. (In terms of Figure 7.7, points A and B in three dimensions and lines AB, BC, and AC in four dimensions must be excluded.) To guarantee this result, a sphere with its center coinciding with that of the simplex is inscribed tightly inside the simplex. In the n-dimensional case, the radius r of this sphere equals .- 1 . A r 1 X'11(11 - 1) smaller sphere with radius a r (0 < a < 1) will be a subset of the sphere, and any point in the intersection of the smaller sphere with the homogeneous system AX = 0 will be 7.7 Karmarkar Interior-Point Method 339 an interior point, with strictly positive coordinates. Thus, we can move as far as possible in this restricted space (intersection of ax = 0 and the a r-sphere) along the projected gradient to determine the new (necessarily improved) solution point. The new solution point no longer will be at the center of the simplex. For the procedure to be iterative, we need to bring the new solution point to the center of a simplex. Karmarkar satisfies this requirement by proposing the following intriguing idea, called projective transformation. Let A, y,- = -jr—J = 1,2,...,« 7=1 where xki is the z'th element of the current solution point Xk, The transformation is valid, because all xki > 0 by design. You will also notice that 2"=iVj = 1, or 1Y = 1 , by definition. This transformation is equivalent to _. Drx >k_ n id:x where Dk is a diagonal matrix whose ith diagonal elements equal xki. The transformation maps the .Y-space onto the Y-space uniquely because we can directly show that the last equation yields DkY x = 1D,y By definition, min cx = 0. Because 1DA y is always positive, the original linear program is equivalent to subject to Minimize z = cday aday = 0 1Y = 1 y > 0 The transformed problem has the same format as the original problem. We can thus start with the simplex center y = (\,\,... ,£) and repeat the iterative step. After each iteration, we can compute the values of the original x variables from the y solution. We show now how the new solution point can be determined for the transformed problem. At any iteration k, the problem is given by Minimize z = cdty subject to ad/(y = 0 y lies in the ar -sphere Because the ar -sphere is a subset of the space of the constraints ix = 1 and x > 0, these two constraints can be dispensed with. As a result, the optimum solution of the 340 Chapter 7 Advanced Linear Programming preceding problem lies along the negative projection of the gradient cp (minimization) and is given as ar -. where Y0 = (j;,fr ■■■,y,)T and cp is the projected gradient, which can be shown to be c = [I - P'fPP^PKCD,)7 where 1 The selection of ct is crucial to enhancing the efficiency of the algorithm. Normally, we select a as large as possible to acquire large jumps in the solution. However, by choosing a too large, we may come too close to the prohibited boundaries of the simplex. There is no general answer to this problem, but Karmarkar suggests the use of n - 1 a = The steps of Karmarkar's algorithm are Step 0. Start with the solution point X0 = ... ,^) and compute r = _ (n - 1) 1 «V(n - 1) and General step k. Define and compute Dfc = diag{xH, ...,xkn} p = (AD, n n n v ^k A new where cp = [i - pT(ppYnky Example 7.7-3 Minimize z = 2xx + 2x2 - 3x3 subject to —jci — 2x2 + 3x3 = 0 xl + x2 + x3 = 1 Xi_,x2,x3 > 0 7.7 Karmarkar Interior-Point Method 341 The problem satisfies the two conditions imposed by the interior-point algorithm— namely, X = (x1,x2,xi) = (3,3,3) satisfies both constraints and the optimum solution X* = {x\A,x,Y = (0,.6,.4)r yields z = 0. Iteration 0. c = (2, 2, -3),A = (-1,-2,3) (I 0 o\ Dn = 0 \« 0 3/ Using projective transformation, we get Y = (- - Mr Iteration 1. cD0 = (2,2,-3) ADn (-1,-2,3) 0 (PP'/)-i = (-1,-1,1) (1 0 o\ - 1 I - P^PP7) p = 0 1 0 -H 1 \<-» 0 1/ \ 1 1/ 25 -20 -20 16 -5 4 -5\ 4 1/ Thus, It then follows that 1 1 ( 25 -20 "5 / ^ / 25\ Cp = (i - pt(ppT-p)(^t = k -20 16 4 2 = _L 126 -20 I -5 4 1/ I SI 252 + (-20)2 + (-5)2 1262 .257172 342 Chapter 7 Advanced Linear Programming Thus, Next, Now, - /I 1 iYT _ 2 w J_ y \3'3'3J 9 ^ v'6 -257172 X Jg(25,-20,-5)7 = (.263340, .389328, .347332)r lD0Ynew = ±(1,1,1)(.263340, .389328, .347332) r _ i 3 Zl .26334 3 new 3 = Ynew = (.263340, .389328, .347332)r Iteration 2. cD, = /.263340 0 (2,2,-3) 0 .389328 \ 0 0 / .263340 0 0 ADj = (-1,-2,3) 0 .389328 0 \ 0 0 .347332/ 0 0 ] = (.526680, .778656,-1.041996) 3473321 (-.263340,-.778656,1.041996) (PP')-i = .26334 -.778656 1.041996\ 1 1 1 J I-.263340 l\ \ -.778656 1 \ 1.041996 1/ / .567727 0 0 .333333 / I - Pr(PPr) P /-.263340 1 -.778656 1 \ 1.041996 1 -.263340 -.778656 1.041996\ 1 1 1 J I .627296 -.449746 -.177550\ -.449746 .322451 .127295 \ -.177550 .127295 .050254/ .567727 0 0 .333333 Thus, cp = (I - Pr(PPVP)(cD,)r / .627296 -.449746 -.177550W .526680\ -.449746 .322451 .127295 .778656 \-.177550 .127295 .050254/\-1.041996/ / .165193 -.118435 \-.046757/ It then follows that Ikpll = V.1651932 + (-.118435)2 + (-.046757)2 = .208571 7.7 Karmarkar Interior-Point Method 343 Thus, Ynew = iW ~lx^x i(T65193,-.118435, -.046757)7" = (.261479, .384849, .353671)r Next, ^.263340 0 0 \ / .261479^ /.068858\ DiYnew — 0 .389328 0 .384849 = .149832 \ 0 0 .347332/ \.353671 / y. 122841 / lDiYnew = .341531 Now, X2 " lDiYn z2 = .201615 Repeated application of the algorithm will move the solution closer to the optimum point (0, .6, .4). Karmarkar does provide an additional step for rounding the optimal solution to the optimum extreme point. /.201616\ = .438707 \.359677/ PROBLEM SET 7.7 A 1. Use TORA to show that the solution of the transformed LP given at the end of Example 7.7-2 does yield the optimal primal and dual solutions of the parent problem. (Hint: Use M=W and make sure that TORA's output gives at least 5 decimal points accuracy.) 2. Transform the following LP to Karmarkar's format. Maximize z = y\ + 2y2 subject to vi - y2 ^ 2 2>'[ + y2 s 4 yi,y2 & 0 3. Carry out one additional iteration in Example 7.7-3, and show that the solution is moving toward the optimum z = 0. 4. Carry out three iterations of Karmarkar's algorithm for the following problem: Maximize z = 4x, + x3 + x4 subject to —2X[ + 2x2 + x3 — x4 = 0 .Vj + x2 + x3 + x4 = 1 xux2,x3,x4 > 0 (Hint: The problem must be converted to Karmarkar format first.) 344 Chapter 7 Advanced Linear Programming 5. Carry out three iterations of Karmarkar's algorithm for the following linear program: Maximize z = 2xx + x2 subject to X\ + x2 < 4 xt,x2 > 0 (HintThe problem must be converted to Karmarkar format first.) SELECTED REFERENCES Bazaraa, M., J. Jarvis, and H. Sherali, Linear Programming and Network Flows, 2nd ed., Wiley. New York, 1990. Hooker, I, "Karmarkar's Linear Programming Algorithm," Interfaces, Vol. 16, No. 4, pp. 75-90. 1986. Nering, E., and A. Tucker, Linear Programming and Related Problems, Academic Press, Boston. 1992. COMPREHENSIVE PROBLEMS 7.1 Suppose that you are given the points A = (6,4,6.-2), B = (4,12,-4,8), C = (-4.0,8,4) Develop a systematic procedure that will allow determining whether or not each of the following points can be expressed as a convex combination of A, B, and C: (a) (3.5,4,2) (b) (5.8,4,9) 7.2 Consider the following LP: Maximize z = 3xx + 2x2 subject to a-, + 2x2 < 6 2*i + x2 < 8 —X\ + x2 < 1 xhx2 — 0 Determine the optimum simplex tableau (use TORA for convenience), and then directly use the information in the optimum simplex tableau to determine the second best extreme-point solution (relative to the "absolute" optimum) for the problem. Verify the answer by solving the problem graphically. (Hint: Consult the extreme points that are adjacent to the optimum solution.) 7.3 Interval Programming. Consider the following LP: Maximize z = {CX|L < AX < U,X > 0} Comprehensive Problems 345 where L and U are constant column vectors. Define the slack vector such that AX + Y = U. Show that this LP is equivalent to Maximize z = {CX|AX + Y = U,0 < Y < U - L,X > 0} Use the proposed procedure to solve the following LP: Minimize z - 5xx - 4x2 + 6x3 subject to 20 < xx + lx2 + 3x3 < 46 10 < 3*! - x2 + x3 < 20 18 < 2xx + 3x2 - x3 < 35 Xi,x2,x3 > 0 7.4 Consider the following 0-1 integer LP: Minimize z = {CX|AX < b,X = (0,1)} Suppose that z m-m is a known upper bound on z. Define the constraint minmax{u.(b - AX) + (zmi. - CX)} > 0 where jul > 0. This constraint does not violate any of the restrictions of the original 0-1 problem. The min-max problem is one way of identifying the "tightest" such constraint through proper selection of (x(2:0). Show that the proposed mixed 0-1 definition for determining jjl actually reduces to solving an ordinary LP problem. {Hint: The integer restriction X = [0,1] is equivalent to the continuous range 0 < X < 1. Use the dual problem to define the desired LP.) 7.5 The optimum solution of the LP in Problem 7-2 is given as xx = y, x2 = \ , and z = y. Plot the change in optimum z with 6 given that x, = y + 9 , where 6 is unrestricted in sign. Note that X\ = y + 9 tracks xx above and below its optimal value. 7.6 Suppose that the optimum linear program is represented as Maximize z = c0 - 2)(*> ~ CM jcNB subject to Xj = x* - ^jOLijXj.i = 1,2, ...,m jsNB all xt and x-. — 0 where NB is the set of nonbasic variables. Suppose that for a current basic variable xt = x* wc impose the restriction x, - dh where d, is the smallest integer greater than x}. Estimate an upper bound on the optimum value of z after the constraint is augmented to the problem. Repeat the same procedure assuming that the imposed restriction is x, s et, where e, is the largest integer smaller than x*. 1.1 Consider the following minimization LP: Minimize z = (lOf - 4)xt + (4t - 8)x2 subject to 2jc, + 2x2 + x3 =8 4x, + 2x2 + x4 = 6 - 2t Xy,X2,X3,Xi — 0 where —oc < f < oo.The parametric analysis of the problem yields the following results: -co < ( < -5; Optimal basis is B = (Pi,P4) -5 < t < -l:Optimal basis is B = (PbP2) -1 < r < 2:Optimal basis is B = (P2,P3) Determine all the critical values of t that may exist for t > 2 . CHAPTER 8 Goal Programming The LP models presented in the preceding chapters are based on the optimization of a single objective function. There are situations where multiple (possibly conflicting) objectives may be more appropriate. For example, aspiring politicians may promise to reduce the national debt and, simultaneously, offer income tax relief. In such situations, it may be impossible to find a single solution that optimizes the conflicting objectives. Instead, we may seek a compromise solution based on the relative importance of each objective. This chapter presents the goal programming technique for solving multiobjective models. The principal idea is to convert the original multiple objectives into a single goal. The resulting model yields what is usually referred to as an efficient solution because it may not be optimum with respect to all the conflicting objectives of the problem. A GOAL PROGRAMMING FORMULATION The idea of goal programming is illustrated by an example. Example 8.1-1 Fairville is a small city with a population of about 20,000 residents. The city council is in the process of developing an equitable city tax rate table. The annual taxation base for real estate property is $550 million. The annual taxation bases for food and drugs and for general sales are $35 million and $55 million, respectively. Annual local gasoline consumption is estimated at 7.5 million gallons. The city council wants to develop the tax rales based on four main goals. 1. Tax revenues must be at least $16 million to meet the city's financial commitments. 2. Food and drug taxes cannot exceed 10% of all taxes collected. 347 348 Chapter 8 Goal Programming 3. General sales taxes cannot exceed 20% of all taxes collected. 4. Gasoline tax cannot exceed 2 cents per gallon. Let the variables xp, xf, and xs represent the tax rates (expressed as proportions of taxation bases) for property, food and drugs, and general sales; and define the variable xg as the gasoline tax in cents per gallon. The goals of the city council are then expressed as 550xp + 35xf + 55xs + .075xg > 16 (Tax revenue) 35xf < .1(550*,, + 35xf + 55xs + .Q75xg) (Food/drug tax) 55xs < .2(550*,, + 35*; + 55*s + .075*g) (General tax) xg < 2 (Gasoline tax) Xf) X$y Xg — 0 These constraints are then simplified as 550*p + 35xf + 55xs + .075xg > 16 55xp - 31.5*; + 5.5*, + .0075*,, > 0 110*p + lxf - 44*, + .015xg > 0 xg < 2 xp, xfi xs, xg > 0 Each of the inequalities of the model represents a goal that the city council aspires to satisfy. Most likely, however, the best we can do is seek a compromise solution among these conflicting goals. The manner in which goal programming finds a compromise solution is to convert each inequality into a flexible goal in which the corresponding constraint may be violated, if necessary. In terms of the Fairville model, the flexible goals are expressed as follows: 550xp + 35xf + 55xs + .075xg + - si = 16 55xp - 3I.5.17 + 5.5*, + .0075*g - Si = 0 110xp + lxf - 44*, + .015*g + S+3 - S3 = 0 ** + 4 - 54 = 2 xp xSi Xg — 0 S-, sj >0,i= 1, 2, 3, 4 The nonnegative variables si and si, i = 1,2, 3, 4, are called deviational variables because they represent the deviations above and below the right-hand side of constraint i. The deviational variables si and sj are by definition dependent and, hence, canno: be basic variables simultaneously. This means that in any simplex iteration, at most one of the two deviational variables can assume a positive value. If the original rth inequality is of the type < and its si > 0, then the ith goal will be satisfied; otherwise, if s~ > 0. goal i will not be satisfied. In essence, the definition of s* and sj allows us to meet or vio- 8.1 A Goal Programming Formulation 349 late the z'th goal at will. This is the type of flexibility that characterizes goal programming when it seeks a compromise solution. Naturally, a good compromise solution aims at minimizing the amount by which each goal is violated. In the Fairville model, given that the first three constraints are of the type ^ and the fourth constraint is of the type the deviational variables s£, s~z, si, and sA of the problem represent the amounts by which the respective goals are violated. Thus, the compromise solution tries to satisfy the following four objectives as much as possible: Minimize Gt = si Minimize G2 = s2 Minimize G3 = s3 Minimize G4 = ,v4 These functions are minimized subject to the constraint equations of the model. How can we optimize a multiobjective model with possibly conflicting goals? Two methods have been developed for this purpose: (1) the weights method and (2) the preemptive method. Both methods are based on converting the multiple objectives into a single function as detailed in Section 8.2. PROBLEM SET 8.1A 1. Formulate the Fairville tax problem, assuming that the town council is specifying an additional goal, G5, that requires gasoline tax to equal at least 10% of the total tax bill. 2. The NW Shopping Mall conducts special events to attract potential patrons. The two most popular events that seem to attract teenagers, the young/middle-aged group, and senior citizens are band concerts and art and craft shows. The costs per presentation of the band and art show are $1500 and $3000, respectively. The total (strict) annual budget allocated to the two events is $15,000. The mall manager estimates the attendance of the events as follows: Number attending per presentation Event Teenagers Young/middle age Seniors Band concert Art show 200 100 0 0 400 250 The manager has set the minimum annual goals of 1000,1200, and 800 for the attendance of teenagers, the young/middle-aged group, and seniors, respectively. Formulate the problem as a goal programming model. 3. Ozark University admissions office is processing freshman applications for the upcoming academic year. The applications fall into three categories: instate, out-of-state, and international. The male-female ratios for in-state and out-of-state applicants are 1:1 and 3:2, respectively. For the international students, the corresponding ratio is 8:1.The American College Test (ACT) score is an important factor in accepting new students. 350 Chapter 8 Goal Programming Statistics indicate that the average ACT scores for in-state, out-of-state, and international students are 27,26, and 23, respectively. The committee on admissions has established the following desirable goals for the new freshman class: (a) The incoming class is at least 1200 freshmen. (b) The average ACT score for all incoming students is at least 25. (c) International students constitute at least f 0% of the incoming class. (d) The female-male ratio is at least 3:4. (e) Out-of-state students constitute at least 20% of the incoming class. Formulate the problem as a goal programming model. 4. Circle K farms consume 3 tons of special feed daily. The feed—a mixture of limestone, corn, and soybean meal—must satisfy the following nutritional requirements: Calcium. At least 0.8% but not more than 1.2% Protein, At least 22% Fiber, At most 5% The following table gives the nutritional content of the feed ingredients. Ingredient lb per lb of ingredient Calcium Protein Fiber Limestone .380 .00 .00 Corn .001 .09 .02 Soybean meal .002 .50 .08 Formulate the problem as a goal programming model, and state your opinion regarding the applicability of goal programming to this situation. 5. Mantel produces a toy carriage, whose final assembly must include four wheels and two seats. The factory producing the parts operates three shifts a day. The following table provides the amounts produced of each part in the three shifts. Shift Units produced per run Wheels Seats 1 500 300 2 600 280 3 640 360 Ideally, the number of produced wheels is exactly twice that of the number of seats. However, because the production rates vary from shift to shift, exact balance in production may not be possible. Mantel is interested in determining the number of production runs in each shift that minimizes the imbalance in the production of the parts. The capacity limitations restrict the number of runs to between 4 and 5 for shift 1,10 and 20 for shift 2, and 3 and 5 for shift 3. Formulate the problem as a goal programming model. 6. Camyo Manufacturing produces four parts that require the use of a lathe and a drill press. The two machines operate 10 hours a day. The following table provides the time in minutes required by each part: 8.1 A Goal Programming Formulation 351 Part Production time in min Lathe Drill press 1 5 3 2 6 2 3 4 6 4 7 4 It is desired to balance the two machines by limiting the difference between their total operation times to at most 30 minutes. The market demand for each part is at least 10 units. Additionally, the number of units of part 1 may not exceed that of part 2. Formulate the problem as a goal programming model. 7. Two products are manufactured on two sequential machines. The following table gives the machining times in minutes per unit for the two products. Machining time in min Machine Product 1 Product 2 1 5 3 2 6 2 The daily production quotas for the two products are 80 and 60 units, respectively. Each machine runs 8 hours a day. Overtime, though not desirable, may be used if necessary to meet the production quota. Formulate the problem as a goal programming model. 8. Vista City Hospital plans the short-stay assignment of surplus beds (those that are not already occupied) 4 days in advance. During the 4-day planning period about 30,25, and 20 patients will require 1-, 2-, or 3-day stays, respectively. Surplus beds during the same period arc estimated at 20,30,30, and 30. Use goal programming to resolve the problem of overadmission and undcradmission in the hospital. 9. The Von Trapp family is in the process of moving to a new city where both parents have accepted new jobs. In trying to find an ideal location for their new home, the Von Trapps list the following goals: (a) It should be as close as possible to Mrs. Von Trapp's place of work (within \ of a * mile). (b) It should be as far as possible from the noise of the airport (at least 10 miles). (c) It should be reasonably close to a shopping mall (within 1 mile). Mr. and Mrs. Von Trapp use a landmark in the city as a reference point and locate the x-y coordinates of work, airport, and shopping mall at (1,1), (20,15), and (4,7), respectively (all distances are in miles). Formulate the problem as a goal programming model. (Note: The resulting constraints are not necessarily linear.) 10. Regression Analysis. In a laboratory experiment, suppose that y, is the fth observed (independent) yield associated with the dependent observational measurements xi}, i = 1, 2, ..., m; j = 1, 2, ...,«. It is desired to determine a linear regression fit into these data points. Given b,, j = 0, 1, ..., n, as the regression coefficients,all ft, are determined such that the sum of the absolute deviations between the observed and the estimated yield is minimized. Formulate the problem as a goal programming model. 352 Chapter 8 Goal Programming 11. Chebyshev Problem. An alternative goal for the regression model in Problem 10 is to minimize over bj the maximum of the absolute deviations. Formulate the problem as a goal programming model. 8.2 GOAL PROGRAMMING ALGORITHMS This section presents two algorithms for solving goal programming. Both methods convert the multiple goals into a single objective function. In the weights method, the single objective function is the weighted sum of the functions representing the goals of the problem. The preemptive method starts by prioritizing the goals in order of importance. The model is then optimized using one goal at a time such that the optimum value of a higher priority goal is never degraded by a lower priority goal. The proposed two methods do not generally produce the same solution. Neither method, however, is superior to the other because each technique is designed to satisfy certain decision-making preferences. 8.2.1 The Weights Method Suppose that the goal programming model has n goals and that the rth goal is given as Minimize G{, i = 1, 2, ..., n The combined objective function used in the weights method is defined as Minimize z = wvGv + w2G2 + ... + wnGn The parameter wh i = 1,2, ..., n, represents positive weights that reflect the decision maker's preferences regarding the relative importance of each goal. For example, W-, = 1, for all i, signifies that all goals carry equal weights. The determination of the specific values of these weights is subjective. Indeed, the apparently sophisticated analytic procedures developed in the literature (see, e.g., Cohon, 1978) are still rooted in subjective assessments. Example 8.2-1 TopAd, a new advertising agency with 10 employees, has received a contract to promote a new product. The agency can advertise by radio and television. The following table provides data about the number of people reached by each type of advertisement, and the cost and labor requirements. Data/min advertisement Radio Television Exposure (in millions of persons) 4 8 Cost (in thousands of dollars) 8 24 Assigned employees 1 2 The contract prohibits TopAd from using more than 6 minutes of radio advertisement. Additionally, radio and television advertisements need to reach at least 45 million peo- 8.2 Goal Programming Algorithms 353 pie. TopAd has set a budget goal of $100,000 for the project. How many minutes of radio and television advertisement should TopAd use? Let X\ and x2 be the minutes allocated to radio and television advertisements. The goal programming formulation for the problem is given as Minimize Gy = Sy (Satisfy exposure goal) Minimize G2 = s2 (Satisfy budget goal) subject to 4x, + 8x2 + Sy - sy =45 (Exposure goal) to, + 24x2 + 4 ~ S2 = 100 (Budget goal) xv + 2x2 < 10 (Personnel limit) x, < 6 (Radio limit) xls X2i Sli Sli S2i S2t — 0 TopAd's management assumes that the exposure goal is twice as important as the budget goal. The combined objective function thus becomes Minimize z = 2Gy + G2 = 2s\ + s2 The optimum solution (obtained by TORA) is z = 10 xy = 5 minutes, x2 = 2.5 minutes, s\ = 5 million persons All the remaining variables equal zero. The fact that the optimum value of z is not zero indicates that at least one of the goals is not met. Specifically, Sy = 5 means that the exposure goal (of at least 45 million persons) is missed by 5 million individuals. Conversely, the budget goal (of not exceeding $100,000) is not violated because ,v2 = 0. Goal programming yields only an efficient solution to the problem, which is not necessarily optimum. For example, the solution Xy = 6 and x2 = 2 yields the same exposure (4x6 + 8x2 = 40 million persons) but costs less (8 X 6 + 24 X 2 = $ 96,000). In essence, what goal programming does is to find a solution that simply satisfies the goals of the model with no regard to optimization. Such "deficiency" in finding an optimum solution raises doubts about the viability of goal programming as an optimizing technique (see Example 8.2-3 for further discussion). PROBLEM SET 8.2A 1. Consider Problem 1, Set 8.1a dealing with the Fairville tax situation. Solve the problem, assuming that all five goals have the same weight. Does the solution satisfy all the goals? 2. In Problem 2, Set 8.1a, suppose that the goal of attracting young/middle-aged people is twice as important as either of the other two categories (teens and seniors). Find the associated solution, and check if all the goals have been met. 3. In the Ozark University admission situation described in Problem 3, Set 8.1a, suppose that the limit on the size of the incoming freshman class must be met, but the remaining 354 Chapter 8 Goal Programming requirements can be treated as flexible goals. Further, assume that the ACT score goal is twice as important as any of the remaining goals. (a) Solve the problem, and specify whether or not all the goals are satisfied. (b) If, in addition, the size of the incoming class can be treated as a flexible goal that is twice as important as the ACT goal, how would this change affect the solution? 4. In the Circle K model of Problem 4, Set 8.1a, is it possible to satisfy all the nutritional requirements? 5. In Problem 5, Set 8.1a, determine the solution, and specify whether or not the daily production of wheels and seats can be balanced. 6. In Problem 6, Set 8.1a, suppose that the market demand goal is twice as important as that of balancing the two machines, and that no overtime is allowed. Solve the problem, and determine if the goals are met. 7. In Problem 7, Set 8.1a, suppose that the production quota for the two products needs to be met, using overtime if necessary. Find a solution to the problem, and specify the amount of overtime, if any, needed to meet the production quota. 8. In the Vista City Hospital of Problem 8, Set 8.1a, suppose that only the bed limits represent flexible goals and that all the goals have equal weights. Can all the goals be met? 9. The Malco Company has compiled the following table from the files of five of its employees to study the relationship between income and age, education (expressed in number of college years completed), and experience (expressed in number of years in the business). Age (yr) Education (yr) Experience (yr) Annual income ($) 30 4 5 40,000 39 5 10 48,000 44 2 14 38,000 48 0 18 36,000 37 3 9 41,000 Use the goal programming formulation in Problem 10, Set 8.1a to fit the data into the linear equation y = b0 + b1x1 + b2x2 + b3x3. 10. Solve Problem 9 using the Chebyshev Method proposed in Problem 11, Set 8.1a. 8.2.2 The Preemptive Method In the preemptive method, the decision maker must rank the goals of the problem in order of importance. Given an rc-goal situation, the objectives of the problem are written as Minimize G, = p] (Highest priority) Minimize G„ = p„ (Lowest priority) The variable p, is either s* or s~ representing goal i. For example, in the TopAd model (Example 8.2-1), px = s\ and p2 = «2- The solution procedure considers one goal at a time, starting with the highest priority, Gu and terminating with the lowest, G„. The process is carried out such that 8.2 Goal Programming Algorithms 355 the solution obtained from a lower priority goal never degrades any higher priority solutions. The literature on goal programming presents a "special" simplex method that guarantees the nondegradation of higher priority solutions. The method uses the column-dropping rule that calls for eliminating a nonbasic variable x,- with Zj — c,- 0 from the optimal tableau of goal Gk before solving the problem of goal G^.The rule recognizes that such nonbasic variables, if elevated above zero level in the optimization of succeeding goals, can degrade (but never improve) the quality of a higher priority goal. The procedure requires modifying the simplex tableau so that it will carry the objective functions of all the goals of the model. The proposed column-dropping modification needlessly complicates goal programming. In this presentation, we show that the same results can be achieved in a more straightforward manner using the following steps: Step 0. Identify the goals of the model and rank them in order of priority: Gi = Pi > G2 = p2 > ... > G„ = p„ Set i = 1. Step i. Solve LP, that minimizes G„ and let p, = pj define the corresponding optimum value of the deviational variable p,. If i = n, stop; LP,, solves the n-goal program. Otherwise, augment the constraint p, = p* to the constraints of the G,-problem to ensure that the value of p, will not be degraded in future problems. Set i = i + 1, and repeat step i. The successive addition of the special constraints p, = p* may not be as "elegant" theoretically as the column-dropping rule. Nevertheless, it achieves the exact same result. More important, it is easier to understand. Some may argue that the column-dropping rule offers computational advantages. Essentially, the rule makes the problem smaller successively by removing variables, whereas our procedure makes the problem larger by adding new constraints. However, considering the nature of the additional constraints (p, = p*), we should be able to modify the simplex algorithm to implement the additional constraint implicitly through direct substitution of the variable p,. This substitution affects only the constraint in which p, appears and, in effect, reduces the number of variables as we move from one goal to the next. Alternatively, we can use the bounded simplex method of Section 7.3 by replacing p, = p- with p, < pj, in which case the additional constraints are accounted for implicitly. In this regard, the column-dropping rule, theoretical appeal aside, does not appear to offer a particular computational advantage. For the sake of completeness, however, we will demonstrate in Example 8.2-3 how the column-dropping rule works. Example 8.2-2 The problem of Example 8.2-1 is solved by the preemptive method. Assume that the exposure goal has a higher priority. 356 Chapter 8 Goal Programming StepO. Gi > G2 Step 1. Solve LP,. Step 2. Gil Minimize s{ (Satisfy exposure goal) G2: Minimize s2 (Satisfy budget goal) Minimize Gx subject to 4xj + 8x2 + si 8x. + 24x2 x, + 2x2 *1 sx = 45 (Exposure goal) + 5j - S2 = 100 (Budget goal) < 10 (Personnel limit) < 6 (Radio limit) 0 Xi, X2, Sj, 5l5 S2> s2 The optimum solution (determined by TORA) is xx = 5 minutes, x2 = 2,5 minutes, s\ = 5 million people, with the remaining variables equal to zero. The solution shows that the exposure goal, G,, is violated by 5 million persons. In LP,, we have pj = 5^. Thus, the additional constraint we use with the G2-problem is si = 5. We need to solve LP2, whose objective function is Minimize G2 = s2 subject to the same set of constraints as in step 1 plus the additional constraint s\ = 5. We can solve the new problem by using TORA's MODIFY option to add the constraint si = 5. The additional constraint si = 5 can also be accounted for by substituting out sx in the first constraint. The result is that the right-hand side of the exposure goal constraint will be changed from 45 to 40, thus reducing LP2 to Minimize G2 = s2 subject to 4x, + 8x2 - s} 8*1 + 24x2 + s2 - s2 Xi + 2x2 40 (Exposure goal) 100 (Budget goal) 10 (Personnel limit) 6 (Radio limit) x1: x2, Si, S2, S2 0 The new formulation is one variable less than the one in LPl5 which is the general idea advanced by the column-dropping rule. In reality, the optimization of LP2 is not necessary in this example because the optimum solution to problem G{ already yields s2 = 0. Hence, the solution of LP[ is automatically optimum for LP2 as well (you can verify this answer by solving LP2 with TORA). 8.2 Goal Programming Algorithms 357 Next, we use an example to show that a better solution for the problem of Example 8.2-2 can be obtained if the preemptive method is used to optimize objectives rather than to satisfy goals. The example also serves to demonstrate the column-dropping rule for solving goal programs. Example 8.2-3 The goals of Example 8.2-2 can be restated as Priority 1: Maximize exposure (Px) Priority 2: Minimize cost (P2) Mathematically, the two objectives are given as Maximize Px = 4xx + 8x2 (Exposure) Minimize P2 = &xx 4- 24x2 (Cost) The specific goal limits for exposure and cost ( = 45 and 100) are removed because the simplex method will determine them optimally. The new problem can thus be stated as Maximize Px = 4xx + Sx2 Minimize P2 = 8xx + 24x2 subject to xx + 2x-2 < 10 X\ ^6 Xi, X2 2: 0 We first solve the problem using the procedure introduced in Example 8.2-2. Step 1. Solve LP^ Maximize P\ = 4xx + 8x2 subject to xx + 2x2 < 10 xv < 6 xl5 x2 > 0 The optimum solution (obtained by TORA) is xx = 0, x2 = 5 with Px = 40, which shows that the most exposure we can get is 40 million persons. Step 2. Add the constraint 4xx + 8x2 s 40 to ensure that goal Gx is not degraded. Thus, we solve LP2 as Minimize P2 = Sxx + 24x2 358 Chapter 8 Goal Programming subject to *i + 2x2 < 10 x, < 6 4x; + 8x2 ^ 40 (Additional constraint) xb x2 — 0 The TORA optimum solution of LP2 is P2 = $ 96,000, Xj = 6 minutes, and x2 = 2 minutes. It yields the same exposure (Pa = 40 million people) but at a smaller cost than the one in Example 8.2-2 where the main objective is to satisfy rather than optimize the goals. The same problem is solved now by using the column-dropping rule. The rule calls for carrying the objective rows associated with all the goals in the simplex tableau. LPX (Exposure Maximization): The LP, simplex tableau carries both objective rows, P\ and P2. The optimality condition applies to the /^-objective row only. The P2-row plays a passive role in LP,, but must be updated with the rest of the simplex tableau in preparation for the optimization of LP2. LP, is solved in two iterations as follows: Iteration Basic x2 Sl Solution 1 /': ■4 -8 0 0 0 ^2 -8 -24 0 0 0 Si 1 2 1 0 10 1 0 0 1 6 2 Pi 0 0 4 0 40 Pi 4 0 12 0 120 x2 1 1 . - t 0 5 s2 1 0 (l 1 6 The last tableau yields the optimal solution x, = 0, x2 = 5, and P, = 40. The column-dropping rule calls for eliminating any nonbasic variable x, with Zj — Cj ^ 0 from the optimum tableau of LPj before LP2 is optimized. The reason for doing so is that these variables, if left unchecked, could become positive in lower priority optimization problems, which would degrade the quality of higher priority solutions. LP2 (Cost Minimization): The column-dropping rule eliminates s1 (with z} - c;- = 4). We can see from the /yrow that if s, is not eliminated, it will be the entering variable at the start of the P2-iterations and will yield the optimum solution xx = x2 = 0, which will degrade the optimum objective value of the iVproblem from P1 = 4010^ = 0. (Try it!) The ^-problem is of the minimization type. Following the elimination of , the variable xx with Zj — cf = 4 (>0) can improve the value of P2. The following table shows the LP2 iterations. The elements of Prrow has been deleted because the row no longer serves a purpose in the optimization of LP2. Comprehensive Problems 359 Iteration Basic Xl x2 *1 s2 Solution 1 P, 40 Pi 4 0 0 120 x2 l 1 0 5 s2 i 0 1 6 2 Pi 40 Pi 0 0 -4 96 x2 0 1 _[ 2 *1 1 0 1 6 The optimum solution (xx = 6, x2 = 2) with a total exposure of P1 = 40 and a total cost of P2 = 96 is the same as obtained earlier. PROBLEM SET 8.2B 1. In Example 8.2-2, suppose that the budget goal is increased to $110,000. The exposure goal remains unchanged at 45 million persons. Show how the preemptive method will reach a solution. 2. Solve Problem 1, Set 8.1a (Fairville tax model) using the following priority ordering for the goals: GL > G2 > G3 > G4 > G5. 3. Consider Problem 2, Set 8.1a. which deals with the presentation of band concerts and art shows at the NW Shopping Mall. Suppose that the goals set for teens, the young/middle-aged group, and seniors are referred to as G,, G2, and G3, respectively. Solve the problem for each of the following priority orders: (a) Gx> G2> G3 (b) G3 > G2 > Gi Show that the satisfaction of the goals (or lack of it) can be a function of the priority order. 4. Solve the Ozark University model (Problem 3, Set 8.1a) using the preemptive method, assuming that the goals are prioritized in the same order given in the problem. SELECTED REFERENCES Cohon,T. L., Multiobjective Programming and Planning, Academic Press, New York, 1978. Ignizio, J. P., and T. M. Cavalier, Linear Programming, Prentice-Hall, Upper Saddle River, NJ. 1994. Steuer, R. E., Multiple Criteria Optimization: Theory, Computations, and Application, Wiley, New York, 1986. COMPREHENSIVE PROBLEMS 8.11 The Warehouzer Company manages three sites of forestland for timber production and reforestation with the respective areas of 100,000,180.000, and 200,000 acres. The main 'Based on K. P. Rustagi, Forest Management Planning for Timber Production: A Goal Programming Approach, Bulletin No. 89, Yale University Press, New Haven, CT 1976. 360 Chapter 8 Goal Programming timber products include three categories: pulpwood, plywood, and sawlogs. Several reforestation alternatives are available for each site, each with its cost, number of rotation years (i.e., number of years from seedling size until harvesting), return from rent, and production output. The following table summarizes this information. Site Alternative Annual $/acrc Rotation yr Annual rnVacre Cost Rent Pulpwood Plywood Sawlogs 1 Al 1000 160 20 12 0 0 Al 800 117 25 10 0 0 A3 1500 140 40 5 6 0 A4 1200 195 15 4 7 0 A5 1300 182 40 3 0 7 A6 1200 180 40 2 0 6 Al 1500 135 50 3 0 5 2 Al 1000 102 20 9 0 0 Al 800 55 25 8 0 0 A3 1500 95 40 2 5 0 A4 1200 120 15 3 4 0 A 5 1300 100 40 2 0 5 A6 1200 90 40 2 0 4 3 ,41 1000 60 20 7 0 0 Al 800 48 25 6 4 0 A3 1500 60 40 2 0 4 A4 1200 65 15 2 0 3 A 5 1300 35 40 1 0 5 To guarantee sustained future production, each acre of reforestation in each alternative requires that as many acres as years in rotation be assigned to that alternative. The rent column represents the stumpage value per acre. The goals of Warehouzer are as follows: 1. Annual outputs of pulpwood, plywood, and sawlogs are 200,000,150,000, and 350,000 cubic meters, respectively. 2. Annual reforestation budget is $2.5 million. 3. Annual return from land rent is $100 per acre. How much land at each site should be assigned to each alternative? 8.2 A charity organization runs a children's shelter. The organization relies on volunteer service from 8:00 A.M. until 2:00 P.M. Volunteers may begin work at the start of any hour between 8:00 A.M. and 11:00 A.M. A volunteer works a maximum of 6 hours and a minimum of 2 hours, and no volunteers work during lunch hour between 12:00 noon and 1:00 P.M. The charity has estimated its goal of needed volunteers throughout the day (from 8:00 A.M. to 2:00 P.M., and excluding the lunch hour between 12:00 noon and 1:00 P.M.) as 15,16,18, 20, and 16, respectively. The objective is to decide on the number of volunteers that should start at each hour (8:00, 9:00,10:00,11:00, and 1:00) such that the given goals are met as much as possible. CHAPTER 9 Integer Linear Programming Integer linear programs (ILPs) are linear programs in which some or all the variables are restricted to integer (or discrete) values. ILP has important practical applications. Unfortunately, despite decades of extensive research, computational experience with ILP has been less than satisfactory. To date, there does not exist an ILP computer code that can solve integer programming problems consistently. ILLUSTRATIVE APPLICATIONS The ILP applications in this section start with simple formulations and then graduate to more complex ones. For convenience, we define a pure integer problem as the one in which all the variables are integer. Otherwise, the problem is a mixed integer program. Example 9.1-1 (Capital Budgeting) Five projects are being evaluated over a 3-year planning horizon. The following table gives the expected returns for each project and the associated yearly expenditures. Expenditures (million $)/yr Project 1 2 3 Returns (million $) 1 5 1 8 20 2 4 7 10 40 3 3 9 2 20 4 7 4 1 15 5 8 6 10 30 Available funds (million $) 25 25 25 Which projects should be selected over the 3-year horizon? 361 362 Chapter 9 Integer Linear Programming The problem reduces to a "yes-no" decision for each project. Define the binary variable x; as _ f 1, if project;' is selected 7 \0, if project j is not selected The ILP model is thus given as Maximize z = 20xj + 40x2 + 20x3 + 15x4 + 30x5 subject to 5x, + 4x2 + 3;c3 + 7x4 + 8x5 < 25 xx + lx2 + 9x3 + 4x4 + 6x5 < 25 8jcj + 10x2 + 2x, + x4 + 10x5 < 25 Xi,X2,X3,X4,X5 = (0,1) The optimum integer solution (obtained by TORA1) is xY = x2 = x3 = x4 = 1, x5 = 0, with z = 95 (million $). The solution shows that all but project 5 must be selected. It is interesting to compare the continuous LP solution with the ILP solution. The LP optimum, obtained by replacing x, = (0, 1) with 0 < x; < 1 for all /, yields Xi = .5789, x2 = x3 = x4 = 1, x5 = .7368, and z = 108.68 (million $). The solution is meaningless because two of the variables assume fractional values. We may round the solution to the closest integer values, which yields x1 = x5 = 1. However, the resulting solution is infeasible because the constraints are violated. More important, the concept of rounding should not apply here because x, represents a "yes-no" decision for which fractional values are meaningless. PROBLEM SET 9.1A2 1. In the capital budgeting model of Example 9.1-1, suppose that project 5 must be selected if either project 1 or project 3 is selected. Modify the model to include the new restriction and find the optimum solution with TORA. 2. Five items are to be loaded in a vessel. The weight wt and volume v, together with the value r, for item / are tabulated below. Item i Unit weight, w, (tons) Unit volume, v, (yd3) Unit worth, r, (100$) 1 5 1 4 2 8 8 7 3 3 6 f> 4 2 5 5 5 7 4 4 The maximum allowable cargo weight and volume are 112 tons and 109 yd3, respectively. Formulate the ILP model, and find the most valuable cargo using TORA. !To use TORA, select inceyei r i. ji aim-no from K»ia Menu. After inputting the problem (file Ch9ToraCapital BudgetEx9-l-l.txt), go to output screen and select Automated bib lo obtain the optimum solution. 2Problems 3 lo 6 are adapted from Malba Tahan, El Hombre Que Calculaba, Editorial Limusa, Mexico City, 1994, pp. 39-182. 9.1 Illustrative Applications 363 3. Suppose that you have 7 full wine bottles, 7 half-full, and 7 empty. You would like to divide the 21 bottles among three individuals so that each will receive exactly 7. Additionally, each individual must receive the same quantity of wine. Express the problem as an ILP constraint equations, and find a solution using TORA. (Hint: Use a dummy objective function in which all the objective coefficients are zeros.) 4. An eccentric sheikh left a will to distribute a herd of camels among his three children: Tarek receives at least one-half of the herd, Sharif gets at least one-third, and Maisa gets at least one-ninth.The remainder goes to a charity organization.The will does not specify the size of the herd except to say that it is an odd number of camels and that the named charity receives exactly one camel. How many camels did the sheikh leave in the estate, and how many did each child get? 5. A farm couple is sending their three children to the market to sell 90 apples with the objective of educating them about money and numbers. Karen, the oldest, carries 50 apples; Bill, the middle child, carries 30; and John, the youngest, carries only 10. The parents have stipulated five rules: (a) The selling price is cither $1 for 7 apples or $3 for 1 apple, or a combination of the two prices; (b) each child may exercise one or both options of the selling price; (c) each of the three children must return with exactly the same amount of money; (d) each child's income must be in whole dollars (no cents allowed); and (e) the amount received by each child must be the largest possible under the stipulated conditions. Given that the three children are able to sell all they have, how can they satisfy their parents' conditions? 6. Once upon a time, there was a captain of a merchant ship who wanted to reward three crew members for their valiant effort in saving the ship's cargo during an unexpected storm in the high seas. The captain put aside a certain sum of money in the purser's office and instructed the first officer to distribute it equally among the three mariners after the ship had reached shore. One night, one of the sailors, unbeknownst to the others, went to the purser's office and decided to claim (an equitable) one-third of the money in advance. After dividing the money into three equal shares, an extra coin remained, which the mariner decided to keep (in addition to one-third of the money). The next night, the second mariner got the same idea and, repeating the same three-way division with what was left, ended up keeping an extra coin as well.The third night, the third mariner also took a third of what was left, plus an extra coin that could not be divided. When the ship reached shore, the first officer divided what was left of the money equally among the three mariners, also to be left with an extra coin. To simplify things, the first officer put the extra coin aside and gave the three mariners their allotted equal shares. How much money was in the safe to start with? Formulate the problem as an ILP. and find the solution using TORA. (Hint: The problem has a countably infinite number of integer solutions. For convenience, assume that we are interested in determining the smallest sum of money that satisfies the problem. Then, boosting the resulting solution by 1, augment it as a lower bound and obtain the next smallest solution. Continuing in this manner, a general solution pattern will evolve.) 7. You have the following three-letter words: AFT, FAR,TVA, ADV, JOE, FIN, OSF.and KEN. Suppose that we assign numeric values to the alphabet starting with A = 1 and ending with Z = 26. Each word is scored by adding the numeric codes of its three letters. For example, AFT has a score of 1 + 6 + 20 = 27. You are to select five of the given eight words that yield the maximum total score. Simultaneously, the selected five words must satisfy the following conditions: /sum of letter 1 \ < /sum of letter 2\ /sum of letter 3\ \ scores J \ scores J \ scores J Formulate the problem as an ILP, and find the optimum solution using TORA. 364 Chapter 9 Integer Linear Programming 8. The Rccord-a-Song Company has contracted with a rising star to record eight songs. The durations of the different songs arc 8,3,5,5,9,6,7, and 12 minutes, respectively. Record-a-Song uses a two-sided cassette tape for the recording. Each side has a capacity of 30 minutes. The company would like to distribute the songs on the two sides in a balanced manner. This means that the length of the songs on each side should be about the same, as much as possible. Formulate the problem as an ILP, and find the optimum solution. 9. In Problem 8, suppose that the nature of the melodies dictates that songs 3 and 4 cannot be recorded on the same side. Formulate the problem as an ILP. Would it be possible to use a 25-minute tape (each side) to record the eight songs? If not, use ILP to determine the minimum tape capacity needed to make the recording. Example 9.1-2 (Fixed-Charge Problem) I have been approached by three telephone companies to subscribe to their long distance service in the United States. MaBell will charge a flat $16 per month plus $.25 a minute. PaBell will charge $25 a month but will reduce the per minute cost to $.21. As for BabyBell, the flat monthly charge is $18, and the cost per minute is $.22.1 usually make an average of 200 minutes of long-distance calls a month. Assuming that I do not pay the flat monthly fee unless I make calls and that I can apportion my calls among all three companies as I please, how should I use the three companies to minimize my monthly telephone bill? This problem can be solved readily without ILP. Nevertheless, it is instructive to formulate it as an integer program. Define Xi = MaBell long-distance minutes per month x2 = PaBell long-distance minutes per month x3 = BabyBell long-distance minutes per month yi = 1 if v: > 0 andOifxj = 0 y2 = lifx2 > 0 and0ifx2 = 0 y3 = 1 if x3 > 0 and 0 if x3 = 0 We can ensure that y, will equal 1 if x; is positive by using the constraint Xj < My,, j = 1, 2, 3 The value of M should be selected sufficiently large so as not to restrict the variables x; artificially. Because I make about 200 minutes of phone calls a month, then x, < 200 for all/, and it is safe to select M = 200. The complete model is Minimize z = .25x, + .21x2 + .22x3 4- 16y1 + 25y2 + 18y3 subject to xl + x2 + x3 — 200 x, < 200y, x2 < 200y2 9.1 Illustrative Applications 365 x3 < 200y3 xu x2, x3 > 0 y\, v2, y3 = (o, l) The formulation shows that the y'th monthly flat fee will be part of the objective function z only if yy- = 1, which can happen only if Xj > 0 (per the last three constraints of the model). If x; = 0 at the optimum, then the minimization of z, together with the fact that the objective coefficient of y7- is strictly positive, will force y, to equal zero, as desired. The optimum solution (file Ch9ToraFixedChargeEx9-l-2.txt) yields x3 = 200, y3 = 1, and all the remaining variables are equal to zero, which shows that BabyBell should be selected as my long-distance carrier. Observe that the information conveyed by y3 = 1 is redundant because the same result is implied by x3 > 0 (= 200). Actually, the main reason for using yh y2, and y3 is to account for the monthly flat fee. In effect, the three binary variables convert an ill-behaved (nonlinear) model into an analytically tractable formulation. This conversion has resulted in introducing the integer (binary) variables in an otherwise continuous problem. The concept of "flat fee" is typical of what is known in the literature as the fixed charge problem. PROBLEM SET 9.1B 1. Jobco is planning to produce at least 2000 widget on three machines. The minimum lot size on any machine is 500 widget. The following table gives the pertinent data of the situation. Machine Setup cost Production cost/unit Capacity (units) 1 300 2 600 2 100 10 800 3 200 5 1200 Formulate the problem as an ILP, and find the optimum solution using TORA. 2. Oilco is considering two potential drilling sites for reaching four targets (possible oil wells). The following table provides the preparation costs at each of the two sites and the cost of drilling from site i to target j (i = 1, 2; / = 1, 2, 3, 4). Drilling cost (million S) to target Sue 12 3 4 Preparation cost (million $) 1 2 18 5 5 2 4 6 3 1 6 Formulate the problem as an ILP, and find the optimum solution using TORA. 3. Three industrial sites are considered for locating manufacturing plants. The plants send their supplies to three customers. The supply at the plants and the demand at the 366 Chapter 9 Integer Linear Programming customers, together with the unit transportation cost from the plants to the customers, are given in the following table. 12 3 Supply 1 $10 $15 $12 1800 2 $17 $14 $20 1400 3 $15 $10 $11 1300 Demand 1200 1700 1600 In addition to the transportation costs, fixed costs also arc incurred at the rate of $12,000, $11,000, and $12,000 for plants 1,2, and 3, respectively. Formulate the problem as an ILP and find the optimum solution using TORA. 4. Repeat Problem 3 assuming that the demands at each of customers 2 and 3 are changed to 800. Example 9.1-3 (Set Covering Problem) To promote on-campus safety, the U of A Security Department is in the process of installing emergency telephones at selected locations. The department wants to install the minimum number of telephones provided that each of the campus main streets is served by at least one telephone. Figure 9.1 maps the principal streets (A to K) on campus. It is logical to place the telephones at the intersections of streets so that each telephone will serve at least two streets. Figure 9.1 shows that the layout of the streets requires a maximum of eight telephone locations. Define _ J1, a telephone is installed in location j J \0, otherwise 9.1 Illustrative Applications 367 The constraints of the problem require installing at least one telephone on each of the 11 streets (A to K).Thus, the model becomes subject to Minimize z = xx + x2 + x3 + x4 + X5 *6 + X-i + xg X] + x2 -1 (Streets) x2 + x3 1 (Street B) x4 + x5 > 1 (Street Q x1 + xs > 1 (Street D) Xb + Xj 1 (Street E) x2 + > 1 (Street F) Xj + x6 ■ 1 (Street G) x4 + x7 > 1 (Street H) X2 + x4 > 1 (Street T) x5 + xs > 1 (Street f) *3 + X5 > 1 (Street K) x, = (0, 1), 7 = 1, 2, ...,8 The optimum solution of the problem (obtained by TORA, file Ch9ToraSetCover Ex9-l-3.txt) requires installing four telephones at intersections 1,2,5, and 7. The problem has alternative optima. The preceding model is typical of what is generically known as the set covering problem. In this model, all the variables are binary. For each constraint, all the left-hand-side coefficients are 0 or 1, and the right-hand side is of the form (s=l). The objective function always minimizes + c2x2 + ... + c„xn, where c,- > 0 for all j = 1, 2, In the present example, c, = 1 for all 7. However, if c, represents the installa- tion cost in location j, then these coefficients may assume values other than 1. PROBLEM SET 9.1C 1. ABC is an LTL trucking company that delivers loads on a daily basis to five customers. The following table provides the customers associated with each route: Route Customers 1 1,2,3,4 2 4,3,5 3 1,2,5 4 2,3,5 5 1,4,2 6 1,3,5 368 Chapter 9 Integer Linear Programming The segments of each route are dictated by the capacity of the truck delivering the loads. For example, on route 1, the capacity of the truck is sufficient to deliver the loads to customers 1,2,3, and 4 only. The following table lists distances (in miles) among the truck terminal (ABC) and the five customers. ABC 1 2 3 4 5 ABC 0 10 12 16 9 8 1 10 0 32 8 17 10 2 12 32 0 14 21 20 3 16 8 14 0 15 18 4 9 17 21 15 0 11 5 8 10 20 18 11 0 The objective is to determine the least distance needed to make the daily deliveries to all five customers. Though the solution may result in a customer being served by more than one route, the implementation phase will use only one such route. Formulate the problem as an ILP and solve using TORA. 2. The U of A is in the process of forming a committee to handle the students' grievances. The directive received from the administration is to include at least one female, one male, one student, one administrator, and one faculty member. Ten individuals (identified, for simplicity, by the letters a to ;) have been nominated. The mix of these individuals in the different categories is given as follows: Category Individuals Females a, b, c, d, e Males f. g, h, i, j Students a,b,c,j Administrators e, f Faculty d, g, h, i The U of A wants to form the smallest committee with representation from each of the five categories. Formulate the problem as an ILP, and find the optimum solution using TORA. 3. Washington County includes six towns that need emergency ambulance service. Because of the proximity of some of the towns, a single station may serve more than one community. The stipulation is that the station must be within 15 minutes of driving time from the towns it serves. The table below gives the driving times in minutes among the six towns. 1 2 3 4 5 6 1 0 23 14 18 10 32 2 23 0 24 13 22 1 1 3 14 24 0 60 19 20 4 18 13 60 0 55 17 5 10 22 19 55 0 12 6 32 11 20 17 12 0 Formulate an ILP whose solution will produce the smallest number of stations and their locations. Find the solution using TORA. 9.1 Illustrative Applications 369 I I L r I I I I r FIGURE 9.2 Museum layout for Problem 4, Set 9.1c 4. The treasures of King Tut are on display in a museum in New Orleans. The layout of the museum is shown in Figure 9.2, with the different rooms joined by open doors. A guard standing at a door can watch two adjoining rooms. The museum wants to ensure guard presence in every room, using the minimum number possible. Formulate the problem as an ILR and find the optimum solution with TOR A. Example 9.1-4 (Either-or Constraints) Jobco uses a single machine to process three jobs. Both the processing time and the due date (in days) for each job are given in the following table. The due dates are measured from the zero datum, the assumed start time of the first job. Job Processing time (days) Due date (days) Late penalty $/day 1 5 25 19 2 20 22 12 3 15 35 34 The objective of the problem is to determine the minimum late-penalty sequence for processing the three jobs. Define Xj = Start date in days for job / (measured from the zero datum) The problem has two types of constraints: The noninterference constraints (guaranteeing that jobs are not processed concurrently) and the due date constraints. Consider the noninterference constraints first. Two jobs i and ;' with processing time p, and pt will not be processed concurrently if either*, > Xj + Pj or Xj x, + ph depending on whether job /precedes job i, or vice versa. Because all mathematical programs deal with simultaneous constraints only, we transform the either-or constraints by introducing the following auxiliary binary variable: _ fl, if i precedes j ' \0, if; precedes; For M sufficiently large, the either-or constraint is converted to the following simultaneous constraints Mytj + (x; - X,) > pj and M(l - y;/) + (xy - x,) > Pi 370 Chapter 9 Integer Linear Programming The conversion guarantees that only one of the two constraints can be active at any one time. If y,, = 0, the first constraint is active, and the second is redundant (because its left-hand side will include Af, which is much larger than pj). If ytj = 1, the first constraint is redundant, and the second is active. Next, the due date constraint is considered. Given d, is the due date for job /, let Sj be an unrestricted variable. Then, the associated constraint is \j + Pj + Sj = dj If Sj a: 0, the due date is met, and if Sj < 0, a late penalty is incurred. Using the substitution Sj Sj Sj, Sj, Sj — 0 the constraint becomes Xj + sj - sj = dj - Pj The late penalty cost is proportional to sj. The model for the given problem is Minimize z = I9s\~ + 12sJ + 34s; subject to *! - x2 + My12 > 20 -xx + x2 - My12 > 5 - M xx - x3 + My13 > 15 + x3 - My13 > 5 - M x2 — x3 + My23 & 15 - x2 + x3 - My23 > 20 - M Xi + sj - s\~ =25-5 x2 + s2 - s2 = 22 - 20 x3 + s3 — s3 =35 — 15 Xj, -^3) S] 5 iS1^ ? 5*25 A*2 j .S'3 — 0 Vl2, yi3, J23 = (0, l) The integer variables— y12, y13, and y23 —are introduced to convert the either-or constraints into simultaneous constraints. The resulting model is a mixed ILP. To solve the model, we choose M = 1000, a value that is larger than the sum of the processing times for all three activities. The optimal solution (obtained by TORA, file Ch9ToraEitherOrEx9-l-4.txt3) is xx = 20, x2, = 0, and x3 = 25. This means that job 2 starts at time 0, job 1 starts at time 20, and job 3 starts at time 25, thus yielding the optimal processing sequence 2 —>• 1 —»3. The solution calls for completing job 2 at time 0 + 20 = 20, job 1 at time = 20 + 5 = 25,andjob3at25 + 15 = 40 days. Job 3 is delayed by 40 - 35 = 5 days past its due date at a cost of 5 X $ 34 = $ 170. 3Because TORA does not accept a negative right-hand side, the variable (RHS-), whose value is always 1, assumes the role of the right-hand side of the constraints. 9.1 Illustrative Applications 371 PROBLEM SET 9.1 D 1. A game board consists of nine equal squares. You are required to fill each square with a number between 1 and 9 such that the sum of the numbers in each row, each column, and each diagonal equals 15. Use ILP to determine the number in each square such that no two adjacent numbers in any row, column, or diagonal are equal. Solve with TORA. 2. A machine is used to produce two interchangeable products. The daily capacity of the machine can produce at most 20 units of product 1 and 10 units of product 2. Alternatively, the machine can be adjusted to produce at most 12 units of product 1 and 22 units of product 2 daily. Market analysis shows that the maximum daily demand for the two products combined is 35 units. Given that the unit profits for the two respective products are $10 and $12, which of the two machine settings should be selected? Formulate the problem as an ILP, and find the optimum using TORA. (Note: This two-dimensional problem can be solved by inspecting the graphical solution space. This is not the case for the H-dimensional problem.) 3. Gapco manufactures three products, whose daily labor and raw material requirements are given in the following table. Required daily labor Required daily raw material Product (hr/unit) (lb/unit) 1 3 4 2 4 3 3 5 6 The profits per unit of the three products are $25, $30, and $22, respectively. Gapco has two options for locating its plant. The two locations differ primarily in the availability of labor and raw material as shown in the following table: Location Available daily labor (hr) Available daily raw material (lb) 1 100 100 2 90 120 Formulate the problem as a mixed ILP, and use TORA to determine the optimum location of the plant. 4. Consider the job-shop scheduling problem that produces two end products using a single machine. The precedence relationships among the eight operations are summarized in Figure 9.3. Let pf be the processing time for operations / (=1, 2, ...,«). The due dates, measured from the zero datum, for products f and 2, are dx and d2, respectively. An operation, once started, must be completed before another starts. Formulate the problem as a mixed ILP. Product 1 FIGURE 9.3 Precedence relationships for the job-shop situation of Problem 4, Set 9.Id S )-*- Product 2 372 Chapter 9 Integer Linear Programming 5. Jaco owns a plant in which three products are manufactured. The labor and raw material requirements for the three products are given in the following table. Required daily labor Required daily raw material Product (hr/unit) (lb/unit) 1 3 4 2 4 3 3 5 6 Daily availability 100 100 The profits per unit for the three products are $25, $30, and $45, respectively. If product 3 is to be manufactured at all, then its production level must be at least 5 units daily. Formulate the problem as a mixed ILP, and find the optimal mix using TORA. 6. Show how the nonconvex shaded solution spaces in Figure 9.4 can be represented by a set of simultaneous constraints. Then use TORA to find the optimum solution that maximizes z = 2xx + 3.y2 subject to the solution space given in (a). 7. Suppose that it is required that any k out of the following m constraints must be active: gi (xu x2, ..., xn) ■ bh i = 1, 2, ..., m Show how this condition may be represented. 8. In the following constraint, the right-hand side may assume one of the values, bx, b2, ... , and bm. g(xh x2, jc„) -: b2, .... or b,„ Show how this condition is represented. FIGURE 9.4 Solution spaces for Problem 6 Set 9.1d 9.2 INTEGER PROGRAMMING ALGORITHMS The ILP algorithms are based on exploiting the tremendous computational success of LP. The strategy of these algorithms involves three steps. Step 1. Relax the solution space of the ILP by deleting the integer restriction on all integer variables and replacing any binary variable y with the continuous range 0 < y < 1. The result of the relaxation is a regular LP. Step 2. Solve the LP, and identify its continuous optimum. 9.2 Integer Programming Algorithms 373 Step 3. Starting from the continuous optimum point, add special constraints that iteratively modify the LP solution space in a manner that will eventually render an optimum extreme point satisfying the integer requirements. Two general methods have been developed for generating the special constraints in step 3. 1. Branch-and-bound (B&B) method 2. Cutting plane method Although neither method is consistently effective computationally, experience shows that the B&B method is far more successful than the cutting plane method. This point is discussed further in this chapter. 9.2.1 Branch-and-Bound (B&B) Algorithm The first B&B algorithm was developed in 1960 by A. Land and G. Doig for the general mixed and pure ILP problem. Later, in 1965, E. Balas developed the additive algorithm for solving ILP problems with pure binary (zero or one) variables. The additive algorithm computations were so simple (mainly addition and subtraction) that it was hailed as a possible breakthrough in the solution of general ILP.4 Unfortunately, the algorithm failed to produce the desired computational advantages. Moreover, the algorithm, which initially appeared unrelated to the B&B technique, was shown to be but a special case of the general Land and Doig algorithm. This section will present the general Land-Doig B&B algorithm only. A numeric example is used to explain the details. Example 9.2-1 Maximize z = 5*1 + 4x2 subject to Xi + x2 s 5 10*1 + 6x2 < 45 x,, x2 nonnegative integer The lattice points (dots) in Figure 9.5 define ILP solution space. The associated LP problem, LPO, is defined by removing the integer restrictions. Its optimum solution is X] - 3.75, x2 = 1.25, and z = 23.75. Because the optimum LPO solution does not satisfy the integer requirements, the B&B algorithm modifies the solution space in a manner that eventually identifies the 4 A general ILP can be expressed in terms of binary (0-1) variables as follows. Given an integer variable x with a finite upper bound u (i.e., 0 s x < u ), then x = 2\ + 21y, + 22y2 + ... + 2*y* The variables y0. yu ... , and yk are binary, and the index k is the smallest integer satisfying 2t+1 —lau. 374 Chapter 9 Integer Linear Programming -l"2 FIGURE 9.5 ILP solution space of Example 9.2-1 ILP optimum. First, we select one of the integer variables whose optimum value at LPO is not integer. Selecting xt (=3.75) arbitrarily, the region 3 < x{ < 4 of the LPO solution space contains no integer values of xY and can be eliminated as nonpromising. This is equivalent to replacing the original LPO with two new LPs, LP1 and LP2, defined as LP1 space = LPO space + (xj s 3) LP2 space = LPO space + {xx > 4) Figure 9.6 depicts the LP1 and LP2 spaces. The two spaces contain the same feasible integer points of the original ILP, which means that, from the standpoint of the integer solution, dealing with LP1 and LP2 is the same as dealing with the original LPO. If we intelligently continue to remove the regions that do not include integer solutions by imposing the appropriate constraints (e.g., 3 < x, < 4 at LPO), we will eventually produce LPs whose optimum extreme points satisfy the integer restrictions. In effect, we will be solving the ILP by dealing with a succession of (continuous) LPs. The new restrictions, xx s 3 and x\ ^ 4, are mutually exclusive, so that LP1 and LP2 must be dealt with as separate LPs as Figure 9.7 shows. This dichotomization gives rise to the concept of branching in the B&B algorithm with x, being the branching variable. The optimum ILP lies in either LP1 or LP2. Hence, both subproblems must be examined. We arbitrarily examine LPl (associated with xY < 3) first. Maximize z = 5xY + 4x2 subject to x{ + x2 < 5 10xj + 6x2 < 45 xx < 3 xu x2 s 0 9.2 Integer Programming Algorithms 375 FIGURE 9.7 Using branching variable x{ to create LP1 and LP2 for Example 9.2-1 The solution of LP1 (which can be solved efficiently by the upper-bounded algorithm of Section 7.3) yields the optimum solution X[ = 3, x2 = 2, and z = 23 The LP1 solution satisfies the integer requirements for X\ and x2. Hence, LP1 is said to be fathomed. This means that LP1 need not be investigated any further because it cannot yield any better ILP solution. We cannot at this point say that the integer solution obtained from LP1 is optimum for the original problem because LP2 may yield a better integer solution (with a higher value of z). All we can say is that z = 23 is a lower bound on the optimum (maximum) objective value of the original ILP. This means that any unexamined subprob-lem that cannot yield a better objective value than the lower bound must be discarded as nonpromising. If an unexamined subproblem produces a better integer solution, then the lower bound must be updated accordingly. 376 Chapter 9 Integer Linear Programming Given the lower bound z = 23, we examine LP2 (the only remaining unexamined subproblem). Because optimum z = 23.75 at LPO and all the coefficients of the objective function happen to be integers, it is impossible that LP2 (which is more restrictive than LPO) will produce a better integer solution. As a result, we discard LP2 and conclude that it has been fathomed, The B&B algorithm is now complete because both LP1 and LP2 have been examined and fathomed (the first for producing an integer solution and the second for showing that it cannot produce a better integer solution). We thus conclude that the optimum ILP solution is the one associated with the lower bound—namely, xt = 3, x2 = 2, and z = 23. Two questions remain unanswered regarding the procedure: 1. At LPO, could we have selected x2 as the branching variable in place of X\? 2. When selecting the next subproblem to be examined, could we have solved LP2 first instead of LP1? The answer to both questions is "yes." However, ensuing computations could differ dramatically. Figure 9.8, in which LP2 is examined first, illustrates this point. The optimum LP2 solution is x, = 4, x2 = .83, and z = 23.33 (verify using TORA LP module). Because x2 (=.83) is nonintegcr, LP2 is investigated further by creating subproblems LP3 and LP4 using the branches x2 ^ 0 and x2 2= 1, respectively. This means that LP3 space = LP2 space + (x2 < 0) = LPO space + {x1 > 4) + (x2 < 0) LP4 space = LP2 space + (x2 s 1) = LPO space + (x, > 4) + (x2 ^ 1) We have three "dangling" subproblems that must be examined: LP1, LP3, and LP4. Suppose that we arbitrarily examine LP4 first. LP4 has no solution, and hence it is fathomed. Next, let us examine LP3. The optimum solution is xx = 4.5, x2 = 0, and z = 22.5. The noninteger value of xx (=4.5) leads to the two branches x} ^ 4 and X] > 5, and the creation of subproblems LP5 and LP6 from LP3. LP5 space = LPO space + [x1 > 4) + (x2 s 0) + (x, < 4) = LPO space + (x, = 4) + (x2 < 0) LP6 space = LPO space + (x, > 4) + (x2 s 0) + >5) = LPO space + (xv > 5) + (x2 < 0) Now. subproblems LP1, LP5, and LP6 remain unexamined. LP6 is fathomed because it has no feasible solution. Next, LPS has the integer solution (x, = 4, x2 = 0, z = 20) and, hence, yields a lower bound (z = 20) on the optimum ILP solution. We are left with subproblem LP1, whose solution yields a better integer (x2 = 3, x2 = 2. z = 23). Thus, the lower bound is updated to z = 23. Because all the subproblems have been fathomed, the optimum solution is associated with the most up-to-date lower bound—namely, xx = 3. x2 = 2, and z = 23. The solution sequence'in Figure 9.8 (LPO -h> LP2 -> LP4 LP3 ^ LP6 -» LP5 -> LP1) is a worst-case scenario that, nevertheless, may occur in practice. The example points to a principal weakness of the B&B algorithm: How do we select the next sub-problem to be examined, and how do we choose its branching variable? In Figure 9.7, we were lucky to "stumble" upon a good lower bound at the very first subproblem, LP1, thus allowing us to fathom LP2 without further computations and to terminate the B&B search. In essence, we completed the procedure by solving 9.2 Integer Programming Algorithms 377 LPO Xl = 3.75, x2 = 1.25, z = 23.75 LP 5 = 4, x2 = 0, z = 20 Lower bound LP 6 No feasible solution FIGURE 9.8 Alternative B&B tree for Example 9.2-1 one subproblem only. In Figure 9.8, we had to examine seven subproblems before the B&B algorithm could be terminated. Although there are heuristics for enhancing the ability of B&B to "guess" which branch can lead to an improved ILP solution (see Taha, 1975, pp. 154-171), there is no solid theory that will always yield consistent results, and herein lies the difficulty that plagues computations in ILP. Indeed in Section 9.2.2, Problem 1, Set 9.2b, demonstrates with the help of TORA the bizarre behavior of the B&B algorithm, even for a small 16-variable 1-constraint problem, where the optimum is found in 9 iterations (subproblems) but requires over 25,000 iterations to verify optimality. It is no wonder that to this day, and after four decades of research, available computer codes (commercial and academic alike) lack consistency (a la simplex method) in solving ILPs. We now summarize the B&B algorithm. Assuming a maximization problem, set an initial lower bound z = —oo on the optimum objective value of ILP. Seti = 0. Step 1. (Fathoming/bounding). Select LP/, the next subproblem to be examined. Solve LP*', and attempt to fathom it using one of three conditions. 378 Chapter 9 Integer Linear Programming (a) The optimal z-value of LP/ cannot yield a better objective value than the current lower bound. (b) LP/ yields a better feasible integer solution than the current lower bound. (c) LP/ has no feasible solution. Two cases will arise. (a) If LP/ is fathomed and a better solution is found, update the lower bound. If all subproblems have been fathomed, stop; the optimum ILP is associated with the current lower bound, if any. Otherwise, set i = i + 1, and repeat step 1. (b) If LP/ is not fathomed, go to step 2 for branching. Step 2. (Branching). Select one of the integer variables .t;, whose optimum value x* in the LP/ solution is not integer. Eliminate the region [**] < Xj < [x*] + 1 (where [v] defines the largest integer < v) by creating two LP subproblems that correspond to Xj < [x'j] and Xj s [x*] + 1 Set £ = i + l, and go to step 1. The given steps apply to maximization problems. For minimization, we replace the lower bound with an upper bound (whose initial value is z = +oo). The B&B algorithm can be extended directly to mixed problems (in which only some of the variables are integer). If a variable is continuous, we simply never select it as a branching variable. A feasible subproblem provides a new bound on the objective value if the values of the discrete variables are integer and the objective value is improved relative to the current bound. PROBLEM SET 9.2A 1. Solve the ILP of Example 9.2-1 by the B&B algorithm starting with x2 as the branching variable. Solve the subproblems with TORA using the MODIFY option for the upper and lower bounds. Start the procedure by solving the subproblem associated with Xn ^ [X2]. 2. Develop the B&B tree for each of the following problems. For convenience, always select as the branching variable at node 0. (a) Maximize z = 3x, + 2x2 subject to 2x, + 5x2 < 9 Ax{ + 2x2 < 9 Xu x2 2 0 and integer (b) Maximize z = 2x1 + 3x2 9.2 Integer Programming Algorithms 379 subject to 5xi + 7x2 S 35 4x, + 9x2 < 36 xu x2 > 0 and integer (c) Maximize z = xt + x2 subject to 2jc, + 5x2 < 16 6xj + 5x2 - 27 xl5 x2 a 0 and integer (d) Minimize z = 5xx + 4x2 subject to 3xt + 2x2 s 5 2x} + 3x2 a 7 X\, x2 a 0 and integer (e) Maximize z = 5x, + 7x2 subject to 2x, + x2 < 13 5x, + 9x, < 41 xl7 x2 > 0 and integer 3. Repeat Problem 2, assuming that x, is continuous. 4. Show graphically that the following ILP has no feasible solution, and then verify the result using B&B. Maximize z - 2xx + x2 subject to 10x, + 10x2 < 9 10x, + 5x2 > 1 x,, x2 a 0 and integer 5. Solve the following problems by B&B. Maximizes = lSxj + 14x, + Sx} + 4x4 subject to 15x, + 12x2 + 7x3 + 4x4 + xs < 37 xh x2, x3, x4, x5 = (0, 1) 9.2.2 TORA-Generated B&B Tree TORA integer programming module is equipped with a facility for generating the B&B tree interactively. To use this facility, select user-guided b&b in the output screen 380 Chapter 9 Integer Linear Programming FIGURE 9.9 Starting solution of the B&B tree in Example 9.2-1 of the integer programming module. The resulting screen provides all the information needed to create the B&B tree. Figure 9.9 shows the layout of the screen representing the root of the search tree, N10, which corresponds to LPO in Figure 9.6 (file ch9ToraB &BEx9-2-l.txt). Each node is identified by two digits, prefixed with the letter N. The left digit identifies the grid row in which the node resides, and the right digit gives a unique numeric value within the same row. Thus, N10 in Figure 9.9 shows that node 0 is situated in row 1 (which is the only node in this row). TORA limits the number of sub-problems per row to 10. The reasoning is that once this limit is reached, the tutorial nature of the interactive procedure becomes unwieldy. A message indicating that the algorithm is reverting to automatic mode is given whenever the number of subprob-lems per row exceeds 10. Keep in mind that in the automated mode, no limit is set in any way on the number of generated subproblems. The screen is now set for the selection of the branching variable by clicking any node tagged with "x?" Such nodes are highlighted in green. If you click anywhere in the entries of the node, the associated solution is exposed in the area on top of the B&B tree, as shown in Figure 9.10 where the solution of N10 shows that xx = 3.75 and x2 = 1.25. It also points out which variables are restricted to integer values. Clicking on either variable automatically creates two subproblems that correspond to the selected 9.2 Integer Programming Algorithms 381 FIGURE 9.10 Selection of the branching variable from the starting solution of Example 9.2-1 branching variable. Figure 9.11 shows the result of selecting jcj as the branching variable at N10. Node N20 (corresponding to xt s 3) and N21 (corresponding to .v, > 4) are added to the tree. Node N20 yields an integer solution, and hence it is fathomed. A fathomed node is highlighted in red or magenta. The magenta color is used if the fathomed node provides the current best lower bound, as is the case with node N20. Node N21 has not yet been fathomed, and clicking it will create further nodes in row 3 of the tree. The process continues until all nodes have been fathomed (highlighted in red or magenta). The top right box in the output screen automatically keeps track of the upper and lower bounds for the problem. The default calls for activating the bounds to fathom the nodes. TORA will automatically discard subproblems whose objective value violates the current bounds. However, you can deactivate the bounds (i.e., remove check in box) to create the entire search tree. In this case, a node is fathomed only if it yields an integer solution or if it is infeasible. It is important to note that in the search, TOR As automated B&B mode is coded to generate and scan subproblems on a strict LIFO basis. For this reason, most likely the user-guided search may lead to a more efficient search tree, mainly because the user invokes good judgment in selecting the next node to be investigated. 382 Chapter 9 Integer Linear Programming FIGURE 9.11 Creation of the first two subproblems in the B&B tree of Example 9.2-1 PROBLEM SET 9.2B 1. The following problem is designed to demonstrate the bizarre behavior of the B&B algorithm even for small problems. In particular, note how many subproblems are examined before the optimum is found and how many are needed to verify optimality. Minimize y subject to 2(x1 + x2 + ■•• + Xis) + y = 15 All variables are (0, 1) Use the automated option of TORA to answer the following: (a) How many subproblems are solved before the optimal solution is found? (b) How many subproblems are solved before the optimality of the solution found in (a) is verified? 2. Consider the following ILP: Maximize z = 18X] + 14x2 + 8x3 subject to 15x} + I2x2 + 7x3 < 43 x], x2, x3 nonnegative integers 9.2 Integer Programming Algorithms 383 Use TORA's B&B user-guided option to generate the search tree with and without activating the objective value bound. What is the impact of activating the objective value bound on the number of generated subproblems? For consistency, always select the branching variable as the one with the lowest index and investigate all the subproblems in a current row from left to right before moving to the next row. 3. Reconsider Problem 2 above. Convert the problem into an equivalent 0-1 TLP, and then solve it with TORA's automated option. Compare the size of the search trees in the two problems. 4. In the following 0-1ILP use TORAs user-guided option to generate the associated search tree. In each case, show how z-bound is used to fathom subproblems. Maximize z = 3.Vj + 2x2 — 5x3 — 2x4 + 3x5 subject to xx + x2 + x? + 2x4 + j:5<4 lxx + 3x3 - 4*4 + 3x5 < 8 Uxj - 6x2 + 3x4 — 3x5 > 3 Xj, x2, x3, x4, x5 = (0, 1) 5. Show by using TORA's user-guided option that the following problem has no feasible solution. Maximize z = 2x, + x2 subject to 10x, + 10x2 < 9 10x, + 5x2 > 1 *i, x2 = (0. 1) 6. Use TORA's user-guided option to generate the B&B tree associated with the following mixed ILP problem and give the optimum solution. Maximize z = xt + 2x2 - 3x3 subject to 3x, + 4*2 - x3 < 10 2*i - 3*2 + 4*, < 20 Xj, x2 nonnegative integers *3 > 0 7. Use TORA to generate the B&B tree for the following problem assuming that only one of the two constraints holds. Maximize z = x, + 2*2 — 3x3 subject to 20xj + 15*2 - x3 < 10 12*, + 3*2 + 4*3 13 X,, x2, x3 > 0 384 Chapter 9 Integer Linear Programming 8. Convert the following problem into a mixed ILP, and then use TORA to generate its B&B tree. What is the optimal solution? Maximize z = xx + 2x2 + 5x3 subject to |-xj + l(k2 - 3x3| > 15 2xi + x2 + x3 < 10 Xi, x2, x3 > 0 9.2.3 Cutting Plane Algorithm As in the B&B algorithm, the cutting plane algorithm also starts at the continuous optimum LP solution. Special constraints (called cuts) are added to the solution space in a manner that renders an optimum integer extreme point. In Example 9.2-2, we first demonstrate graphically how cuts are used to produce an integer solution and then implement the idea algebraically. Example 9.2-2 Consider the following ILP. Maximize z = 7x, + 10x2 subject to -x, + 3x2 < 6 lxx + x2 < 35 xu x2 s 0 and integer The cutting plane algorithm modifies the solution space by adding cuts that produce an optimum integer extreme point. Figure 9.12 gives an example of two such cuts. Initially, we start with the continuous LP optimum z = 66|, x\ = 4|, x2 = 3\ . Next, we add cut I, which produces the (continuous) LP optimum solution z = 62, xt = 4f, x2 = 3. Then, we add cut II, which, together with cut I and the original constraints, pro- FIGURE 9.12 Illustration of the use of cuts in ILP 9.2 Integer Programming Algorithms 385 duces the LP optimum z = 58, x, = 4, x2 = 3. The last solution is all integer, as desired. The added cuts do not eliminate any of the original feasible integer points, but must pass through at least one feasible or infeasible integer point. These are basic requirements of any cut. It is purely accidental that a 2-variable problem used exactly 2 cuts to reach the optimum integer solution. In general, the number of cuts, though finite, is independent of the size of the problem, in the sense that a problem with a small number of variables and constraints may require more cuts than a larger problem. Next, we use the same example to show how the cuts arc constructed and implemented algebraically. Given the slacks x3 and x4 for constraints 1 and 2, the optimum LP tableau is given as Basic Xi x2 *3 X4 Solution z 0 0 63 22 31 66| x2 0 1 00 1 22 3\ 1 0 1 22 3 4 The optimum continuous solution is z = 665, xx = 4-, x2 = 3§, x3 = 0, x4 = 0. The cut is developed under the assumption that all the variables (including the slacks x3 and x4 ) are integer. Note also that because all the original objective coefficients are integer in this example, the value of z is integer as well. The information in the optimum tableau can be written explicitly as z + §§x3 + j§*4 = 662 (z-equation) x2 + 22*3 + 23x4 = % fe-equation) xi ~ 22*3 + 1>X4 = ^2 (*i-equation) A constraint equation can be used as a source row for generating a cut provided its right-hand side is fractional. We also note that the z-equation can be used as a source row because z happens to be integer in this example. We will demonstrate how a cut is generated from each of these source rows, starting with the z-equation. First, we factor out all the noninteger coefficients of the equation into an integer value and a fractional component, provided that the resulting fractional component is strictly positive. For example, I = (2 + |) -I = (-3 + 1) The factoring of the z-equation yields z + (2 + |)x3 + (1 + |)x4 = (66 + i) Moving all the integer components to the left-hand side and all the fractional components to the right-hand side, we get z + 2x3 + lx4 - 66 = -52x3 - 2if4 + \ (1) Because x3 and x4 are nonnegative and all fractions are originally strictly positive, the right-hand side must satisfy the following inequality: 386 Chapter 9 Integer Linear Programming Next, because the left-hand side in Equation (1), z + 2x3 + lx4 - 66, is an integer value by construction, the right-hand side, — \^x3 — y\x4 + \, must also be integer. It then follows that (2) can be replaced with the inequality: This is the desired cut, and it represents a necessary condition for obtaining an integer solution. It is also referred to as the fractional cut because all its coefficients are fractions. Because x3 = x4 = 0 in the continuous LP tableau given above, the current continuous optimum violates the cut (because it yields \ < 0). Thus, if we add this cut to the optimum tableau, the resulting optimum extreme point moves the solution toward satisfying the integer requirements. Before showing how a cut is implemented in the optimal tableau, we will demonstrate how cuts can also be constructed from the constraint equations. Consider the j^-row: Factoring the equation yields *1 + ("1 + !)*3 + (0 + |)*4 = (4 + l) The associated cut is 22-^2 — 22-^4 + 2 — 0 Similarly, the x,-equation , _7_ , J_ _ al is factored as x2 + (0 + £)x3 + (0 + ~)xA = 3 + | Hence, the associated cut is given as _i___i_ , i _ n Any of the three cuts given above can be used in the first iteration of the cutting plane algorithm. As such, it is not necessary to generate all three cuts before selecting one. Arbitrarily selecting the cut generated from the ,\'2-row, we can write it in equation form as —^x3 — y,x4 + s\ = —\, sL s 0 (Cut I) This constraint is added as a secondary constraint to the LP optimum tableau as follows: Basic x1 x3 JC4 j, Solution z 0 o 1 Ji 0 66] 0 1 g 31 1 0 -5 o • 0 0 ~a -a i The tableau is optimal but infeasible. We apply the dual simplex method (Section 4.4) to recover feasibility, which yields 9.2 Integer Programming Algorithms 387 Basic *1 Xl x3 x4 Solution z 0 0 0 1 9 62 X2 0 1 0 0 1 3 *1 1 0 0 1 _i *S 0 0 1 i 22 7 If The last solution is still noninteger in xx and x3. Let us arbitrarily select x{ as the next source row—that is, x, + (0 + i)x4 + (-1 + f)5l = 4 + | The associated cut is The dual simpL 1 -7X4 - 6 1 ■ s2 = 4 -7. S2 > 0 (Cut II) Basic Xl x2 xl x4 S] s2 Solution z 0 0 0 1 9 (I 62 x2 *1 Ü 1 0 1 0 0 Ü 0 1 0 1 7 1 1 1 —1 1 0 0 0 3 4| 1| 0 0 {) -I -= I : method yields the following tableau: Basic Xl x2 xl *4 s2 Solution z 0 0 0 0 3 7 58 Xl Xl X} xA 0 1 0 0 1 0 0 0 0 0 1 0 0 0 0 1 1 -1 -4 6 0 1 i -7 3 4 1 4 The optimum solution (x, = 4, x2 = 3, z = 58) is all integer. It is not accidental that all the coefficients of the last tableau are integers. This is a typical property of the implementation of the fractional cut. It is important to point out that the fractional cut assumes that all the variables, including slack and surplus, are integer. This means that the cut deals with pure integer problems only. The importance of this assumption is illustrated by an example. Consider the constraint 1 1 13 xl "t" 3X2 — 2 xb x2 ^ 0 and integer From the standpoint of solving the associated ILP, the constraint is treated as an equation by using the nonncgative slack sx —that is, 1 1 1 _ 13 X, i 2X2 '5} — 2 388 Chapter 9 Integer Linear Programming The application of the fractional cut assumes that the constraint has a feasible integer solution in all xx, x2 and s{. However, the equation above will have a feasible integer solution in JCt and x2 only ifs} is noninteger. This means that cutting-plane algorithm will show that the problem has no feasible integer solution, even though the variables of concern, X\ and x2, can assume integer feasible values. There are two ways to remedy this situation. 1. Multiply the entire constraint by a proper constant to remove all the fractions. For example, multiplying the constraint above by 6, we get 6xj + 2x2 < 39 Any integer solution of x, and x2 automatically yields integer slack. However, this type of conversion is appropriate for only simple constraints because the magnitudes of the integer coefficients may become excessively large in some cases. 2. Use a special cut, called the mixed cut, which allows only a subset of variables to assume integer values, with all the other variables (including slack and surplus) remaining continuous. The details of this cut will not be presented in this chapter (see Taha, 1975, pp. 198-202). PROBLEM SET 9.2C 1. In Example 9.2-2, show graphically whether or not each of the following constraints can form a legitimate cut: (a) x: + 2x2 < 10 (b) 2x, + x2 < 10 (c) 3x2 < 10 (d) 3*i + x2 < 15 2. In Example 9.2-2, show graphically how the following two (legitimate) cuts can lead to the optimum integer solution: x, + 2x2 < 10 (Cut I ) 3x, + x2 < 15 (Cut IT) 3. Express cuts I and II of Example 9.2-2 in terms of xx and x2, and show that they are the same ones used graphically in Figure 9.12. 4. In Example 9.2-2, derive cut II from the xrrow of the tableau resulting from the application of cut I. Use the new cut to complete the solution of the example. 5. Show that, even though the following problem has a feasible integer solution in xt and x2. the fractional cut would not yield a feasible solution unless all the fractions in the constraint have been eliminated. Maximize z = xx + 2x2 subject to *i + h £ f Xj, x2 2 0 and integer 9.2 Integer Programming Algorithms 389 6. Solve the following problems by the fractional cut, and compare the true optimum integer solution with the solution obtained by rounding the continuous optimum. (a) Maximize z = \X\ + 6x2 + 2x3 subject to 4xj - Ax2 =£ 5 -xx + 6x2 s 5 -x] + x2 + x3 < 5 x], x2, x3 s 0 and integer (b) Maximize z = 3xt + x2 + 3x3 subject to -xx + 2x2 + x3 s 4 4x2 - 3x3 < 2 Xy — 3x2 + 2x3 < 3 xbx2,x3 > 0 and integer 9.2.4 Computational Considerations in ILP To date, and despite over 40 years of research, there does not exist a computer code that can solve ILP consistently. Nevertheless, of the two solution algorithms presented in this chapter, B&B is more reliable. Indeed, practically all commercial ILP codes are B&B-based. Cutting plane methods are generally difficult and uncertain, and the roundoff error presents a serious problem. Though attempts have been made to improve the cutting plane computational efficacy, the end results are not encouraging. In most cases, the cutting plane method is used in a secondary capacity to improve B&B performance at each subproblem. The most important factor affecting computations in integer programming is the number of integer variables and the feasible range in which they apply. Because available algorithms are not consistent in producing a numeric ILP solution, it may be advantageous computationally to reduce the number of integer variables in the ILP model as much as possible. The following suggestions may prove helpful: 1. Approximate integer variables by continuous ones wherever possible. 2. For the integer variables, restrict their feasible ranges as much as possible. 3. Avoid the use of nonlincarity in the model. The importance of the integer problem in practice is not yet matched by reliable solution algorithms. It is unlikely that a new theoretical breakthrough will be achieved in the area of integer programming. Instead, new technological advances in computers (such as parallel processing) may offer the best hope for improving the efficiency of ILP codes. 390 Chapter 9 Integer Linear Programming 9.3 SOLUTION OF THE TRAVELING SALESPERSON PROBLEM In the obvious sense, the traveling salesperson problem deals with finding the shortest (closed) tour in an rc-city situation where each city is visited exactly once. The problem, in essence, is an assignment model with additional restrictions that guarantee the exclusion of subtours in the optimum solution. Specifically, in an /r-city situation, define _ j 1, if city j is reached from city i '' (0, otherwise Given dtj is the distance from city i to city j, the traveling salesperson model is given as n n Minimize z = 2 X('--v.'- = 00 f°r ' = / ttpl subject to n 2x i? —» f? —>W is the optimum loop. Production loop Total cleanup time W^Y^>B->R^W 10 + 19 + 25 + 45 = 99 W^-Y^R-^B^W 10 + 18 + 20 + 50 = 98 W^>-B^Y->R->W 17 + 44 + 18 + 45 = 124 W^B^R^Y^W 17 + 25 + 40 - 20 = 102 W^R^B^-Y^-W 15 + 20 + 44 + 20 = 99 W-*R-*Y-*B-*W 15 + 40 + 19 + 50 = 124 Exhaustive enumeration of the loops is not practical in general. Even a modest-sized 11-city problem will require enumerating 10! = 3,628,800 tours, a demanding task indeed. For this reason, the problem must be formulated and solved in a different manner, as we will show later in this section. To develop the assignment-based formulation for the paint problem, define Xjj = 1 if paint j follows paint i and zero otherwise 392 Chapter 9 Integer Linear Programming Letting M be a sufficiently large positive value, we can formulate the Rainbow problem as Minimize z = Mxww + \0xWY + 17xWB + 15xWK + 2(kw + MxYY + V)xYB + 18xYR +50xBW + 44xBY + MxBB + 25xHK + 45xRW + 40xRY + 20xRB + MxRR subject to xww + xWY + xWB + XWR = 1 x^y 4" xYY ~\~ XYB XYR = 1 xbw + xdy + XHli + XBR = 1 XRW + XRY + Xrb + XRR ~ 1 Xww + XYW ^ XBw + XRW = 1 xwy + xyy + XBY + XRY = 1 •^H'B + XYB + XBg + XRB = 1 XWR + XYR + XBR + XRR = 1 Xa = (0, 1) for all i and j Solution is a tour (loop) The use of M in the objective function guarantees that a paint job cannot follow itself. PROBLEM SET 9.3A 1. A manager has a total of 10 employees working on six projects.There are overlaps among the assignments as the following table shows: The manager must meet all 10 employees once a week to discuss their progress. Currently, the meeting with each employee lasts about 20 minutes—that is. a total of 3 hours and 20 minutes for all 10 employees. A suggestion is made to reduce the total time by holding group meetings, depending on the projects the employees share. The 9.3 Solution of the Traveling Salesperson Problem 393 manager wants to schedule the projects in a way that will reduce the traffic (number of employees) in and out of the meeting room. How should the projects be scheduled? 2. A book salesperson who lives in Basin must call once a month on four customers located in Wald, Bon, Mena, and Kiln. The following table gives the distances in miles among the different cities. Basin Wald Bon Mena Kiln Basin 0 120 220 150 210 Wald 120 0 80 110 130 Bon 220 110 0 160 185 Mena 150 110 160 0 190 Kiln 210 130 185 190 0 The objective is to minimize the total distance traveled by the salesperson. Formulate the problem as an assignment-based ILP. 3. Circuit boards (such as those used with PCs) are fitted with holes to allow mounting different electronic components. The holes are drilled with a movable drill. The following table provides the distances (in centimeters) between pairs of 10 holes of a specific circuit board. The objective is to determine the optimum sequence for drilling all the holes. /- 1.2 .5 2.6 4.1 3.2 1.2 — 3.4 4.6 2.9 5.2 .5 3.4 — 3.5 4.6 6.2 2.6 4.6 3.5 — 3.8 .9 4.1 2.9 4.6 3.8 — 1.9 \3.2 5.2 6.2 .9 1.9 Formulate the problem as an assignment-based ILP. 9.3.1 B&B Solution Algorithm The idea of the B&B algorithm is to start with the solution of the associated assignment problem. If the solution is a tour, then there is nothing more to be done and the process ends. Otherwise, we need to introduce restrictions that remove the subtours. This can be achieved by creating as many branches as the number of x,(-variables associated with one of the subtours. Each branch will then correspond to setting one of the variables of the subtour to zero (recall that all the variables associated with a subtour equal l).The solution of the resulting assignment problem may or may not produce a tour. If it docs, we use its objective value as an upper bound on the true minimum tour length. If it does not, further branching will be necessary, again creating as many branches as the number of variables in one of the subtours. The process continues until all unexplored subproblems have been fathomed, either by producing a better (smaller) upper bound or because there is evidence that the subproblem cannot produce a better solution. The optimum tour is the one associated with the best upper bound. The following example provides the details of the traveling salesperson B&B algorithm. 394 Chapter 9 Integer Linear Programming Example 9.3-2 The matrix below summarizes the distances in a 5-city traveling salesperson problem. \\d„\\ = ( 00 10 3 6 9 \ 5 OG 5 4 2 4 9 00 7 8 7 1 3 oc 4 \ 3 2 6 5 CO 1 We start by solving the associated assignment (using TORA), which yields the following solution: z = 15, (x13 = x31 = 1), (;t25 = x54 = x42 = 1), all others = 0 This solution yields two subtours: (1-3-1) and (2-5-4-2) as shown at node 1 in Figure 9.14.The associated total distance is z = 15, which provides a lower bound on the optimal length of the 5-city tour. A straightforward way to determine an upper bound is to select any tour and then sum its respective distances to obtain an upper bound estimate. For example, the tour 1-2-3-4-5-1 (selected totally arbitrarily) has a total length of 10 + 5 + 7 + 4 + 3 = 29. (You may be able to find a better upper bound by inspection. Remember that the smaller the upper bound, the more efficient the B&B search.) The calculation of the lower and upper bounds now tells us that the optimum length of the tour must lie in range (15,29). A solution that yields a tour length larger than 29 is discarded as nonpromising. To eliminate the subtours at node 1, we need to "disrupt" its loop by forcing its member variables, x„, to zero level. Subtour 1-3-1 is broken if we impose x13 = 0 or x31 = 0 (i.e., one at a time) on the assignment problem at node 1. Similarly, subtour FIGURE 9.14 B&B solution of the traveling salesperson problem of Example 9.3-2 z = 15 (l-3-l)(2-5-4-2) xn = 0 *31 = 0 5 ) z = 16 (1-3-4-2-5-1) 9.3 Solution of the Traveling Salesperson Problem 395 2-5-4-2 is eliminated by imposing one of the restrictions x25 = 0, x54 = 0, or x42 = 0. In terms of the B&B tree, each of these restrictions gives rise to a branch and hence a new subproblem. It is important to notice that branching both subtours at node 0 is not necessary. Instead, only one subtour needs to be disrupted at any one node. The idea is that a breakup of one subtour automatically alters the member variables of the other sub-tour and hence produces conditions that are favorable to creating a tour. Under this argument, from the computational standpoint, preference is given to the shortest subtour because it creates the smallest number of branches. Targeting the shorter subtour (1-3-1), two branches x13 = 0 and x3] - 0 are created at node 1. The associated assignment problems are constructed by removing the row and column associated with the zero variable, which will make the assignment problem smaller. Another way of achieving the same result is to leave the size of the assignment problem unchanged and simply assign an infinite distance to the branching variable. For example, the assignment problem associated with x13 = 0 requires substituting d{3 = oo in the assignment model at node 0. Similarly, for x31 = 0, we substitute d31 = oo. In Figure 9.14, we arbitrarily solve the subproblem associated with x3l = 0. Node 2 gives the solution z = 17 but continues to produce the subtours (2-5-2) and (1-4-3-1). Repeating the procedure we made at node 1 gives rise to two branches: x25 = 0 and x52 = 0. We now have three unexplored subproblems, one from node 1 and two from node 2, and we are free to investigate any of them at this point. Arbitrarily exploring the subproblem associated with x2S = 0 from node 2, we set dl3 = oo and d2S = oo in the original assignment problem, which yields the solution z = 21 and the tour solution 1-4-5-2-3-1 at node 3. Node 3 need not be investigated any further and hence is fathomed. The solution at node 3 provides an improved upper bound, z = 21, on the optimal length of the tour. This means that any unexplored subproblem that can be shown to yield a tour length larger than (or equal to) 21 must be discarded as nonpromising. We now have two unexplored subproblems. Selecting subproblem 4 for exploration, we set d[3 = oc and d52 = oo in the original assignment, which yields the tour solution 1-4-2-5-3-1 with z = 19. The new tour solution provides the better upper bound z = 19. Only subproblem 5 remains unexplored. Substituting d3y = oo in the original assignment problem at node 1, we get the tour solution 1-3-4-2-5-1 with z = 16, at node 5. Once again, this is a better solution than the one associated with node 3 and thus requires updating the upper bound to z = 16. There arc no remaining unfathomed nodes, which completes the search tree. The optimal tour is the one associated with the current upper bound: 1-3-4-2-5-1 with length 16 miles. One remark is in order: The search sequence 1 —» 2 —» 3 -> 4 —» 5 for exploring the nodes demonstrates once again one of the difficulties associated with the B&B algorithm. We have no way of predicting in advance which sequence we should follow to explore subproblems in the B&B tree. For example, had we started with node 5, we would have obtained the tight upper bound z = 16, which will automatically fathom subproblem 2 and hence eliminate the need to create subproblems 4 and 5. Of course, there are heuristics that can be of help in "foreseeing" which sequence could lead to a more efficient tree. For example, after specifying all the branches from a given node, we can start with the branch associated with the largest dtj among all the created branches. This heuristic calls for exploring branch x3] =0 at node 0. Had this been done, the upper bound z = 16 would have been encountered at the first subproblem. 396 Chapter 9 Integer Linear Programming PROBLEM SET 9.3B 1. Solve Example 9.3-2 using subtour 2-5-4-2 to start the branching process at node 0 and the following sequences for exploring the nodes. (a) Explore all the subproblems horizontally from left to right in each tier before proceeding to the next tier. (b) Follow each path vertically from node 0 until it ends with a fathomed node. 2. Solve Problem 1, Set 9.3a using B&B. 3. Solve Problem 2, Set 9.3a using B&B. 4. Solve Problem 3, Set 9.3a using B&B. 9.3.2 Cutting Plane Algorithm The idea of the cutting plane algorithm is to add a set of constraints, which when added to the assignment problem are guaranteed to prevent the formation of a subtour. The additional constraints are defined as follows. In an rc-city, associate a continuous variable Uj(>0) with cities 2, 3, ... , and n. Next, define the required set of additional constraints as U[ — Uj + nxtj £ n — 1, i = 2, 3, n; j = 2, 3, ..., n\ i ¥= j These constraints, when added to the assignment model, will automatically remove all subtour solutions but will not eliminate any tour solution. Example 9.3-3 Consider the following distance matrix of a 4-city traveling salesperson problem. loo 13 21 26 \ 10 oc 29 20 30 20 oo 5 V12 30 7 oo/ The associated LP consists of the assignment model constraints plus the following additional constraints that prevent the formation of subtour solutions. All xtj = (0, 1) and all w,- > 0. The problem is solved as a mixed integer linear program. *11 X\7 *13 x14 X21 x22 *23 *24 *31 *?2 *33 *34 x„ x42 *43 *44 ": «3 «4 4 1 -1 S3 4 1 -1 £3 4 -1 1 <3 4 1 -1 <3 4 -1 1 s3 4 -1 1 S3 The optimum solution, obtained by TORA's ILP module (file Ch9ToraTraveling SalespersonEx9-3-3.txt), is given as u2 = 0, «3 = 1, u4 — 2, xl2 = X23 = xM = x41 = 1, tour length = 59 Comprehensive Problems 397 This corresponds to the tour solution 1-2-3-4-1. The solution satisfies all the additional constraints in us (verify!). To show that subtour solutions do not satisfy the additional constraints, consider the subtour solution (1-2-1, 3-4-3). This solution corresponds to xl2 = xlx = 1, x34 = x43 - 1. Now, consider constraints 4 and 6 in the tableau above—namely, 4*34 + «3 - «4 S 3 4x43 - M3 + «4S3 Substituting x34 = x43 = 1 and summing the two inequalities yields 8 < 6, which is impossible, thus disallowing the formation of the subtour. The main disadvantage of the cutting plane model is that its size grows exponentially with the number of cities. For this reason, the B&B algorithm offers a more efficient way for solving the problem. PROBLEM SET 9.3C 1. Solve the following traveling salesperson problem by the cutting plane algorithm. (a) \\