back start next
[start] [1] [2] [3] [4] [5] [6] [7] [8] [9] [10] [11] [12] [13] [14] [15] [16] [17] [18] [19] [20] [21] [22] [23] [24] [25] [26] [27] [28] [29] [30] [31] [32] [33] [34] [35] [ 36 ] [37] [38] [39] [40] [41] [42] [43] [44] [45] [46] [47] [48] [49] [50] [51]
36 The Benders decomposition procedure (described in the Appeiidix inathematical note 8.1) requires the solution of the dual of problem (8.38), which can be stated as: maximize {S,)u„ + 1 ( . ,« subject to (8.40) for all ij,k,£ u,j 0 for all iJ and is unrestricted in sign for all i, k, £. Because problem (8.38) is to be solved efiiciently by solving an independent transportation problem (8.39) for each commodity, the optimal dual solution to problem (8.38) must be synthesized from the optimal solutions for problem (8.39), one for each commodity. Let the dual variables of problem (8.39) associated with the supply constraints. An optimal solution to problem (8.40) is: u* = (8.41a) 7r,tf = maxj fM*  for all i,k,£. (8.41b) Conditions (8.41a) and (8.41b) are derived in the Appendix, mathematical note 8.2. The necessary results are now in place for stating the solution procedure. The Algorithm Step 0 Select a suboptimality tolerance parameter < 0. Initialize UB = +00, LB =  cx), = 0. If zeroone vectors and z are available (as from a heuristic solution procedure) that satisfy constraints (8.34) through (8.36), go to Step 2. Otherwise, proceed to Step 1. Step 1 Solve the Benders master problem, denoted problem (BDD), in the and z variables given by: minimize B,y,z (8.42) subject to constraints (8.34) through (8.36) and: ,2 = or I for all k,£. (8.43) (8.44) If the value of expression (8.45) is less than the curtent upper bound UB, replace UB by the value of expression (8.45) and store (y"+z" *, A"+) as the new incumbent solution. Terminate if UB  LB t; the incumbent solution is an eoptimal solution of problem (DD). Otherwise, go to Step 3. Step 3 Determine an optimal dual solution to problem (8.38) with = "* using equations (8.41). The necessary data for equations (8.41) are available from having solved problem (8.39) for each commodity in Step 2. Denote the dual solution by (u set H = H+ 1, and return to Step 1. Figure 8.7 is a schematic of the algorithm. The procedure sequentially identifies improved designs of the distribution system until it is determined that ho significant cost improvement can be achieved. It is assumed that problem (8.38), and therefore problem (8.39), is feasible for every choice of yifi satisfying constraint (8.34). This is ensured if 2 ii 2 for all i (if not, the design problem is infeasible) and if all possible Jk links are in the model. (However, as discussed, impracticable combinations of indices should be dropped if possible.) These assumptions suffice to guarantee that problem (8.39) is feasible for each / and therefore has a finite minimum value for any zeroone satisfying constraint (8.34). Convergence of the algorithm is guaranteed for any e 0 because problem (DD) possesses a finite minimum Denote an optimal solution by z"\y"). SctLB = B"; LB is a lower bound on the optimal value of the distribution design problem (DD), denoted by v[DD]. Terminate if UB LB f; the incumbent solution is an optimal solution of problem (DD). Otherwise, proceed to Step 2. Step 2 Solve the xpartition of problem (DD), given by problem (8.38), with = + by solving the independent classical transportation problems given by problem (8.39). Denote the optimal solution to problem (8.38) as x" and the optimal value: Z (X 2 ( I J I as T(y"+<). Then following the properties discussed in the Appendix, mathematical note 8.1, an upper bound on v[DD] is given by: 2 (/a4" + V, 2 2 ) + "). (8.45)
MASTER PROBLEM (configuration generator) Solve problem (BBD"). Thereby find the best sites to establish distribution centers and the best assignments of demand zones to those centers. Do this using the accumulated cost estimating information in constraints (8.43) in lieu of any direct knowledge of transportation and production/handling costs (c„„s) and supply and demand levels (5,/s and /s). Trial Location/Assignment Configuration of the System, ie, (z"+,y"+) New Cost Estimating Relationship, ie, new * constraint in set of constraints (8.43), to provide additional indirect information about the xpartition of problem (DD) Use the trial configuration to find optimal associated transportation flows x,;u by solving an independent transportation problem (8.39) for each commodity. TRANSPORTATION SUBPROBLEMS (configuration evaluator) Find best flows Find best flows for first commod for second comity modity First subproblem Second subproblem Find best flows for last commodity Last subproblem Figure 8.7 Schematic of the Decomposition Procedure. (Adapted from: GeolTrion, Graves, and Lcc, 1982, in INFOR 20:287314.) and the extreme pointgenerating problem (8.40) has a finite number of extreme points. Insights from the information processing system dehneated in Figure 8.7 suggest the following variant of the algorithm. When is small in the master problem, problem (BDD"), too little information is included by way of the transportation dual variables and , h = l,...,H, about transportation subproblems to justify optimizing the master problem. There are too few constraints in the master problem to expect that the optimal value will provide a sharp lower bound on the optimal value of the design problem. Thus the current master problem is solved only to the extent that a feasible solution is produced having a value less than UBt. A lower bound LB is therefore no longer available, thus inactivating the termination criterion in Step 2. Termination in Step 1 occurs if problem (BDD") has no feasible solution with a value of below UBi. This scheme implies an adaptive increase in the optimization of the master problem. The minimal value of the solution to the master problem increases as H increases and the "threshold" UBt decreases with each minimize E (/,z, + v, X ) new incumbent. The master problem in Step 1 becomes feasibilityseeking only, ie, a feasible solution is sought for: UB. > 2(Xz,+v, E X E S (.IMy,, if I S  E S "A h = 1,..., (8.46) J together with constraints (8.34) through (8.36), and (8.44). Any convenient objective function in and z could be augmented to these constraints to produce a feasible solution. A natural choice is to use the latest costestimating relationship, which is the H function on the righthand side of constraint (8.46). This choice has proved computationally sound. The master problem, in Step 1, then becomes: minimize + . X E .eV«)E S l{"kiD,i)y,l X uu y2 I e Ike i j subject to (8.47) constraints (8.34) through (8.36), (8.44), and (8.46). Problem (8.47) is conveniently a pure zeroone integer programming problem. Problem (BDD") is a mixedinteger programming problem due to the inclusion of B. This adds to the advantage of using problem (8.47). To repeat, the minimize instruction in (8.47) is not to be taken seriously because it is only a feasible solution that is required. Example 8.7 The structure of a twostage distribution system is exempHfied in Figure 8.8. We will associate the location of each distribution system entity with the coordinates of that entity in Figure 8.8. For example, distribution center site 2 is at (4,3). There are two commodities. To preserve the visual appeal of the figure, the average unit cost of producing and shipping commodity i from plant j through DC at site to demand zone 2 is arbitrarily defined as the rectangular distance involved for commodity 1, and that plus 2 for commodity 2. Values of the c,, are thus obtained. These and other problem parameters are given in Table 8.8. Although this lis a miniature distribution design problem, there are already 64 variables. There are 16 zeroone variables, 48 transportation variables, and 39 constraints. No constraints of type (8.36) are included. Step 0 Set 1/5= boo, LJ5 = oo, and = 0. To force an optimal solution, set £ = 0 for the example. Step 1 As = 0, solve:
Plants (/ = 1,2) DC Sites (k = 1,2,3,4) Customer Zones (8=1,2,3) 123456789 10 Figure 8.8 TwoStage Distribution System Structure. subject to constraints (8.34), (8.35), and (8.44), which is: minimize 3000z, + ... + SOOOz + I75j,, + 350.V2, b ... b 150 2 + ... + 950.V33 + 475j.43 subject to  + 2, +   +    + 22 +   + 42    + 23 +   + 43   175 ,,  + 75,2   475,3  < 650z,  175 ,  + 75>22   475 23  650Z2  175.V3,  + 75   47533  < 650Z3  175 „  + 75)42   47543  =5" 650z4  175;;,,  + 75.v,2   475.v,3  lOOzi   + 7522   475 23  > IOOZ2  1753,  + 75 2   475  IOOZ3  175.V4,  + 75>42   47543  S= IOOZ4 
8.3 TWOSTAGE, MULTICOMMODITY DISTRIBUTION SYSTEM 209 Table 8.8 Data for Example 8.5. = 1.7 = 1 DC Data 100 650 3000 2 100 650 3000 2 100 650 3000 1 coefficients in objective function (8.31) £ 600 50 600 50 yi),y2i,y3i,y4i,yi2,,y33,y43,z„Z2,Z3,Z4 = 0 0 1. The optimal solution (found using a zeroone integer programming computer code) is y,, = ,42 = 43 = z, = z4 = 1 and all other variables equal to zero. This is (y,z). The optimal objective value is 6725 and so LB = 6725, presently. Step 2 We have iI) = 1, T<(2) = 4, and (3) = 4. The objective function coefficients for the transportation subproblems are given below.
[start] [1] [2] [3] [4] [5] [6] [7] [8] [9] [10] [11] [12] [13] [14] [15] [16] [17] [18] [19] [20] [21] [22] [23] [24] [25] [26] [27] [28] [29] [30] [31] [32] [33] [34] [35] [ 36 ] [37] [38] [39] [40] [41] [42] [43] [44] [45] [46] [47] [48] [49] [50] [51]

