The Benders decomposition procedure (described in the Appeiidix inath-ematical 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 f-M* - 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 zero-one 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 e-optimal 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 zero-one 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 x-partition 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 x-partition 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:287-314.)

and the extreme point-generating 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 UB-t. 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 UB-i. 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" UB-t decreases with each

minimize E (/,z, + v, X )

new incumbent. The master problem in Step 1 becomes feasibility-seeking 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 cost-estimating relationship, which is the H function on the right-hand 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 zero-one integer programming problem. Problem (BDD") is a mixed-integer 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 two-stage distribution system is ex-empHfied 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 zero-one 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 Two-Stage 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

8.3 TWO-STAGE, MULTI-COMMODITY 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 zero-one 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.