The Multi-Supplier Delivery Scheduling Problem: Heuristics and Lower Bounds By Nejib Ben Kheder Candace A. Yano The University of Michigan Technical Report 90-4 February 1990

The Multi-Supplier Delivery Scheduling Problem: Heuristics and Lower Bounds By Nejib Ben Kheder Candace A. Yano Department of Industrial & Operations Engineering The University of Michigan Ann Arbor, MI 48109-2117 Technical Report 90-4 February 1990 Abstract We consider the problem of scheduling the deliveries of high-volume suppliers of an assembly facility. The problem is formulated as a multiple-choice problem. We seek to find the best choice of delivery pattern for each supplier considering the cost of the individual schedules and the cost of overtime of dock workers. We suggest a lower bounding procedure based on surrogate relaxation. The multiperiod problem is transformed into a single period problem using surrogate multipliers. The tightness of our lower bounding procedure depends on our ability to derive good surrogate multipliers. We show that for a two-constraint problem such multipliers can be computed exactly. The solution for the two-constraint problem is incorporated into an iterative heuristic for computing multipliers for problems with more than two constraints. In addition to providing tight lower bounds, the surrogate multipliers can also be used in several heuristics. We perform a series of experiments to test the effectiveness of the lower bounding procedure and the quality of the heuristics. We also discuss the computational complexity of the algorithms. This work has been supported in part by a research contract from a domestic automotive manufacturer.

1. Introduction We consider the problem of scheduling the deliveries of high-volume suppliers of an assembly facility of a major US manufacturer. Mixed carload shipments are sent by truck directly from each supplier to the assembler. The inbound freight is unloaded at the docks. All workers at the docks handle all the incoming freight with no distinction between suppliers. The unloading employees can work overtime, if necessary, for which an overtime premium is incurred. The manufacturer negotiates with each supplier a day-of-week delivery schedule. These schedules specify the timing and contents of the shipments. We assume a set of candidate delivery patterns has been generated for each supplier. Each delivery pattern corresponds to a detailed schedule to which we assign a cost equal to the sum of inventory and transportation costs induced by such procurement schedule, and a daily load equal to the total daily freight load. The generation and costing of the delivery patterns are discussed in a separate paper (Ben-Kheder and Yano [90]). In this paper, we seek to find the best assignment of delivery patterns to suppliers considering the cost of the individual schedules and the cost of overtime. We formulate the problem as a multiple choice problem. The side constraints correspond to the resource constraints for each period of time in the planning horizon. By allowing overtime, the capacity in each period becomes a decision variable and the problem is said to be a variable resource (VR) problem. The fixed resource (FR) version of the problem is a multidimensional 0-1 knapsack problem with multiple choice constraints. Manne [58] first formulated a multi-item scheduling problem as a multiple choice problem. He suggested solving the continuous version and showed that a near-optimal solution is obtained, provided the number of items far exceeds the number of periods. In such a case, the number of fractional variables is shown to be limited. Solutions to the original problem are obtained by rounding the solution of the linear programming (LP) relaxation, or by interpreting the fractional solution as a convex combination of candidate schedules. Bitran and Matsuo [86] derived bounds on the error resulting from Manne's approximation schemes for both the fixed and variable resource problems. Multi-item lot-sizing problems usually involve scheduling the production of thousands of items for which a large number of potential schedules can be generated. Dzielenski and Gomory [65] suggested solving Manne's large LP by Dantzig-Wolfe decomposition. This method does not guarantee a principally integer solution until optimality. This deficiency is corrected in the Lasdon and Terjung [71] revised simplex procedure. The principal disadvantage -1

of the LP relaxation is its limitation to the case where the number of periods is negligible compared to the number of items, and the existence of split lots (fractional solution). It is not clear how to modify such a solution to obtain good operational schedules. For our multi-supplier delivery schedule (MSDS) problem, the number of suppliers is relatively small. This is true in a just-in-time context where the supply networks have few direct suppliers. In addition, the planning horizon is usually limited to one or two weeks, especially if MSDS is solved in the context of establishing trucking contract alternatives based on repeating schedules. The number of fractional variables in the LP solution may be relatively high and the LP relaxation would be less effective for this type of problem. However, the problem is NPcomplete and remains too large (potentially thousands of 0-1 variables) to be solved to optimality. We concentrate our efforts on developing simple heuristic procedures and a good lower bounding procedure to evaluate the heuristic solutions. We suggest a lower bounding procedure based on surrogate relaxation. The multiperiod problem is transformed into a single period problem using surrogate multipliers. The singleconstraint problem is a variant of the one-dimensional knapsack problem where a penalty cost is incurred for exceeding the knapsack capacity. The tightness of our lower bounding procedure depends on our ability to derive good surrogate multipliers. If the optimal surrogate multipliers are known, then the bound generated by the surrogate relaxation is known to be better than or equal to the bounds generated by Lagrangian and linear relaxations (Glover [75]). We show that for a two-constraint (2C) problem such multipliers can be computed exactly. An ascent direction is identified each time one of the constraints is violated and a search along the direction is performed. The solution for the 2C-problem is incorporated into an iterative heuristic for computing multipliers for problems with more than two constraints. In addition to providing tight lower bounds, the surrogate multipliers can also be used in several heuristics. One such heuristic is the "bang-for-buck ratio" heuristic. This ratio is clearly defined for a single knapsack. The definition can be extended to the multiple knapsack case by considering the surrogate constraint as a single-constraint representation of the multiple constraints of the problem. Alternatively, since overtime is allowed, the single-constraint surrogate problem solution can be easily converted to a feasible solution to the original problem. The quality of both heuristic solutions depends on the ability of the surrogate constraint to capture the aggregate level of resource consumption and availability. In the remainder of this paper, we will first state the multiple choice formulation of MSDS and discuss the relevant literature on multidimensional knapsack problems. We will then define the -2

surrogate problem and suggest an approach to derive good surrogate multipliers. We will also discuss how to adapt existing solution procedures for the single knapsack, fixed-resource problem to solve the variable resource case, and how to derive good solutions for the multidimensional problem from the analysis of the one-dimensional problem. Finally, we test the effectiveness of our lower bounding scheme both in terms of computation times and quality of the bounds, and the quality of the heuristic solutions. 2. The multi-supplier delivery scheduling problem: a multiple choice formulation The MSDS problem can be stated as: S Ki H Minimize, I CikYik + Y Wh Vh (1) i=1 k=1 h=l s.t. S Ki X LikhYik <Rh + Vh, h=1,..,H; (2) i=lk=l Ki XYik= 1, i=1,..,S; (3) k=1 Yik = 0 or 1, i=,..,S; k=,..,Ki; (4) Vh>0, h=1,..,H; (5) where S: total number of suppliers, Ki: total number of candidate delivery schedules for supplier i, Yik: 0-1 variable equal to 1 if schedule k is assigned to supplier i, Likh: workload at the docks induced by supplier i-schedule k in period h, Cik: cost of supplier i-schedule k, Vh: overtime labor in period h, Rh: regular workload capacity at the docks in period h, and W h: cost per unit of overtime in period h. Constraints (2) are the variable resource constraints; they ensure that overtime is incurred whenever the total workload exceeds the regular capacity for a given period. Constraints (3) are the multiple choice constraints, which in combination with constraints (4), state that one and only -3

one schedule is chosen for each supplier. Constraints (5) imply that no cost savings or penalties are incurred when undertime occurs in a period. If we assume a fixed capacity and disregard overtime, the problem can be viewed as a multidimensional 0-1 knapsack problem with multiple choice constraints (MMCK.) Such a problem has been addressed by Sinha and Zoltners [79], as an extension of their elaborate branch and bound (B&B) procedure to solve the one-dimensional problem. They suggest a very basic surrogate relaxation procedure. The most violated constraint in the trivial solution composed of the minimum cost alternative in each multiple choice set is chosen to be the surrogate constraint. As we will see later, this simplistic method to derive surrogate multipliers results in poor lower bounds. Most of the research on multiconstraint knapsack problems deals with the 0-1 problem without multiple choice constraints. Early work by Gilmore and Gomory [66] and Weingartner and Ness [67] has focused on dynamic programming (DP) based algorithms. More recently, Shih [79] and Gavish and Pirkul [85] developed B&B algorithms that take advantage of the structure of the problem, and are easier to conceptualize and more convenient to use than previous algorithms. The efficiency of the B&B procedures depends strongly on the lower bounding scheme used. Gavish and Pirkul [85] present several methods for computing lower bounds. They include Lagrangian, surrogate and composite relaxation. Based on extensive computational results, it is shown that for the 0-1 integer problem with few knapsack constraints, surrogate relaxation is a viable alternative to the more commonly used Lagrangian and LP relaxations. We observed in preliminary tests that similar results hold for the multiple choice version of the problem, provided good surrogate multipliers can be computed efficiently. Once a set of multipliers is computed, we need to solve a one-dimensional (single) multiple choice knapsack problem (SMCK). Due to the significant number of applications of this problem (menu planning, capital budgeting and catalog planning, for example), extensive theoretical and empirical investigations have led to the development of highly efficient solution procedures. DP procedures have been suggested by Dudzinski [84] and Bean [87]. Alternatively, Nauss [78] suggest a B&B procedure based on a relaxation of the multiple choice constraints. Sinha and Zoltners [79] and Dyer et al. [84] use the LP relaxation, for which linear time algorithms have been proposed by Zemel [84], Dyer [84] and Dudzinski and Walukiewicz [84]. In the next section, we will extend some of the theoretical results of Gavish and Pirkul to our problem and suggest various heuristics to compute surrogate multipliers. We will also discuss how to adapt the fixed-resource SMCK algorithm to solve the variable-resource case. -4

3 Surrogate reaation of MSDS In the following, we will use a matrix representation of the problem. We rewrite MSDS as: Min CY + WV (P) s.t. LY<R+V YEI,Ve R+ where Y is the decision vector with K 0-1 elements, V is the overtime vector with H non-negative elements, L is the H x K workload matrix, C and R are, respectively, the cost and dock capacity vectors of conforming dimensions, and' is the set defined by all 0-1 and multiple choice constraints in the decision vector Y. We will also denote by Lh the workload vector in period h. The surrogate relaxation of problem P associated with a given set of multipliers u (20) is Min CY + WV (SPO) s.t. v)(LY- R - V) < 0 Yep,Ve R+ If we define z(-) to be the value of an optimal solution to problem ( ), then z(SPu) can be easily proven to be a lower bound on z(P). The best bound is given by the solution to the surrogate dual: Sup )o0 z(SPu). (S) The idea of surrogate relaxation was first introduced by Glover [65] but did not receive as much attention as the more widely known Lagrangian relaxation, for which very simple search procedures have been developed and extensively tested on a variety of optimization problems. Considerably less experience has been accumulated with surrogate relaxation. Renewed interest in surrogate relaxation has been triggered by the work of Karwan and Rardin [79], who show that the surrogate bound is in general strictly tighter than the Lagrangian bound. In a more recent paper [84], they adapt some of the ideas in a Lagrangian dual search (e.g., subgradient optimization) and develop several general surrogate multiplier search procedures. We propose an -5

alternate search method based on an efficient procedure to derive the optimal surrogate multipliers for the two-constraint problem. Our procedure is similar to the one developed by Gavish and Pirkul [85] for the 0-1 problem, which has also been applied to the general knapsack problem by Pirkul and Narasimhan [86]. 3.1 Derivation of optimal multipliers for a two-constraint problem We consider the following two-dimensional knapsack problem: Min CY + W1 V1 + W2 V2 (P2) s.t. L1 Y< R + V1 (6) L2 Y< R2 + V2 (7) Ye~ V1,V2>0 and its surrogate relaxation for a pair of multipliers (y, l): Min CY + Wl V1 + W2 V2 (SPy4) s.t. (y L1 + g L2) Y < (y R1 + I R2) + ( V1 + A V2) Y E v V, V2 0 We assume that constraints (6) and (7) are linearly independent. We also assume that constraint (6) is violated by the solution to SP01, and that constraint (7) is violated by the solution to SP10, i.e., both y* and A* are positive. Otherwise an optimal solution to the surrogate problem has been found. The dual problem can be rewritten as: Sup o>0 v(SPi1) (D2) In the following we investigate some of the properties of the solution to SP1j. Lemma 1: Let j < W2/W1. Then an optimal solution to SP1i has V2=0. Similarly, if > > W2/W1 then an optimal solution to SP1L has V1=0. Proof: See Appendix. -6

Suppose I < W2/W1. As a result of Lemma 1, SP1I can be rewritten as: Min C Y + w v s.t. aY<r+v Ye, V > 0 where w=Wi, v=Vl, r=R1+LR2 and a=L1+gL2. In the remainder of this paper, we will refer to problem as the surrogate multiple choice knapsack problem, SMCK(a,r,w). In the following, for simplicity, we will assume that j < W2/W1. Similar results hold for the opposite case ( >W2/W1), which can be obtained by reindexing the constraints. Lemma 2: Let (Y,V) be an optimal solution to SPj1. Then at most one constraint is violated by this solution. Proof: See Appendix. Lemma 3: Let (Y,V) be an optimal solution to SP1L that does not satisfy constraint (1). Then Ai* ~ A, where A* denotes the optimal multiplier. Proof: See Appendix. Lemma 4: Let (Y,V) be an optimal solution to SP1, that does not satisfy constraint (2). Then A* > L. Proof: See Appendix. Lemmas 2, 3 and 4 identify an improving direction for the dual problem when one of the constraints is violated. For the special case where j=W2/W1, SP1l has an infinite number of solutions in terms of overtime values (V1 and V2). Let (Y*,Vi*,V2*) be one such solution and let v=Vl*+JV2*. Then any feasible solution (Y*,V1,V2) that satisfies v=Vl+LV2 is also optimal. In order to check the feasibility of the surrogate solution with respect to the original problem P2, we use the following values of the overtime variables: Vl=Min(v,Max(O,L1Y*-Rl)) and V2=(v-V1)/L. If L1Y* < R1 + V1 and L2Y* < R2 + V2 then LJ*=gL. Otherwise it can be shown that at most one of the constraints is violated and a search direction is then identified using results similar to Lemmas 3 and 4. -7

The theoretical results established in the preceding lemmas lead to the following procedure to compute an e-interval that contains the optimal multipliers. Procedure SI: (single multiplier, integer knapsacks) Step 0: (a) Solve SMCK(L2,R2,W2). If the solution satisfies L1Y < R1 then y*=0 and g*=1. Terminate. Otherwise let y*=1 and go to (b). (b) Solve SMCK(L1,R1,W1). If the solution satisfies L2Y < R2 then g*=0. Terminate. Otherwise go to step 1. Step 1: Let W=W2/W1. Solve SMCK(L1+IL2, R1+ilR2,W1). Let V1 = Min (v, Max(O,LiY-R1)) and let V2 = (v-V1)/L. If L1Y < R1 + V1 and L2Y < R2 + V2 then L*=W2/W1. Terminate. If L1Y > R1 + V1 then mmax=W2/W1 and gUmin=O. Go to step 2. If L2Y > R2 + V2 then mmax=M (large number) and lmin=W2/Wi. Go to step 2. Step 2: If (4max - lmin) < e, terminate. Otherwise go to step 3. Step 3: Update.. Let 1 = 1lmin + (Amax - gmin)/2. Solve SMCK(LI+LL2, Rl+uR2,w) where w=Min(W1,W2/l). If w=W1 then let Vi=v and V2=0. Otherwise let V1=0 and V2=v/4. If L1Y< RI+V1 and L2< R2 + V2 then,*=,. Terminate. If LY > R1 + V1 then gmax=g. Go to step 2. If L2Y > R2 + V2 then Lmin=p- Go to step 2. The performance of this iterative procedure depends on how p. is updated at each iteration. Here, we have suggested a bisection method. The search interval [pmax,pmin] is reduced by half at each iteration. If the initial interval has a range Ap and if the tolerance is equal to e, then the algorithm would require O(log2(AP./e)) iterations before termination. Alternatively, if a golden section search is performed then the interval is reduced by the ratio (2/(1+45)) at each iteration. -8

At each iteration of SI, a one-dimensional multiple choice knapsack problem would have to be solved to optimality, which can be time consuming, since a B&B procedure has to be executed. It is therefore preferable to compromise on the quality of the dual bounds in order to have a more efficient procedure. We suggest solving the linear relaxation of SMCK, LSMCK, at each iteration. The 0-1 constraints are relaxed and the continuous version of the knapsack is solved. The multipliers obtained by such a procedure can be shown to be equal to the dual multipliers of the LP relaxation of the original two-constraint problem. Therefore the bound obtained would be equal to the LP bound. A better bound can be obtained by using the dual multipliers to generate a surrogate constraint and solving the resulting surrogate problem as a 0-1 problem. In the following, we will refer to the modified SI procedure, where SMCK is replaced by LSMCK as SL (single multiplier, linear knapsacks). Besides being solvable in a linear time, the continuous knapsack problem, LSMCK, offers the possibility of using sensitivity analysis and an efficient reoptimization procedure to solve successive problems. This is described below. The LSMCK problem: solution approach and sensitivity analysis As mentioned earlier the LSMCK problem with fixed resources has received a great deal of attention (see Dudzienski and Walukiewicz [87] for a recent literature review). The problem is usually solved in two phases. First, some of the variables are eliminated from the problem (set equal to zero or one) using dominance criteria. The reduction scheme consists of comparing the cost-to-weight ratios of variables belonging to the same multiple choice set; this is achieved by first sorting the variables. This operation, which constitutes the time consuming part of the reduction S scheme, can be performed in running time O( KilogKi). In the next step, the dual of the reduced i=l problem is solved. It is shown that the optimal dual multiplier can only take a finite number of values, which can be determined a priori. The set of potential dual multipliers is ordered and a median search for the optimal value is performed. At each iteration, the median is checked for optimality. If it is not optimal then it is shown that half of the values in the set can be disregarded from further consideration and as a consequence half of the variables can be eliminated from the problem. As a result, the search for he optimal value is reported (see Dyer[84], for example) to be O(K), where K is the total number of variables in the reduced problem. -9

The dual problem of LSMCK may be formulated as: S Min r- X)i (DSMCK) i=1 s.t. Vi - aik8 < Cik 0<8<w which can be rewritten as a minimization of a convex, piecewise linear function: S Min f(t) = Min O<<w (r8 - M Min (Cik + aik 8, k=l,..,Ki) ) i=1 S Mino<8<w (r6 - fi() ) i=l where fi() = Min (Cik + aik 8, k=1,..,Ki) It is easy to see from the structure of f(8) that a minimum occurs at either a breakpoint 6 = Cik - Cik' aik - aik' (0 < 8 < w) for some multiple choice set i, or at one of the bounds (0 or w). The two aik - aik' extreme cases (8 = 0 and w) correspond to trivial solutions which can be checked easily for optimality, as discussed below. Trivial solutions: 1. Let fi = Minl<k<Ki Cik and let k'(i) = argmin [ aik, l<k<Ki I Cik=fi. The minimum cost alternative in set i is k'(i). Ties are broken by choosing the alternative with minimum total resource consumption. This solution is optimal if it results in no overtime, i.e., if S Z aik'(i) < r, then an optimal solution to LSMCK is given by i=l Yik'(i) =1 i=,..,S Yik =0 otherwise and v = 0. 2. Let gi = Min ( Cik + w aik, l<k<Ki ) and let k"(i) = argmax ( aik, 1<k<Ki I Cik+waik = gi ) Assuming that the solution results in overtime, k"(i) is the minimum (total) cost alternative in set i. The ties are broken by choosing the alternative with minimum individual cost. This solution is - 10

s optimal if it results in positive overtime, i.e., if A aik"(i) > r, then an optimal solution to LSMCK i=1 is given by Yik"(i) =1 i=1,..,S Yik =0 otherwise S and v = r- aik"(i). i=1 This is the only case where the optimal solution has positive overtime. Both trivial solutions are integer, and therefore are optimal to the integer problem as well. In general the solution to the continuous problem has two fractional variables. Next we describe how the solution is determined in the non-trivial case. Optimalitv conditions: The convex piecewise-linear function f(6) achieves its minimum at 6* if its left gradient, af(6*), is non-positive and its right gradient, af'(6*), is non-negative. The gradients at 6* are given by: S af(6*) = r- X Max (aik I Cik + 8* aik = fi(8*)) i=1 S and af+(6*) = r- E Min aik I Cik + 8* aik = fi(6*)) i=1 Ci*k" - Ci*k' The minimum is obtained at a breakpoint 6* - Ci*k - ik' for some set i*, and some variable ai*k' - ai*k" indices k' and k" in the set i* (we assume ai*k' < ai*k"). The optimal solution to the primal problem is obtained as follows: Yik =1 for (k I fi(6*) = Cik + 6* aik for i # i*) = a for k=k" and i=i* = 1- a for k=k' and i=i* =0 otherwise. r- Xaik Yik - ai*k' i* i* where a = is determined so that Xaik Yik + a ai*k" + (1-a) ai*k' = r. ai*k" - ai*k' i.i* i~i* -11

Dominance Criteria: In the fixed resource case, it has been shown that the problem is reduced using the following results: For a given set i: 1. If aik < ail and Cik < Cil then there exists an optimal solution with Yil = 0. In such a case, any solution containing alternative k will cost less than any solution containing alternative 1, since alternative 1 consumes more resources and costs more than alternative k. Cik- Cil Cil-Cip 2. If aik < ail < aip and CA- <il Cil-il then there exists an optimal solution with Yil =0. In this ail-aik aip-ail case, it can be shown that for any value 8 of the dual multiplier, the reduced cost of alternative 1, Cil + 5ail, is greater than either the reduced cost of alternative k or the reduced cost of alternative p. Therefore it is never selected. Further variable elimination can be achieved in the variable resource version of the problem, where we can show that: Cil- Cik 3. If aik > ail and- > w then there exists an optimal solution with Yil = 0. In this case, it aik - ail can be easily shown that the reduced cost of alternative k, for any value of the multiplier 8 ( < w), is always less than the reduced cost of alternative 1. Therefore alternative 1 is dominated by alternative k. We conclude from our brief discussion of the LSMCK problem that the VR version of the problem can be solved by any existing dual algorithm developed for the FR case, with the addition of two features, namely the second trivial solution and the third dominance criteria discussed earlier. As a result solution times for the VR problem are expected to be even smaller than those observed for the FR case. The derivation of good multipliers for the two-constraint problem by procedure SL may require iteratively solving a large number of single constraint problems. Despite the existence of fast algorithms for such problems, it may be computationally tedious to solve the successive LP's to optimality, without taking advantage of previous solutions. Usually, the optimal solution to one surrogate problem remains optimal for a range of multiplier values, which can be determined by sensitivity analysis. - 12

Sensitivity analysis: We consider a two-dimensional multiple choice knapsack problem and its linear surrogate relaxation LSP9 for some non-negative multiplier g: Min CY + w(g) v (LSPg) s.t. a(g) Y < r(g) + v Y e'P,v>0 where w(g) = Min (W1, W2/ 1), a(L) = L1 + g L2, and r(hR) = R1 + L R2, and the set IP' is the same as set T except that the 0-1 constraints become 0<Yikl, k=1,..,Ki; i=1,..,S. The optimal solution (Y*,v*) to the one-dimensional continuous knapsack problem LSPg can take one of two forms: 1. the solution results in positive overtime. The solution is integer and can be represented by the set (k(i), i=1,..S ) where k(i) = argmin (Cik + w(j) aik(Lr), k=l,..,Ki }. The optimal dual multiplier is then equal to w(p). 2. the solution has no overtime. Then, all sets, except at most one, have an integer solution, i.e., there exists k(i) E (1,..,Ki) for which Yik(i) =1 and Yik=O otherwise. Let i* be the fractional set, and let k'(=k(i*)) and k" be the indices corresponding to the fractional variables in the set i*, i.e, Yi*k" = a(Rl) and Yi*k' = 1 - a(R). Let 86() be the optimal dual multiplier corresponding to this solution. Note that k(i) = argmin (Cik + 86() aik(L) I and that I aik(i)(L) + ai*k'(r) < r(L) < I aik(i)(r) + ai*k"(L). ixi* iwi* We introduce the following notation: Abik = bik - bik(i) Acik = Cik(i) - Cik abik = Abik / Acik Ab = bi*k" - bi*k' - 13

Ac = Ci*k' - Ci*k" and ab = Ab/Ac where C is the cost matrix and b is the workload matrix L1, L2 or a(!i)=L1i+uL2, p>0. Next we show how sensitivity analysis is conducted for the case where: (a) W1 < W2/4, and (b) constraint (2) is violated by the solution to LSP4, i.e., L2 Y > R2. By Lemma 1, our assumption in (a) implies that the cost of a unit overtime for the single constraint problem is equal to W1, the unit overtime cost of the first period. Lemma 4, in conjunction with our assumption in (b) implies that the optimal surrogate multiplier p* is greater than pi. We seek to obtain an improved lower bound on p*, starting with the solution to LSP4. We distinguish two cases: Case 1: Solution has a positive overtime, v* > 0. Observe that k(i) remains optimal for ji'=g+T if Acik < w Aaik(4+Tl). This is equivalent to 7 < lik k= 1,..,Ki,i= 1,..,S Acik- WlAaik(p) where Tlik = -W1 2ik if AL2ik<0 = +oo otherwise. If T = Min ( Tik, k=1,..,Ki,i=1,..,S) is positive, then a better surrogate bound is obtained for I'=lt+rl. The overtime increases by q(L2Y* - R2), and accordingly the cost increases by lWl(L2Y*-R2). Case 2: Solution has no overtime, v*=0. The current solution remains optimal for g'=.t+q if the solution Y for problem LSPu' is so that Yik(i) = 1 for ii*, and Yi*k' + Yi*k" = 1. However the fractional values are subject to change. S S Let A(i) = E aik(i)(g), and A2 = XL2ik(i) i=l i=1 The two conditions stated above are guaranteed to hold for a value of n = Min (7i 1,T2,f3 ), where r-A(QL) (i) Til = r-R ensures that A(li+1) < r(g+TI), i.e., the solution for the extreme case where Yi*k'=l (a(l+l) = 0) and Yi*k"=O is feasible, Ac - W1Aa(p.) (ii) -12 = WlAL2 ensures that the dual multiplier 6(+11) is less than w (=Wi) and therefore the solution has no overtime, and - 14

(iii) 13 = Min (lik, k=1,..,Ki;i=1,..,S), 3aik(i) - 3a(.) where Tik = 311L2- aa if (aL2ik- aL2) Acik < 0 = + 0 otherwise ensures that k(i) has the minimum reduced cost for p=C.++1, i.e., Acik < 6(L+T1) ( Aaik(pi)+ TrAL2ik). We can show that the only change in the solution is in the value of the fractional variables. The value of Yi*k" in the solution decreases by AL2 Aa = T [A2 - R2 + (R-A(i))Aa(-] and as a consequence, the cost increases by Aa AC. The same reasoning can be applied to derive the incremental values in the case where constraint (1) is violated and therefore A* < A, and in the case where 4 > W2/W1 and therefore w=W2/1. The detailed results for all possible cases are reported in appendix B. The sensitivity analysis is executed in linear time and does not require any pre-ordering of the sets. Alternative solutions can be computed at each breakpoint with no additional computation. Starting at some value At, it is possible to find p* by only conducting sensitivity analysis alone (as long as iT > 0). However, this may require a large number of iterations if the starting value of Ai is far from A* and the increments are relatively small. We suggest using sensitivity analysis to determine a good starting value of 4max and min, i.e., to determine a relatively tight interval to start the bisection search for 4*. Sensitivity analysis is also used to accelerate the procedure when the values of lmin and lmax are very close. All the concepts developed in this section are summarized in the following algorithm: Procedure SLS: (SL with sensitivity analysis) Step 0. Initialization of Lmin and Imax Same as step 0 of procedure SI. Replace SMCK by its continuous relaxation LSMCK If gmin=0 then conduct sensitivity analysis at 9=imin. Determine increment A1, and new solution at g+q. Let lmin=9+q. Go to step 1. Otherwise (if umax = +oo ) then conduct sensitivity analysis at 1=4max. Determine decrement i and new solution at jLmax=r-1. Let jimax=ji-n. Go to step 1. - 15

Step 1. Termination test If (Lmax - Lmin) < e, go to step 4. Otherwise, if ke < (gmax - Jmin) <K or i=0 then go to step 2. Otherwise go to step 3. Step 2: Bisection search - Update [Imin,4max] Let r = Lmin + (Jmax - min)/2 Same as Step 2 of SI. Replace SMCK by its linear relaxation LSMCK. Step 3. Sensitivity Analysis - Update [min,4max]If constraint (1) is violated by the current solution then conduct sensitivity analysis for Il=gmax. Determine decrement 1, and new solution at 1-qr. Let Imax=W-l. Go to step 1. Otherwise if constraint (2) is violated by current solution then conduct sensitivity analysis for ui=ILmin. Determine increment AT, and new solution at p+r. Let lmin=4+n. Go to step 1. Otherwise (if neither constraint is violated) then terminate. Note that if the incremental value determined by the sensitivity analysis is always positive then step 2, where we actually solve the LP, is visited at most log2(K/k) times. The values of K and k ( K > k > 1) as well as the value of e can be selected consistently with the application. As discussed S earlier, every step of procedure SLS can be executed in a linear time (O(XKi) ). i=l 32. Derivation of multipliers for the multiconstraint problem Define SP(h)~ as follows: Min CY + WV (SP(h)7y) s.t. yLY < yR +yV (M1) LhY < Rh + Vh (M2) Y esPV eR+ - 16

where constraint Ml is the single-constraint of the surrogate problem SPv for a set of multipliers y, and constraint M2 is the hth period constraint of the original problem P. SP(h)y is a two-constraint problem to which the analysis of section 3.1 can be applied. Consider the surrogate relaxation to SP(h)y where the multiplier of the first constraint is equal to 1 and the multiplier of the second constraint is equal to i. Lemma 4 states that if the solution to the surrogate problem violates the second constraint then a better surrogate bound can be obtained by increasing i. Therefore if the solution to SPv violates some constraint, h, of the multiconstraint problem P, then an ascent direction is identified for the surrogate dual. A better surrogate bound is obtained by increasing the hth component of y. Based on this result, we incorporate the two-constraint procedure SL in a heuristic to derive surrogate multipliers for the multiconstraint problem. The following procedure is similar to the one suggested by Gavish and Pirkul for the 0-1 multidimensional knapsack problem. Procedure ML: (multiple multipliers, linear knapsacks) Step 0. Determine the constraint that produces the highest objective value when all other constraints are ignored in problem P. Reindex this constraint as constraint 1. Step 1. Determine the constraint most violated by the solution of the single constraint problem (constraint 1). Reindex this constraint as constraint 2. Step 2. Apply procedure SL (or SLS) to the problem determined by constraints 1 and 2. If the bound obtained is not higher than the previous bound then terminate. Otherwise let the surrogate constraint obtained be constraint 1 and go to step 1. In order to implement procedure ML, we need to resolve some details. For example, it is not obvious how to define the appropriate overtime costs for the two-constraint problem from the multiconstraint problem. Also it is not clear what "maximum violation" means in the presence of available overtime. 1. Transforming SP(h~ into a standard two-constraint problem: An ambiguity exists due to the presence of Vh, the overtime in period h, in both constraints Ml and M2. It is not clear how to define the overtime costs corresponding to the first and second constraints in SP(h)y, or how to interpret the aggregate overtime in problem SP(h)y in terms of the overtime in periods 1,..,H. -17

Let us first consider the surrogate problem corresponding to SP(h)y for some multiplier A. This problem is actually SPy, where Yh=Yh+g and Yj=yj otherwise. It is easy to show that for the one-dimensional problem SPy', the overtime cost w is given by w =Wj* = Minl<j<H Wj/y'j. Moreover if v is the aggregate overtime solution in problem SPY, then in terms of the original overtime variables, we have Vj*=v/Yj* and Vj=O otherwise. In order to check the feasibility of the solution to SPy' in the two-constraint problem, SP(h)y, and as a result identify an improving direction, we need to define the overtime for constraints Ml and M2 in terms of the aggregate overtime v. Based on the results above, we have: V 1 = yj*Vj* = yj*/vy'j* for constraint M1 and V2 = Vh for constraint M2. The feasibility check consists of verifying that: (yL + lLh) Y < (yR +i Rh) + V1 for constraint M1 and LhR < Rh + V2 for constraint M2. Notice that unlike the standard two-constraint problem, both the first and second constraint may haYv positive overtime (if j*=h). For this reason, some of the results (related to overtime) in the sensitivity analysis presented in Appendix B need to be altered. These changes are implemented in our final code but are not explicitly described in this paper. 2. Determination of the most violated constraint: Since overtime is allowed and not bounded, feasibility is not an issue in problem P. The socalled constraint violation is defined in terms of overtime cost. Let Vh = Max (O,LhY-Rh) be the overtime in period h. Then the most violated constraint, h*, is defined as the constraint h, with the highest overtime cost resulting from the solution under consideration, i.e., h* = argmax (WhVh, h=1,..,H ). 3. Redundant computations in ML: The initialization step in SL need not be performed when SL is used in conjunction with procedure ML. At each iteration in ML, we solve the surrogate dual of SP(h)y, where y is the set of multipliers determined in the previous iteration. In SL, when we first let the multiplier corresponding to the first constraint be equal to zero, the resulting problem has already been solved in step 0 of ML, when all constraints are ignored except one. Then when we let the multiplier corresponding to the second constraint be equal to 0, the problem obtained is SPV, which has been solved in the previous iteration. - 18

At termination, the bound obtained by solving the successive two-constraint problems will be at best equal to the LP bound. A better bound is obtained by solving the surrogate dual problem as an integer problem. The dual multipliers determined by procedure ML are used to generate a surrogate constraint, and the single-constraint multiple choice problem obtained is then solved as a 0-1 problem. Computational experience shows that the unidirectional search procedure ML provides good multiplier values in a reasonable amount of time. The quality of the multipliers is tested both in terms of tightness of the bounds obtained and in terms of their ability to capture the aggregate level of resources. This last property can be judged by the quality of the heuristic solutions that make use of the surrogate multipliers to solve the multidimensional problem as a one-dimensional problem. 4. Heuristic Solutions A solution to the multidimensional problem can be obtained, with no additional computation, from the solution to the one-dimensional surrogate problem. If it is solved as a 0-1 problem then the solution obtained is integer and no rounding is needed. Feasibility is not an issue here, since overtime is allowed. However the actual overtime values for each period need to be computed in order to evaluate the actual cost of the solution. This solution will be referred to as the single integer knapsack heuristic (SIKH). It requires solving a 0-1 problem to optimality. Alternatively, the multipliers generated by procedure ML can be used in simpler heuristics to obtain approximate solutions to the 0-1 problem. Many of the successful algorithms developed for the 0-1 multidimensional knapsack problem are greedy heuristics that make use of "bang-for-buck" ratios. In such a heuristic the variables are sorted according to a measure of their relative value cj/tlj, where the penalty factor Lj is an indication of the aggregate consumption of the resources by alternative j. For the singleconstraint knapsack problem (Max CTX s.t. AX<b, xj E (0,1)) the ratios are simply defined as the ratios of the objective function coefficient to the resource constraint coefficient or cj/aj. Balas and Zemel [80] show that the solution obtained by packing the knapsack in decreasing order of the bang-for-buck ratio differed from the optimal solution by only a few variables. When several constraints are present, it is not quite clear how the above ratio can be generalized. Toyoda [75], Loulou and Michaelides [79] and Pirkul [87] suggest different penalty factors to define the "bang-for-buck" ratios. Pirkul defines the penalty factor as yL, where y is a set of multipliers obtained by solving the surrogate dual of the problem and L is the resource consumption matrix. We use a similar approach for our problem. - 19

The multipliers obtained by procedure ML are close to the dual multipliers of the linear relaxation of our original problem. The value (C+yL)ik is a good estimate of the reduced cost of variable Yik, which is an indication of the total cost of schedule i-k both in terms of the cost of the individual schedule and the consumption of the resources in period 1 through H. Note that the multipliers need to be scaled appropriately in order to be used for the computation of the reduced cost. Observe that if (y) is a set of optimal surrogate multipliers then so is (ay), where a>0. To avoid the problem of scaling the multipliers, we use the product Cik(yL)ik as a measure of the effectiveness of alternative k for supplier i. Since our problem is a minimization problem with knapsack constraints, we use a product rather than a ratio The lower is this "cost", the higher is the chance that the corresponding alternative will be in the optimal solution. We suggest the following procedure: Procedure GH: (greedy heuristic) Step 0. Determine a set of surrogate multipliers using algorithm ML. y0h < — h h=1,..,H. H Step 1. Compute C~ik = Cik ( y0h Likh) k=l,..,Ki; i=1,..,S. h=l Let k(i) = argmint C0ik, k=l,..,Ki 1. Break ties by choosing the index with lowest aggregate consumption. This also corresponds to the index with the highest individual cost. S LetTh = Lik(i)h; i=l If Th >Rhthen yh < —wh, otherwise ylh < — Y0h for h=1,..,H. If y1 y then go to step 2, otherwise go to step 3. H Step 2. Compute Clik = Cik ( ylh Likh ), k=l,..,Ki; i=1,..,S. h=1 Let k(i) = argmin ( Clik, k=l,..,Ki ). Break ties by choosing the index with minimum C ik. Go to step 3. -20

Step 3. Let Yik(i) = 1, i=1,..,S and Yik = 0, otherwise. Stop. Note that in step 2, we consider readjusting the multiplier values for the periods with positive overtime. The dual multiplier is then known to be exactly equal to the overtime cost in the corresponding periods. S All the steps in procedure GH can be executed in O(XKi) time, and it is therefore linear in the i=l number of variables. Both GH and SIKH are executed after procedure ML terminates and a set of near-optimal multipliers is determined. We suggest a third heuristic procedure which is executed in parallel with procedure ML. Each time a continuous single-knapsack problem is solved in step 2 of procedure ML, we use its fractional solution to construct a 0-1 solution to the original problem. Let Y be the set of current multipliers, and let b be the matrix of current surrogate coefficients (b=yA). Let Y* be the solution to the current surrogate problem. By the results in section 3, we know that there are at most two fractional values and they belong to the same multiple-choice set. Let m be the index of this set (if such a set does not exist then the solution is integer and no rounding is needed) and and let Y and Ymj be the two fractional values (we assume bmj < bm). Procedure MLKH (short for multiple linear knapsacks heuristic) uses this information to generate a set of 01 solutions and chooses the least cost one. Procedure MLKH: Step 0. Let y be the set of surrogate multipliers at step 2 of procedure ML. Let b be the corresponding matrix of surrogate coefficients and let Y* be the optimal solution to the current (continuous) surrogate problem. Let m, j'and j" be the indices defined above. Step 1. Generation of an initial 0-1 solution: For all k such that bmjy < bmk < bmjy, construct the schedule Y(k) as follows: Let Yij(k) = Y* for iwm, j=l,..,Ki Ymj(k) = 0 for jwk, and Ymk(k) = 1. -21

Find k* = k such that the total cost of schedule Y(k) is minimum. Let Y=Y(k*). Step 2. Reduction of overtime: Find the period h* with the maximum overtime cost if schedule Y is implemented, (i.e., h* = argmax( WhMax ( LhY'-Rh,O), h=1,..,H ). ) Find the supplier i*, with the largest workload in the period h* if Y is implemented, ( i.e., i* = argmax( Max(Lijh*, j=l,..,Ki ), i=1,..,S ). For all the alternatives in the multiple choice set corresponding to i*, construct the schedule Y(k)as follows: Let Yij(k) = Yij for im, j=l,..,Ki, Yi*j(k) = 0 for jzk, and Yi*k(k) = 1. Find k* such that Y(k) is the least cost schedule. Let T = Y(k*). Go to step 3. Step 3. If the cost of schedule Y' is lower than that of the incumbent solution then update the incumbent to be Y". Terminate. Remark: The incumbent solution is initialized at the trivial solution consisting of choosing the least cost alternative (based on the individual costs) in each multiple choice set. This solution is referred to as the ARGMIN solution. Conceptually, MLKH is an enumeration procedure. An alternative is a priori selected for each multiple choice set, except in one "critical set" for which a set of alternatives is enumerated. In step 1 the critical set is defined as the unique set with fractional variables in the solution to the surrogate problem. We limit our search to those alternatives with an aggregate load between the aggregate loads of the fractional variables. The solution to the 0-1 version of the surrogate problem usually has this property. The alternative selected then has a lower cost than the lowest load alternative (among the fractional variables) and a smaller load than the lowest cost alternative. The solution generated in step 1 is further improved by the overtime reduction scheme in step 2. - 22 -

First, we identify a "critical period" and define the "critical set" as the one with the largest load in the critical period if the policy determined in step 1 is implemented. We consider all the possible alternatives corresponding to such set while assigning the solution found in step 1 to the remaining sets. We choose the least total cost schedule. The search for the critical period and the critical set consists of comparing a number of values at most equal to the total number of alternatives plus the number of periods in the planning horizon. The number of alternatives investigated in both step 1 and step 2 do not exceed the number of alternatives in the critical set. Therefore the additional amount of computation needed to generate the heuristic solution is linear in the problem size. Along with these heuristics that make use of the multipliers derived by procedure ML, we mention two simpler heuristics which do not require the explicit computation of surrogate multipliers. First, the ARGMIN heuristic introduced above and which does not take into account the overtime costs and secondly, the most violated constraint heuristic (MVH) which has the same features as MLKH with the distinction that it is only run once for a specific value of the surrogate multipliers. The surrogate coefficients are equal to the coefficients of the constraint with the highest overtime cost resulting from implementing the ARGMIN solution, i.e., the surrogate constraint is given by Lh*Y < Rh* + Vh*, where h*=argmax WhMax ( LhY-Rh,O), h=1,..,H ) and Y is the ARGMIN solution. This simple method for deriving surrogate coefficients has been used by Sinha and Zoltners for the fixed resource case. We will see in section 6 that the lower bound obtained by this surrogate relaxation, as well as the heuristic solution derived from it, are outperformed by our procedures. In addition to producing lower bounds and upper bounds (heuristic solutions) for the multidimensional problem, good surrogate multipliers can be used to reduce the size of the problem, as we explain in the next section. 5. Problem reduction Consider the Lagrangian relaxation of problem P: Min CY+WV+X[LY-R-V] (LRPx) s.t. Y eP,V eR+ where X is a set of Lagrangian multipliers. We assume that OXh<Wh, h=1,..,H. This relaxation has the integrality property, i.e., the best bound that can be obtained is equal to the bound from the LP relaxation. Furthermore the optimal Lagrange multipliers are equal to the LP dual -23

multipliers, for which the above assumption is known to hold for the optimal solution. Under this condition the overtime variables can be set to 0 and LRPX can be rewritten as: Min (C+XL)Y (-XR) s.t. Y eP The solution to LRPX is trivial and given by: Yik(i)=l for k(i) = k I (C+XL)ik = Min 1<j<Ki (C+)L)ij Yik = 0 otherwise i=1,..,S. Now, assume Yik=l for some k=1,..,Ki and i=l,..,S. Then z(LRP) I Yik=l) = z(LRP)) + (c+XL)ik - (c+XL)ik(i) which by duality theory is a lower bound on any solution to the original problem which has Yik=l Now let Zheur be the objective value of a heuristic solution to problem P. If z(LRPX I Yik=l) > Zheur then a fortiori z(P I Yik=l) > Zheur in which case we conclude that there exists an optimal solution to P with Yik=O. Alternative k can therefore be disregarded from the multiple choice set i. For large problems with thousands of variables, the quality of the lower bound provided by the solution to the 0-1 single-constraint knapsack problem corresponding to the surrogate multipliers computed in procedure ML may be offset by the considerable amount of time needed to solve the knapsack problem to optimality. The quality of the solution provided by procedure MLKH can also be affected by the existence of thousands of alternatives. We suggest reducing the problem to a more reasonable size before solving it. Procedure LML is specially designed for large size problems: Procedure LML: (modified procedure ML for Large problems) Step L Obtain a set of good surrogate multipliers by procedure ML. Compute the corresponding surrogate bound (by the solving the corresponding single-constraint LP). Step 2. Use procedure MLKH to derive a heuristic solution using the surrogate multipliers determined in step 1. Step 3. Reduce the problem size using the surrogate multipliers determined in step 1 and the upper bound determined by the heuristic solution of step 2. - 24 -

Step 4. Solve the reduced single-constraint 0-1 problem, where the single constraint is determined by the surrogate multipliers of step 1. Compute the improved lower bound and the new heuristic solution as in SIKH. Terminate. 6. Computational experience In order to test the quality of the heuristics and the effectiveness of the surrogate lower bounding scheme, we run a series of computer experiments. All CPU times are given for a workstation with an 80386 processor running at 16 MHZ. The computer codes are written in Turbo Pascal version 5.0. All the procedures that have been developed throughout this paper can be applied to any multiconstraint multiple-choice problem provided all the constraints have non-negative coefficients and a penalty cost is defined for violating each constraint. It is clear from the terminology adopted so far that we are primarily interested in scheduling problems. We seek to coordinate the deliveries of multiple suppliers so as to minimize the total cost of the individual schedules and the labor cost induced by unloading the inbound freight at the docks. All the problems generated in our computational experiments have the structure of scheduling problems. For a given supplier, all the alternative schedules have the same total workload over the planning horizon, i.e., the same amount of material is shipped over the planning horizon. The schedules will differ by their individual costs and by the delivery pattern, i.e., the distribution of the workload over the planning horizon. The individual costs may vary because of the different level of lumpiness of the schedules. Some schedules will have the material grouped for shipments so as to benefit from economies of scale in the transportation cost. Other schedules will have just-in-time type schedules where the inventory costs are minimized. Next, we discuss how to generate the cost matrix and the workload matrix. Experimental set: The input data consists of: - the number of supplier (multiple choice sets): S, - the number of alternative schedules per supplier: K, - the number of periods in the planning horizon (number of side constraints): H, - the cost matrix: CSxK, - the workload matrix: ASxKxH, - the vector of regular time capacities at the unloading facility: RH, and - 25 -

- the overtime cost premium vector: WH. The costs of the individual schedules are generated from the uniform distribution U[50,150]. The workload matrix for a given supplier i, i=l,..,S, is obtained by the following scheme. First the total workload, Ti is generated from the uniform distribution U[10H,100H]., Then for each schedule j, j=1,..,K, we generate a vector of coefficients aijh, h=l,..,H, from U[1,50]. The workload of alternative j for supplier i in period h is given by ijh-. This ensures that the ratio of the aijh h maximum workload to the minimum workload for a given alternative is between one (balanced schedule) and fifty (lumpy schedule). The regular capacity for each period is computed as the average of the maximum and the minimum possible workload in that period. Finally the overtime cost is computed by first specifying the value of P, a measure of the importance of the overtime cost with regard to the total cost. It represents an estimate of the fraction of overtime cost in the total cost. Consider the ARGMIN solution. If this set of schedules results in no overtime, then it is optimal (in which case all the alternatives forming the ARGMIN schedule are deleted in order to avoid this trivial solution). Otherwise let V be the total overtime computed over all periods. A generic overtime cost, S W, is then given by the equality: W V = p(W V + XCik* ), where k* = argmin( Cik, k=l,..,K) for a i=l given set i, i=l,..,S. The unit overtime cost for each period is then given by U[0.5W,2W]. The results of our experiments are analyzed both in terms of quality of the solution and computation times. First, the heuristics are compared for various data sets. We analyze the effect of the problem size and the overtime cost on the relative performance of each heuristic. We also investigate the quality of the lower bound obtained by solving the surrogate problem induced by the set of multipliers determined by procedure ML. The gap between the lower bound and the upper bound provided by the best heuristic solution is reported as a measure of the effectiveness of the ML procedure. Comparison of the heuristics: Two types of heuristics were introduced in section 4 of this paper. The first group relies on the derivation of a set of multipliers by procedure ML and includes the following heuristics: - SIKH, which consists of solving the 0-1 single-constraint surrogate problem obtained at the termination of procedure ML, - 26 -

- GH, a greedy heuristic that uses the surrogate multipliers obtained by ML to rank the alternatives, and - MLKH, which is executed in parallel with procedure ML. It consists of deriving a 0-1 solution to the original problem from the LP solution to the surrogate problems generated throughout the execution of ML. We also suggested two simpler heuristics that can be run independently of procedure ML. Those are: - ARGMIN, the trivial solution which consists of choosing the minimum cost alternative in each set, and - MVH, which consists of solving a single-constraint relaxation of the problem where the single constraint is chosen to be the constraint with the highest penalty cost resulting from implementing the ARGMIN schedule. We conducted an extensive computational experiment consisting of 180 problems. Procedure MLKH gave the best solution in all but one problem where it was less than 1% from the best heuristic solution obtained. All the heuristics are tested and the relative deviation from the MLKH solution is reported. For each basic data set, ten problems are generated by varying the schedule costs, total workloads and degree of lumpiness. The average deviation is reported in each case. In the first experiment we study the effect of the problem size (number of alternatives, K, and number of multiple choice sets, S.) The overtime factor, P, is set to 0.5 and the number of side constraints is set to five. The results are shown in Table 6.1. Problem Size Heuristics I K ARGMIN MVH SIKH GH 5 10 28.4 11.5 0.8 13.9 20 56.3 15.9 1.6 9.3 30 30.9 13.0 1.9 11.7 40 39.2 16.7 2.6 13.1 10 25 31.3 11.9 3.2 8.4 o20 19.6 8.6 1.6 8.0 30 31.5 14.0 1.3 12.7 40 ________ 36.9 20.3 2.6 13.2 Table 6.1: Effect of the problem size on the relative performance of the heuristics (% deviation from the MLKH heuristic solution.) -27

The second experiment deals with the effect of the number of side constraints. The number of multiple choice sets and the number of alternatives are set respectively to 40 and 20. The overtime cost factor is set to 0.5. The results are reported in Table 6.2. I Heuristics I # of side constraints (H) ARGMIN MVH SIKH GH 3 48.6 14.0 1.4 18.7 4 24.7 12.0 2.2 10.4 5 23.1 9.7 0.5 10.3 6 29.5 17.7 3.4 9.3 8 28.9 15.9 1.5 12.2 10 26.5 16.8 1.0 11.2 I Table 6.2: Effect of the number of knapsack constraints on the relative performance of the heuristics (% deviation from the MLKH heuristic solution.) Finally the heuristics are compared for different values of the overtime cost. The problem size is fixed to 45 sets with 25 alternatives each and 5 side constraints. The results are summarized in Table 6.3. I Heuristics I Overtime cost factor (p) ARGMIN MVH SIKH GH 0.1 8.4 4.1 0.3 0.8 0.3 26.4 12.7 2.2 6.8 0.5 36.9 20.3 2.6 13.2 0.7 47.7 24.2 4.2 17.1 0.9 1 37.8 1 17.7 3.6 18.6 Table 6.3: Effect of the overtime cost on the relative performance of the heuristics (% deviation from the MLKH heuristic solution) The gap between MLKH and the remaining heuristics is a lower bound on the gap between the solution obtained by those heuristics and the optimal solution. It is clear that, except for SIKH that requires solving a 0-1 problem to optimality, all the other heuristics are in general far from optimality regardless of the problem structure. The poor quality of the trivial solution obtained by ARGMIN can be viewed as an indication of the level of difficulty of the problem. Obviously, when the overtime cost is negligible, the optimal solution is very close to the ARGMIN solution and the -28 -

problem can be considered trivial. Except for this case, the problem of finding a good heuristic solution is very difficult. Heuristics GH and MVH give comparable results with a small advantage for GH which is based on a more elaborate procedure to determine multipliers. Heuristic SIKH was the closest to MLKH but never did it generate a better solution. All the results reported above suggest that MLKH consistently outperform simpler heuristics. The problem size does not seem to affect the relative performance of the heuristics considerably. The gap between MLKH and the remaining heuristics appears to become larger for higher overtime costs, i.e., as the problem becomes harder. So far, we have demonstrated numerically the superiority of MLKH over the other heuristics. It remains to evaluate MLKH intrinsically in terms of the quality of its solution. We compare the value of the solution provided by MLKH to the value of the lower bound obtained by solving the 0-1 surrogate relaxation problem generated at the termination of ML. The lower bounding procedure ML, and the upper bounding procedure MLKH are closely related. The quality of the multipliers derived by ML depend on their ability to aggregate the multidimensional problem into a one-dimensional problem with a minimal loss of information concerning resource consumption. The more accurate is the one-dimensional representation, the better is the heuristic solutions generated by MLKH. The quality of both procedures is measured by the relative deviation of the heuristic solution value from the lower bound value. Note that we do not compare our heuristic solution to the optimal solution but rather to a lower bound because of the difficulty of solving large and dense 0-1 problems to optimality using existing commercial codes. The lower bound, however, is obtained by solving a single constraint 0-1 multiple choice problem for which we coded a specialized B&B procedure. Table 6.4 summarizes the results obtained for various data sets. Ten problems are generated in each case and the mean and standard deviation are reported. The results of Table 6.4 should be analyzed with caution. A major portion of the deviations may be due to the duality gap rather than to the gap between the heuristic solution and the optimal solution. The heuristic was found to be, on the average, less than 5 % from the lower bound which is an indication of its good performance. The low standard deviations suggest that the heuristic was consistent in its performance for each case analyzed. -29 -

SI K H P Average Gap Maximum Gap Gap Std. Dev. 25 110 5 0.5 3.4 7.3 1.9 201 3.7 7.9 2.2 30 3.9 7.61.9 _ _40 L... _ 4.2 10.0 2.3 10 25 5 0.5 4.2 7.0 1.1 20 1 3.8 6.3 1.1 30 3.8 6.8 1.7'40_ 1 [ j 3.1- 7.5 0.7 40 25 5 0.1 1.6 3.4 0.9 1 0.31 2.4 5.0 1.2 0.5 3.1 7.5 0.7 I0.71 3.9 10.0 2.3 I0.9j 4.8 9.2 2.7 40 20 1 3 0.5 0.5 1.0 0.2 4 1 1.8 3.3 0.8 51 3.0 5.0 1.1 6 4.4 7.3 2.2 8 4.7 6.9 1.7 o10 4.9 8.6 2.0 Table 6.4: Effect of the different factors on the percentage gap between the MLKH heuristic solution and the lower bound obtained by ML. The results of Table 6.4 should be analyzed with caution. A major portion of the deviations may be due to the duality gap rather than to the gap between the heuristic solution and the optimal solution. The heuristic was found to be, on the average, less than 5 % from the lower bound which is an indication of its good performance. The low standard deviations suggest that the heuristic was consistent in its performance for each case analyzed. The problem size has no apparent effect on the effectiveness of the heuristic. We would expect the heuristic to perform worse if the number of alternatives to choose from is higher, and the number of sets is smaller. The difference is not significant. The overtime cost and the number of side constraints seem to influence the performance of the heuristic. It is only natural that if the number of side constraints increases, then a good one-dimensional representation of the problem becomes harder to achieve. However, after the number of side constraints exceeds six, there is no significant change in the average deviations reported. The same applies to the effect of the 3 -30

factor. As p increases, the scheduling problem becomes much more difficult. The schedules need to fit together very well in order to avoid exceeding the regular capacity as much as possible. For both factors, we expect the duality gap to play a preponderant role in explaining the existing trends. The maximum deviation reported was 10 %. Among the 80 problems generated in the first experiment (variable problem size, P=0.5, H=5) three out of four have a deviation lower than 5 % and less than one tenth have a deviation higher than 7%. Even for the cases where apparently the heuristic did not appear to perform well (P=0.9, H=6,8 and 10) only five of the forty problems generated resulted in a deviation higher than 7%, and more than half of the problems were below the 5% mark. The good performance of both ML and MLKH is partially explained by the convergence behavior of the ML procedure. Figures 6.1 and 6.2 show the lower bound obtained by ML and the heuristic solution obtained by MLKH iteration by iteration for one specific problem. Notice that multiple solutions can be found at some iterations of ML, because at each iteration more than one surrogate problem may be solved and as a result several solutions may be generated by the MLKH procedure. 20000 MB Heuristic Solutions X X X B O 1 1 Surrogate Lower Bound. 10000 - ~ o' 0 0 0 5 10 15 Iterations Figure 6.1: Illustration of the convergence behavior of ML and the heuristic procedure MLKH -31

20000 19000' 18000.0 o 17000 o mw 16000- Lower Bound on the Optimal Value - 15000- ~, I., ~,. 0 2 4 6 8 10 12 14 16 Iterations Figure 6.2: Illustration of the convergence behavior of the heuristic procedure MLKH. Finally, we compare the lower bound obtained by ML to the one obtained by the "most violated constraint" (MVC) relaxation. Both lower bounds are obtained by solving a single-constraint surrogate relaxation of the problem. In MVC, the surrogate constraint is chosen to be the one corresponding to the period with the highest overtime cost resulting from the ARGMIN schedule. This relaxation is used by Sinha and Zoltners [79] for the fixed resource multiple choice multidimensional knapsack problem. The results confirm that simplistic approaches do not work well for our problem. Except for the case where the overtime cost is negligible, the MVC lower bound was found to be less than one third of the ML lower bound. This figure jumps to one fiftieth when the overtime cost is important (P=0.9). The average percentage gap between the two bounds is minimum in the case where P=0.1 when it is equal to 55%. Computation tractability: The search for a set of "near-optimal" multipliers is achieved by the iterative procedure ML in which another iterative procedure, SL (or SLS) is imbedded. At each iteration of SL, a continuous one-dimensional knapsack problem is solved. As mentioned in section 3, a linear time algorithm can be implemented to solve the single-constraint LP's. The total number of procedure ML iterations before termination and the number of LP's solved at each iteration determines the computation time required by procedure ML. If the total number of LP's solved is bounded by a -32

value which is known to be linear in the problem size then so is procedure ML. Unfortunately, it is difficult to derive a theoretical bound. However, the results of our tests suggest that the number of iterations of procedure ML before termination barely exceeds the number of multipliers, i.e., the number of knapsack constraints, H. Figure 6.3 shows a frequency graph of the number of iterations needed beyond the Hth iteration. The experiment consisted of 60 randomly generated problems. There is a set of ten problems for each value of H(=3,4,5,6,8 and 10.) 40 30 2010 0 0 1-3 4-7 8-14 Number of iterations above H Figure 6.3: Number of iterations required by procedure ML in 60 randomly generated problems (iterations above H, the number of multipliers) At each iteration of procedure ML, we address the problem of obtaining the optimal multipliers for a two-constraint problem. We explain in section 3 how this is achieved by the unidirectional search procedure SL. One of the multipliers is fixed to 1 and an e-interval containing the optimal value of the other multiplier is obtained by a bisection method. If the initial interval has a range A, then the algorithm would require O(log2(A/e) iterations before termination occurs. This value determines the number of LP's solved at each iteration of procedure ML. In our computation experiment, we let A be large enough to avoid eliminating the optimal solution. The value of e varies with the application. We terminate when the value of gmin and Umax are such that (JLmax-Lmin) < 10-3 1Lmax. With no prior knowledge of A*, and therefore no indication how big should A be, the number of iterations may be quite large. We fixed the value of A to 10000 and solved 130 problems corresponding to different problem sizes (S,K and H). The average number of iterations required by the SL procedure is reported in a frequency graph shown in Figure 6.4. -33

40 30 I l20 10 0 4-6 6-8 8-10 10-12 12-30 30-40 Number of LP's per Iteration Figure 6.4: Average number of LP's solved in one iteration of ML. (values for 130 randomly generated problems) The results did not suggest any dependency of the number of iterations in procedure SL on the problem size. The spread of values depicted in Figure 6.4 is indicative of the variances that are found within the set of problems of a given size. The total number of LP's solved remain of. manageable size, around one hundred in most cases. As a substitute for procedure SL, we suggested the procedure SLS based on the concept of sensitivity analysis. In SLS, the number of LP's solved explicitly is a controllable factor. Sensitivity analysis is used to initialize the search interval at some pred'etermined range (KE), and is also used to speed up the convergence to the optimal multiplier when the interval range is small (ke.) The sensitivity analysis consists of computing a set of potential increments to the multiplier value and choosing the minimum one. The number of these increments is proportional to the total number of alternatives. The number of LP's explicitly solved by a single-constraint LP procedure is at most equal to log2K/k, and therefore its value can be selected a priori. The choice of the values of K and k depends on the quality of the increments generated by the sensitivity analysis. Generally, the value of the increment, i.e., the range of multipliers for which the present solution is optimal, tends to be high when the multiplier value is set at its lower bound (zero) or at its upper bound (infinity). But it drastically declines as the search interval gets smaller. We need to choose the parameters K and k so that the time savings due to the reduction of the number of LP's to be solved is not offset by the number of times the increments are computed. Our computation experiment suggested that up to 20 % reduction can be achieved by appropriate use of sensitivity analysis. The derivation of good surrogate multipliers, and the solution to the successive LP's generated in procedure ML play a major role in finding a good solution to the original problem. Our heuristic procedure MLKH consists of "rounding" the fractional solution obtained each time a -34 -

surrogate problem is solved in ML. The additional computation effort needed by the rounding operation is reported in section 4 to be linear in the total number of alternatives and in the number of side constraints. The heuristic solution constitutes an upper bound on the optimal solution. A lower bound is obtained each time the set of multipliers is updated. Procedure ML terminates when there is no improvement in the lower bound. However a better lower bound is obtained by solving the surrogate problem as a 0-1 problem. We coded a specialized B&B procedure to solve the problem. The derivation of multipliers by procedure ML, the generation of heuristic solutions by MLKH and the computation of a tight lower bound by our specialized B&B procedure constitute the main features of a major algorithm that seeks to find good approximate solutions to the multidimensional problem while assessing the quality of such solution. The computation times reported in Table 6.7 correspond to the overall CPU times, all routines included. These CPU times are meant, above all, to give the reader an order of magnitude of the times needed to run the algorithm. Since our code is only experimental, these values can be considerably reduced, for example, by implementing a linear time algorithm to solve the LP's, which in our code is done in a polynomial time. The sorting operations, which consume 20 to 30% of the total computation time, can also be executed much faster than in our code. S K H j Average CPU time Standard deviation 25 10 5 0.5 20.5 10.0 20 21.6 7.2 30 51.7 24.1 I_40_1 1 1 69.4 40.8 10 25 15 10.5 22.0 12.1 20 I I 34.2 18.6 30 I I 1 42.5 19.2 40 I_ I I 1 63.7 41.9 40 20 3 0.5 34.4 5.3 4 29.3 12.6 5 I 54.0 31.7 6 53.2 25.7 8 56.1 11.4 10 72.6 15.2 Table 6.5: Average CPU times and standard deviations (in secs.) (10 problems generated for each set) for different data sets. -35 -

The average CPU times in Table 6.5 suggest that the problem size has little effect on the computation time. This is confirmed by the high variance of the computation times in each case. It is clear however that the solution times are very reasonable considering the degree of sophistication of our algorithm ( solution of dozens of LP's, execution of a B&B algorithm) and the quality of the solution obtained for this difficult problem. 7. Conclusion We addressed a multi-supplier scheduling problem, where we must choose among numerous alternative schedules for dozens of suppliers. We seek to coordinate the supplier deliveries over several days so as to smooth the workload at the receiving docks. A supplier delivers the same amount of material over a planning horizon regardless of the schedule assignment. However the alternative schedules differ in both the delivery pattern and the induced transportation and inventory costs. If the emphasis is on transportation cost, which usually exhibits economies of scale, then schedules with delivery peaks will be more economical; and if reducing inventory is the main focus then just-in-time deliveries may be more appropriate. The labor cost may also be an important factor in choosing the best schedule for each supplier while considering all the suppliers simultaneously. We assume a regular time capacity at the docks and incur an overtime premium for exceeding the standard capacity. The labor allocated to the docks may be set by longrange plans, or the model can be used to decide the work force level at the docks. The scheduling problem is modeled as a multidimensional multiple-choice knapsack problem in which the we allow the knapsacks to be enlarged at some cost. It is hard to solve the problem to optimality. We suggest several heuristic procedure and show that simplistic approaches provide poor solutions. We propose a heuristic which is based on the solution to the surrogate relaxation to the problem. The multidimensional problem is transformed to a onedimensional problem using surrogate multipliers. The multipliers are derived by an iterative procedure which requires solving dozens of one-dimensional continuous knapsacks. The solution to these LP's is appropriately rounded to provide a good solution to the original problem. Computational results show that the surrogate relaxation bound is very tight. The heuristic solution is in, general, less than 5% from the this bound. The suggested algorithm derives good surrogate multipliers that are used to generate both good heuristic solution and a tight lower bound. The total CPU time, i.e., including all these operations, suggest that the algorithm is computationaly tractable for reasonably large problems. If converted from a workstation with an -36

80386 processor to a mainframe computer, the computation times will range in the milliseconds for problems with 40 suppliers, 25 alternatives and a 7-day horizon. The lower and upper bounding procedures proposed in this paper can be used to develop efficient B&B methods for solving the problem to optimality. A good bounding scheme will be based on surrogate relaxation, as suggested here. The initial value of the multipliers at a given node may be set at the terminal values obtained at the predecessor node in the B&B tree, which will certainly speed up the convergence of procedure ML at each node. The branching scheme may also be based on the surrogate relaxation, which if solved as a LP will have at most two fractional values. Dichotomy rules of the type used for the one-dimensional multiple choice problem can be used for branching. When overtime is permitted, no feasibility issues are raised and the solutions obtained by our heuristic are good enough to disregard solving the problem optimally. However, if the resources are fixed (overtime cost equal to infinity) or if the amount of overtime permitted is restricted then our heuristic solution may be infeasible. However most of the work involving the derivation of the multipliers can be easily adapted to handle such cases. The multipliers obtained can still be used in different heuristic procedures that ensure feasibility or in a B&B scheme to solve the problem to optimality. In conclusion, we have developed an algorithm to solve a scheduling problem which can be applied to any multiple-choice problem with a few knapsack type side-constraints. We suggested an efficient procedure to derive good heuristic solutions and tight lower bounds to assess the quality of these solutions. We have focused in our experiments on delivery scheduling problems. However, our results also have application to other problems, such as multi-item production planning and capital budgeting. -37

BIBLIOGRAPHY Bean, J.C. (1987), "Multiple Choice Knapsack Functions," Technical Report 87-26, Industrial and Operations Engineering Department, The University of Michigan, Ann Arbor, Mi. Ben-Kheder, N. and Yano, CA. (1990),' A Sequential Approach to Solve a Large Procurement Scheduling Problem,' Technical Report 90-?, Industrial and Operations Engineering Department, The University of Michigan, Ann Arbor, Mi. Bitran, G.R.and Matsuo, H. (1986), "The Multi-Item Capacitated Lot-Size Problem: Error Bounds of Manne's Formulations," Management Science 32, pp. 350-358. Dudzinski, K. (1984), "A Dynamic Programming Approach for Solving the Multiple Choice Knapsack Problem," Bulletin of the Polish Academy of Science, Technical Science 32, pp. 325-332. ----------- and Walukiewicz, S. (1984), "A Fast Algorithm for the Linear Multiple Choice Knapsack Problem," Operations Research Letters 3, pp. 205-209. -----------—. —---—.. —--------- (1987), "Exact Methods for the Knapsack Problem and its Generalizations." European Journal of Operational Research 29, pp. 3-21. Dyer, M.E. (1984), "An 0(n) Algorithm for the Multiple Choice Knapsack Linear Program," Mathematical Programming 29, pp. 57-63. -------—, Kayal, N. and Walker, J. (1984), "A Branch-and-Bound Algorithm for Solving the Multiple Choice Knapsack Problem," Journal of Computational and Applied Mathematics 11, pp. 231-249. Dzielenski, B.P. and Gomory, R.E. (1963), "Optimal Programming of Lot-Sizes, Inventory and Labor Allocations," Management Science 11, pp. 874-890. Gavish, B., and Pirkul, H., "Efficient Algorithms for Solving Multiconstraint Zero-One Knapsack Problems to Optimality," Mathematical Programming 19, pp.255-278. Gilmore, P.C. and Gomory, R.E. (1966), "The Theory of Computation of Knapsack Functions," Operations Research 14, pp. 1045-1074. Glover, F. (1975), "Surrogate Constraint Duality in Mathematical Programming," Operations Research 23, pp. 434-451. Karwan, M.H. and Rardin, R.L. (1979), "Some Relationships between Lagrangian and Surrogate Duality in Integer Linear Programming," Mathematical Programming 17, pp. 320-334. ------------------------------- (1984), "Surrogate Dual Multiplier Search Procedures in Integer Programming," Operations Research 32, pp.52-69. Lasdon, L.S. and Terjung, R.C. (1971), "An efficient Algorithm for Multi-Item Scheduling," Operations Research 19, pp. 946-969. Loulou, R. and Michaelides, E. (1979), "New Greedy Like Heuristics for the Multidimensional 0-1 Knapsack Problem," Operations Research 27, pp. 1101-1114. Manne, A.S. (1958), "Programming of Economic Lot-Sizes," Management Science 4, pp. 115-135. -38

Nauss, R.M. (1979), "The 0-1 Knapsack Problem with Multiple Choice Constraints," European Journal of Operational Research 2, pp. 125-131. Narasimhan, S. and Pirkul, H. (1986), "Efficient Algorithms for the Multiconstraint General Knapsack Problem," IIE Transactions 1?, pp. 195-203. Pirkul, H. (1987), "A Heuristic Solution Procedure for the Multiconstraint Zero-One Knapsack Problem," Naval Research Logistics 34, pp. 161-172. Shih, W. (1979), "A Branch and Bound Method for the Multiconstraint Zero-One Knapsack Problem," Journal of the Operational Research Society 30, pp. 369-378. Sinha, P. and Zoltners, A.A. (1979), "The Multiple Choice Knapsack Problem", Operations Research 27, pp. 503-515. ---—.-. — ---—.-. — (1979), "A Multiple-Choice Integer Programming Algorithm," Unpublished Paper. Toyoda, Y. (1975), "A Simplified Algorithm for Obtaining Approximate Solutions to Zero-One Programming Problems," Management Science 21, pp. 1417-1427. Weingartner, H.M. and Ness, D. N. (1967), "Methods for the Solution to the Multidimensional 0/1 Knapsack Problem," Operations Research 15, pp. 83-103. Zemel, E. (1984) "An O(n) Algorithm for the Linear Multiple Choice Knapsack Problem and Related Problems," Information Processing Letters 18, pp. 132-138. -39 -

Appendix A Theorems and Proofs We consider the following two-dimensional knapsack problem: Min CY + W1 V1 + W2 V2 (P2) s.t. L1YSRI+V1 (1) L2YR2 + V2 (2) YelT V, V2>0 and its surrogate relaxation for a non-negative multiplier.: Min CY + W1 V1 + W2 V2 (SPA) s.t. (L1 + p L2)Y < (R1 + R2) + (V1 + V2) Y E T V1,V2>0 where v is the set defined by all 0-1 and multiple choice constraints in the decision vector Y. In the following we investigate some of the properties of the solution to SPp. Lemma 1: Let p < W2/W1. Then an optimal solution to SPp has V2=0. Similarly, if > W2/W1 then an optimal solution to SPg has V1=0. Proof: We prove the result for the case where p < W2/W1. The proof is similar for the case p > W2/W1. Let (Y,V1*,V2*) be an optimal solution to SPp and suppose that V2*>0. Let Vl=V1*+gV2*. Then (L1 + L2)Y* <(R1 + R2) + (V1* + V2*) < (R1 + LR2) + V1'. Therefore (Y*,Vl,0) is a feasible solution to SPA. Now since p. < W2/W1 and V*2 > 0, we have CY* + WJV1' = CY* + WlVl*+WiLV2* < CY* + W1 V1*+ W2 V2* which contradicts the optimality of (Y*,V1*,V2*), for V2* > 0. -40

In the following, for simplicity, we will assume that j~ < W2/W1. Similar results hold for the case x>W2/W1 (simply reindex the constraints). Based on this assumption and the results of Lemma 1, V2 is equal to zero and we write the solution to SPg as (Y,v), where v is equal to V1. Let (Y,v) be an optima l solution to SP. Then at most one constraint is violated by this solution. Proof: Let (Y,v) be an optimal solution to SPgL. Assume that both constraints of problem P2 are violated by this solution, i.e., L1 Y > R1 + v and L2 Y > R2. This implies that: (L1 + gL2) > (R1 + p R2) + v (since p >0) which contradicts the feasibility of (Y,v) in problem SPIl. mma: Let v) be an optima l solution to SP3 that does not satisfy constraint (1) of P2. Then p* < p., where g* denotes the optimal multiplier. Proof: Let (Y,v) be an optimal solution to SPg that does not satisfy the first constraint of problem P2, i.e., L1Y > R1. (L31) If p.=g*, i.e., z(SPp.) = Sup y>o SPy, then we are done. Otherwise, we show that if the value of A is increased by a positive increment A, then the surrogate bound decreases. As a consequence 4* must be smaller thanp. Since the first constraint is violated, we know by Lemma 2 that the second one is not, i.e., L2Y < R2 (L32) and since (Y,v) is feasible to SPg, we have: (L1+9L2) ~ (Rl+pR2) + v (L33) Now let p'=p+i, where I7>0. Then (L1 + L'L2)Y = (L1 + IL2)Y + TiL2 < (L1 + pL2)Y +1 R2 (by L32) < (R1 + p R2) + 11R2 + v (by L33) = (R1 + p' R2) + v We conclude that (Y,v) is also feasible to SPg'. Therefore the set of feasible solution to SPg is included in the set of feasible solutions to SPpL'. Hence z(SPgI') < z(SPp). Since p is not optimal then neither is p', p'>L. Lemma 4: Let (Y,v) be an optimal solution to SPp that does not satisfy constraint (2) of P2. Then a* > p. -41 -

Proof: Let (Y,v) be an optimal solution to SPA that does not satisfy the second constraint of problem P2, i.e., L2Y > R2. (L41) If g=r*, i.e., z(SPgL) = Sup o>o SPy, then we are done. Otherwise, we show that if the value of 4 is decreased by a positive increment AT, then the surrogate bound decreases. As a consequence A* must be higher than w. Since (Y,v) is feasible to SPL, we have: (L1+LL2) < (Rl+p.R2) + v (L42) Now let g'=g-Tj, where rT>0. Then (L1 +'L2)Y =(L1 + IL2)Y- TL2 S (L1 +!L2)Y - I R2 (by L41) < (R1 + g R2)- T1R2 + v (by L42) = (R1 + A' R2) + v We conclude that (Y,v) is also feasible to SPj.'. Therefore the set of feasible solution to SPg is included in the set of feasible solutions to SPg'. Hence z(SPg') < z(SP.). Since tL is not optimal then neither is |A', gL'< p. -42

Appendix B Sensitivity Analysis We consider a two-dimensional multiple choice knapsack problem and its linear surrogate relaxation LSPg for some non-negative multiplier l: Min CY + w(L) v (LSPL) s.t. a(p)Y < r(l) + v Y eP',v>0 where w(i) = Min (W1, W2/ ), a(L) = Ll + g L2, and r(L) = R1 + g R2, and the set V' is the same as set P except that the 0-1 constraints become 0<Yik<l, k=l,..,Ki; i=1,..,S. We adopt the same notation as in section 3.1. We let: Abik = bik - bik(i) Acik = Cik(i) - Cik abik = Abik / Acik Ab = bi*k" - bi*k' Ac = Ci*k' - Ci*k" and ab = Ab/Ac where C is the cost matrix and b is the workload matrix L1, L2 or a(g)=Ll+lIL2, _>0O. If the solution is fractional, then we let: i*: index of the fractional set. k',k": index of the two fractional variables in set i* ( chosen so that ai*k' < ai*k"), a: fraction of k" in the solution (Yi*k"= a and Yi*k'=l-a), and 8: optimal dual multiplier ( 0 < 8 < w). Let (Y,v) be the solution to LSPIL. There are four possible cases to be investigated: Case 1: A < W2/W1 and L2Y > R2, Case 2: p > W2/W1 and L2Y > R2 + v/l, Case 3: ~ > W2/W1 and L1Y > R1, and Case 4: W < W2/W1 and L1Y > R1 + v. -43

Note that the special case g=W2/W1, which is the only case where both V1 and V2 may be positive, can be handled by analysis similar to one of these cases once we determine which constraint of the original problem is violated (see section 3.1). When starting the bisection search for the optimal surrogate multiplier, the initial value of g is set to W2/W1. In this way we eliminate either interval [W2/W1,+oo), or (O,W2/W1] from further consideration. This also ensures that when starting the sensitivity analysis at a value corresponding to case 1, for example, the value of the increment is such that the updated multiplier will still be less than W2/W1. The computation of the increments in each one of these cases depends on whether or not the solution has overtime. B.I -Solution with overtime Suppose that, Y, the optimal solution to LSPg has overtime, i.e., v>O. The solution is then integer. Define k(i) so that Yik(i)=l, Yik(i)=O for kwk(i), i=1,..,S. We have: a(gl)Y > r(L), and (S1) Cik + w(L) aik() > Cik(i) + w(g)aik(i)(g) k=l,..,Ki; i=l,..,S. (S2) In order for Y to be optimal for a different problem LSPgI', both conditions Si and S2 need to hold for p'. Next, we discuss the implications for each case. Case 1: w(g)=W1 and L2Y > R2. We know that the optimal multiplier is greater than A. We derive a condition on the increment in so that Y is still optimal for g'=g+jn. Since L2Y > R2, a(g+Tn)Y = [a(R) + jL2]Y > r(p.) + 1?R2 = r(g+iq) and condition S1 is satisfied for any non-negative increment. For S2 to be satisfied, we need to have: Cik + Wl(aik(l) + TIL2ik) > Cik(i) + Wl(aik(i)(p) + lL2ik(i)) which implies: 1 Thik - WA Lik if AL2ik < 0 WiAL2ik = +00 otherwise, k=1,..,Ki and i=l,..,S. Note that the numerator is positive since condition S2 holds for -1=0, i.e., p.'=g. We choose 1q to be the smallest of all the increments. It is easy to see that: z(LSPp.') = z(LSPp.) + 1W1(L2Y - R2) since the only change in the solution is in the overtime value which increases by: [a(L+rl) - a()) ] - [r(Vp+i) - r(L)] = TI(L2Y - R2). -44

Case 2: w(pL)=W2/L and L2Y > R2 + v/i. We know that the optimal multiplier is greater than pg. We derive a condition on the increment s so that Y is still optimal for C'=g+TI. Since L2Y > R2+v/g > R2, we have a(l+n)Y = [a(z) + rL2]Y > r(r) + r1R2 = r(+'nl) and condition S1 is satisfied for any non-negative increment, 1l. For S2 to be satisfied, we need to have: W2(aik()i) + nL2ikii) W2(aik(i)(c) + L2ik(i)) Cik + L^2i Cik(i) + which implies: W2Aaik(~)- p~cik 1 < fik = 2Aik()- Aik if Acik -W2AL2ik > 0 Acik -W2bL2ik =+oo otherwise, k=1,..,Ki and i=1,..,S. Note that the numerator is positive since condition S2 holds for rl=O, i.e., g'=g. We choose 1 to be the smallest of all the increments. The only change in the solution is in the overtime value. As a consequence, W2 W2 z(LSPg') - z(LSPg) = —[a(gL+T) - r(t+i )] -— a(a ) - r(g)] W2 = W-2T[t(R1 - L1Y)] (> 0, since by Lemma 2, L1Y < Ri). It is easy to show that in the presence of positive overtime, if one constraint is violated, the other constraint holds as a strict inequality. Therefore, the change in the objective function is actually positive. Case: w(L)=W2/4 and L1Y > R1. We know that the optimal multiplier is smaller than pg. We derive a condition on the decrement T1 so that Y is still optimal for SL'=i-T1. Since L1Y > R1 and since the solution results in positive overtime, i.e., a(g)Y = r( i) + v > r( ), we have L2 < R2 + v/gL, and a(i-il)Y = (a(g) - 1L2)Y > r(gL) - ilR2 = r(4+rl). Therefore condition S1 is satisfied for any non-negative decrement, T1. For S2 to be satisfied, we need to have: W2(aik() - NL2ik) Cik(i) +W2(aik(i)() - TlL2ik(i)) which implies Cik + - 2 Cik(i) + L- - which implies: W2Aaik(IX)- 1 Acik 0ki 1 < Tik= W2AL2ik - Acik if W2AL2ik - Acik > 0 W2,L2ik-.Acik = +00oo otherwise, k=l,..,Ki and i=l,..,S. Note that the numerator is always positive since condition S2 holds for i1=0, i.e., g'=g1. We choose 71 to be the smallest of all the increments. The only change in the solution is in the overtime value. -45 -

As a consequence, W2 W2 z(LSPg') - z(LSPg) = -- [a(-r) - r(-r )] —- [a(g) - r())] W2 =( [(L1Y-RR)] (>0). Case 4: w(g)=W1 and L1Y > Rl+v. We know that the optimal multiplier is smaller than ~. We derive the condition on the decrement 71 so that Y is still optimal for I'=-TIq. Since L2Y < R2 and a(p) > r(i) then a(r-n)Y = [a(R) - rjL2]Y > r(g) - tlR2 = r(ig-r) and condition S1 is satisfied for any non-negative decrement, TI. For S2 to be satisfied, we need to have: Cik + Wl(aik(g) - TlL2ik) > Cik(i) + W1 (aik(i)(L) -TlL2ik(i)) which implies: WiAaik(l) - Acik I < Tlik = W1AL2ik f AL2ik > 0 W1AL2ik = +00 otherwise, k=l,..,Ki and i=1,..,S. Note that the numerator is positive since condition S2 holds for 7T=0, i.e., L'=g. We choose i1 to be the smallest of all the increments. It is easy to see that: z(LSP~') = z(LSPi) + rnW1(R2 - L2Y) since the only change in the solution is in the overtime value which increases by: [a(L+Til) - a(R) ] - ]r(+rT1) - r(L)] = Tj (R2 - L2Y). This value is positive since L1Y > R1 + v, where the overtime value, v, is equal to (Ll+gL2 )Y- (R1 + g.R2). B.2- Solution with no overtime Suppose that the optimal solution to LSPg, Y, has no overtime. Then, all sets, except at most one, have an integer solution, i.e., there exists k(i) E (1,..,Ki) for which Yik(i) =1 and Yik=O otherwise. Let i* be the fractional set, and let k'(=k(i*)) and k" be the indices corresponding to the fractional variables in the set i*, i.e., Yi*k" = a(x) and Yi*k' = 1 - a(g), r- Xaik(g) Yik - ai*k'(4) where a(l)- ai*k"(- ) - ai*k'). The optimal dual multiplier, 8(g), corresponding to ai*k"(9) - ai*k'(9) Ci*k" - Ci*k' this solution is equal to Ci*k" - Ci*k ai*k'(i) - ai*k"(tL) Now consider the problem: -46 -

MinCY+wv s.t. aY<r+v YeP, V > and its dual: S Min r - U)i i=l s.t. Vi - aik8 < Cik k=1,..,Ki; i=l,..,S. 08 w Assume that v is equal to zero in the optimal solution, Y. Let k(i) be such that: Yik(i) =1 and Yik=O otherwise, for i=1,..,S and iii*. Let Yi*k" = a, Yi*k' = 1- a and Yi*k=O otherwise. Then the optimality conditions can be stated as follows. 1. Primal feasibility First, we check that aY < r, i.e., e aik(i) + a ai*k" + (l-a) ai*k' < r. This condition holds as an i*i* r- Xaik(i) - ai*k' izi* equality for a = ai*k" - ai*k' We also check the non-negativity of the fractional variables Yi*k' and Yi*k", i.e., we need to have 0 < a < 1. As a consequence, we derive the following conditions: Xaik(i) + ai*k' r, and (S3) i*i* Xaik(i) + ai*k" > r (S4) i*i* (assuming ai*k" > ai*k'). 2. Dual feasibility The dual constraints state that: 8 w, and (S5) Cik(i) + Saik(i) < Cik + Saik for k=1,..,Ki; i=l,..,S. (S6) 3. Complementary Slackness We check that the dual objective value is equal to the primal objective value, i.e., XCik(i) + a Cik" + (1-a) Cik' = -r 8 + X(Cik(i)) + 8aik(i)) i i* i -47

Ci*k" - Ci*k' We can easily verify that this holds for the value of 65 *k - and the value of a specified ai*k' - ai*k above. Now consider a problem LSPj~,,u > 0. Its solution is completely determined by specifying the set [k(i), i=1,..,S), the index i*, the indices k' and k" and the values of a(R) and 86(). The objective of our analysis is to determine the value of the increment (or decrement) il, so that the solution of LSPr is still optimal for LSPg', ~'=g+ir (or g-r7). The values of a and S will, however, change from one problem to another. Next, we analyze the problem of determining T\ in each of the four cases cited earlier. First, we introduce some additional notations in order to simplify the analysis. We let: S A(Wl) = aik(i)(L), and i=l S A2 =L2ik(i). i= 1 Case 1: w(g) = W1 and L2Y > R2. We seek to find the highest increment, Aq, so that the optimal solution to LSPpi is optimal to LSPC', i'- +TI. First, we check that ai*k"(+rl) > ai*k'(4l+Tn), i.e., ai*k"(PL)+ iL2i*k" >ai*k'(r)+ rnL2i*k'. This is ensured by choosing: <lo0 = - AL) if AL2 < 0 = +oo otherwise. Next, we derive the bounds on 1 resulting from the primal feasibility conditions. Condition S3 states that A(i+7i) < r(+r7l), i.e., A() + r1 A2 < r(g) + r R2. This implies that T<il = -r() () ifA2 > R2 A2-R2 = +0 otherwise. Note that the numerator is non-negative since S3 holds for 1=0, i.e., when L'=t. Condition S4 states that A(g+q) + Aa(g+ln) > r(l+rl), i.e., A(gt) + Aa(gL) + 11 A2 + T1AL2 < r(L) + r1 R2. This implies that A(t) +Aa(~) - r(|i) 1~ 11' A(J.) +AaQ.) - r(ji') if A2 +AL2 < R2 R2 - A2- AL2 = +00 otherwise. -48

Since we assume in this case that L2Y > R2, i.e., A2 + ca(l) AL2 > R2, for T1l' to be finite, i.e., A2 + AL2 < R2, we need to have AL2 < 0. This implies that A2 > A2 + cxa()AL2 > R2. We can easily show that in this case tl1 < T11'. Next, we derive bounds on rl from the dual feasibility conditions. Ac Condition S5 states that 8(1L+1) ~ W1, i.e., a(-) + - L < W1. Since Aa(lg) + il AL2 > 0 (i.e., 1i > Aa(g) + Tj AL2 llo), the above condition implies that WlAa(a) - Ac 1<112 = - WAL2 if AL2<0 = +00 otherwise. Ac Note that when T12 and rlo are both finite, i.e., when AL2 < 0, then rl2 = rho + W < 1o. Condition S6 implies that Cik + 8(l+TI)aik(i)(u+T1) < Cik + 8(+rl1)aik(IL+n) for k=l,..,Ki, i=1,..,S. By adopting the notation introduced earlier, this condition can be written as: Ac Acik < 8(I+TI) Aaik(L+T1), i.e., Acik < Aa(+) +TI Aaik(l+1l). Since Aa(l) + TI AL2 > 0 ( T > o10), and since Acik and Ac are non-negative by definition, the condition above can be written as: Aa(Rl) + lT AL2 Aaik(1u) +TIAL2ik Aa c — Ac< ik, or more compactly as: Ac Acik aa(l) + lnaL2 < aaik(L) + n3aL2ik. As a consequence, we have: aaik(l) - aa(l~) T1 7lik= aL2 -Lk ifaL2 > aL2ik dL2- aL2ik = +0 otherwise Based on this analysis, we choose Ti = Min ( 11,1U2,13 ), where 113 = Min ( lik, kwk(i) for i#i* and kck',k" for i=i*). Next, we check that the objective value does indeed increase when the value of the multiplier increases. The only change in the solution is in the value of the fractional variables. The change in the cost is then equal to: z(LSP') - z(LSPI) = [ a(1') Ci*k" + (1-a(l')) Ci*k' ]- [ a(l) Ci*k" + (l-a(l)) Ci*k' ] = [ a(Z) -aO(')] [Ci*k' - Ci*k"] = [ a(z) -a(1')] Ac. Now by substituting for the value of a(1L') and rewriting it in terms of a(g), we can show that [ a(gL) - A2 + a(x~)AL2 - R2 a(1')] = A7a(~) + 1AL2, which is positive by our assumption that L2Y(=A2 + a((I)AL2) > R2 and the fact that the denominator is positive as noted above. -49 -

Case 2: w(t) = W2/L and L2Y > R2. We can perform the same same analysis as in the previous case. We obtain the same values for all the bounds, except for T12 which is obtained from the inequality: W2.Ac W2 8(A+Tq) <, ie., Aa( A < - which implies that A^ Aa(g) + lT AL2 -g W2Aa(r) - LiAc <11T2 = AcW2AL2-W2AL2 if - W > = +0o otherwise. Note that when 1o is finite, i.e., when AL2 < 0, then Ac - W2AL2 > 0 and TI2 < - A = Tlo. Case 3: w(jL) = W2/gu and L1Y > R1. We seek to find the largest increment, i, so that the optimal solution to LSPL is optimal to LSPP','=It -ri. By reasoning similar to the one developed for case 1, we derive the following results: o = A() if AL2 > AL2 = +oo otherwise. r(J) - A(g) 11 = R2( A(2 ifA2 < R2 = + otherwise. A() +Aa() - ) if A2 +AL2 >R2 T1 A2 + AL2- R2 A2 L2 = + otherwise. W2Aa(t) - rLAc 12 = W2AL2 - Ac if W2AL2 > Ac = +0 otherwise. aaik(L) - aa() i k= L2ik L2 faL2 <L2ik aL2ik - aL2 = +00 otherwise. We can show that, as in the previous cases, 1r2 <io and ill < I'f. We choose aq = Min ( 11,12,n3 ), where 13 = Min ({nik, kfk(i) for ixi*and k'k',k" for i=i*). We also check that the objective value increases when the value of the multiplier is decreased. The only change in the solution is in the value of the fractional variables. The change in the cost is then equal to: -50

R2 - A2 -a(~t)AL2 z(LSPg') - z(LSPIl) = [ a(L) -a(X')] Ac, which can be shown to be equal to Rl - TAL2 Ac, Aa(gt)-,qAL2 which is positive by our assumption that L2Y(=A2 + a(J)AL2) < R2. Case 4: w(~) = W1 and LlY > R1. WiAa(t) - Ac This is the same as case 3, except for the value of q2, which is equal to W- 2 if AL2 >0 and +oo otherwise. -51

UNIVERSITY OF MICHIGAN 3 9015 04732 7369