A MULTIPLIER ADJUSTMENT METHOD FOR MULTIPLE SHORTEST PATH PROBLEMS WITH COUPLING CONSTRAINTS Nejat Karabakal and James C. Bean Department of Industrial & Operations Engineering The University of Michigan Ann Arbor, Michigan 48109-2117 Technical Report 95-11 June 1995

A Multiplier Adjustment Method for Multiple Shortest Path Problems with Coupling Constraints* Nejat Karabakal and James C. Bean Department of Industrial and Operations Engineering University of Michigan, Ann Arbor, Michigan 48109-2117 June 28, 1995 Abstract WVe describe a problem that requires joint determination of multiple shortest paths due to some shared resource constraints. A common procedure is to relax the resource constraints and solve the Lagrangian dual by a multiplier adjustment method (Mi AM). We describe a general MAM that unifies various features of similar methods for spor;-fic problems in the literature. The MAM always achieves monotonic ascent and, ifi some cases, steepest ascent with little extra computation. We discuss how to adopt the general MAM into various applications, including equipment replacement, production planning, and pavement maintenance. We use the generalized assignment problem to illustrate the steepest ascent feature of the MAM. *This research was supported in part by National Science Foundation grant DDM-9202849 to the University of Michigan. Previous version of this paper was presented at the 1994 ORSA/TIMS meeting in Detroit.

1 Introduction Many important decision problems, such as equipment replacement and production planning, can be formulated as acyclic shortest path problems that are efficiently solved by dynamic programming (DP). Difficulties arise, however, in implementing such solutions if there are limited resources to be shared by shortest path problems, such as budgets and storage space. For example, in fleet vehicle replacement, each individual vehicle replacement induces a shortest path. A capital expenditure budget links all individual problems [19]. The resource-constrained shortest path problem is an NP-hard combinatorial optimization problem [14]. A common way to handle resource constraints is to relax them using Lagrange multipliers and solve the Lagrangian dual problem [2, 14]. Although there is no guarantee to solve the original problem optimally, this approach is attractive for two reasons. First, shortest paths obtained by this approach are sometimes acceptable when slight resource violations are considered tolerable, for example, under soft capital rationing [17, 15]. Second, the Lagrangian dual problem provides a lower bound which can be used in implicit enumeration algorithms [1, 2, 7, 8, 12, 19]. In this paper, we describe a general multiplier adjustment method (MAM) for solving the Lagrangian dual. The MAM unifies various aspects of similar methods designed for the specific applications of the resource-constrained shortest path problem [8, 12, 13, 17, 19, 22], and applies the general structure to new specific problems. Since the most difficult part of a MIANI is usually the determination of a step size, for given a set of ascent directions, most existing methods select the first ascent direction that gives a nonzero step size. A novel feature of our method is its efficiency in calculating the step size along any given ascent direction. With this feature, selecting the steepest ascent direction is justified computationally in many applications that satisfy some mild network conditions. In the following sections, we first formulate the multiple acyclic shortest path problem 1

i = i source i=2 C: source j=2 j=3 T TI I Figure 1: Two shortest path problems with three common resources. with complicating resource constraints. We then present an algorithm for the MAM and establish its properties through a number of lemmas. Next, we discuss how to adopt the general MAM for various applications. We illustrate the steepest ascent property through the generalized assignment problem. Finally, we present the concluding remarks. 2 The Model Coinsider n77 shortest path problems that must be solved jointly due to n common resources. Let the i-th problem be defined over a directed, acyclic graph G, = (Ni, Ai), i = 1,...,m, as the problem of finding a shortest path between a source and sink node. Each Ni can be partitioned into n disjoint node sets such that Ni = U>i Nij, and all arcs emanating from:7 consume resource j. Essentially, each Gi is a DP network with resources corresponding to stages, and the set Nij corresponding to the states in stage j. Figure 1 illustrates a case where two shortest path problems must be solved jointly, each using three common resources. 2

Let c(i, k, ) = length of arc (k, ) E A2 a(i, k, ~) = resource j consumption of arc (k, ~) E Ai, k Nij (j implicit from k) b(j) = resource j availability/requirement 1 if arc (k, ~) C Ai is on the optimal path in Gi x(i, k,) = 0 otherwise We can formulate this problem as an integer program (IP) as follows. For the ease of exposition, add to each A; a dummy arc with zero length from the sink node to the source node. minimize subject to m i 1 c(k,k))x(, k ) i=l (kf,)EAiA Z x(i, k,) - E x(i, e,k) = 0 gENi gENi m _ _ < E E a(i,f )x(il,k,) i=1 (k,)EA, kx( N,, x(i, k, ) {0,1} Vi, ki i= 1,...,m I b(j) j = l,.., n (1) (2) (3) Network constraints (1) assure the conservation of unit flow for each i. Resource constraints (2) link the individual shortest path problems, rendering an NP-complete problem [14]. Let A C in be a vector of Lagrange multipliers for constraint set (2) with the following sign conventions. X > 0 unrestricted in sign < 0 resource constraint type 3

Dualizing all resource constraints yields the following relaxation. m n n L(A) =minimize E E cA (i k, k, ) x(i, k, f)-: b(j) I(j) i=1 j=l (k,e)EA j=l subject to (1) and (3), where cx(ik,), k, c(i, k, ~) + a(i, k, ~) A(j), k E N-j. Without resource constraints, individual shortest path problems can be solved efficiently by a DP recursion [6]. Let fA(i) be the length of the shortest path in Gi for a given A. Then m n L(A) = f>(i) - b(j)A(j) (4) i=l j=l For a given A, L(A) is a lower bound on the optimal value to the IP. The tightest bound is obtained by solving the Lagrangian dual problem. max L(() (5) A In the next section, we present a MAM for solving (5). 3 Multiplier Adjustment Method MAMs are heuristic algorithms for solving Lagrangian duals by exploiting the special structure of a particular problem. A MAM has the advantage of achieving monotonic bound improvement in most applications unlike the more common subgradient algorithms. However, a HAM does not guarantee bounds better than those obtained by subgradient algorithms. For details and successful application examples of the MAMs, see [5, 7, 8, 19, 22]. Although most MAMs use the violated constraints to select an ascent direction, they differ considerably in finding the step size along a chosen direction. Based on the total float concept borrowed from the critical path method, our MAM features an efficient procedure for determining exact step sizes. Under some conditions, we can guarantee steepest ascent. We discuss these issues in detail following the formal presentation of the MAM. We now present a generic framework for the MAM. 4

Step 1. Pick initial multipliers, A~. With cxo, solve m shortest path problems and obtain xAo. Set t *- 0. Step 2. If XAt satisfies (2), stop; otherwise select a violated constraint j' from constraint set (2). Step 3. Let LHS(j*) be the left hand side of constraint j*. Determine a step size, A > 0, as follows. (a) If the LHS(j')> b(j*) for "<" or "=" type constraints, increase At(j*) by A until one of the following arcs is deselected. {(k,) e Nj. I XAt(i,-k,) )=1}. (b) If the LHS(j')< b(j*) for "">" or "=" type constraints, decrease At(j*) by A until one of the following arcs is selected. {(k, e) E Nij I xAt(i k,) = o0}. If findIlng A > 0 is not possible, stop; otherwise, adjust multipliers At'(j*) + A if case (a) At+l' A. t+' j) A-) for ji. At(j) - A if case (b) \\ it I1 C\t+1. solve n77 shortest path problems to obtain xt+l. Set t t + 1, go to step 2. I'1lie most critical step of the MAM is the determination of the step size, A. We start wit i sOIle definitions. Definition 1 Givenl a Lagrangian solution xx, define I1(j) = Al.x(i, k.f) = 1, k E Nj, for some L}, and Io(j) = { I x(i, k, f) = 0, k Nj, for some e}. 5

C (i, k, f) source sink Figure 2: Determination of OA(i, k, f). Definition 2 (Slack of an arc) Given XA(i, k, e) = 0 in the current solution, define OA(i, ) as the minimum decrease in c (i, k, e) necessary to set xA(i, k, e) = 1. We refer to OA(i, k, e) as the slack of arc (k, e) in Gi. The value of OA(i, k, e) can be determined by a procedure similar to that of the critical path method for finding total floats in activity networks. This concept is related to sensitivity in dynamic programming as discussed in [20]. The idea is illustrated in Figure 2. Let L1 and L2 be the shortest path lengths from the source node to the tail of (k, e) and from the sink node to the head of arc (F, ~), respectively. The lengths L1 and L2 can be computed efficiently by forward and backward DP recursions [6]. The value of OA(i, k, e) is the difference between the length of a shortest path from source to sink constrained to include (k, e), f\(i. i., ~), and the length of the current shortest path, fA\(i). Lemma 1 Given x(i, k, f) = 0 in the current solution, OA(i, k,, ) = f(i, k, e) - fA(i) > O uwhere f,(ik,, C) = L1 + cA(i, k, e) + L2. Hence, we have Lemma 2 Consider a Lagrangian solution XA for a given A. If constraint j* is violated because consumption is less than what is required, i.e., LHS(j*)< b(j*), then the step size in 6

step 3 of the MAM can be computed min. (6) i A(j) a( i,, ( ) (6) (k,e)EAi,kENij* Proof: Consider x\(i,k,e) = 0, i E IJ(j*) and k E Nij*. Decrease cx(i,k,~) until another path in Gi that contains (k, ~) E A, emerges as an alternative to the current shortest path. Suppose this occurs at increment 6 > 0, which, in turn, must satisfy fx(i) = fx(i, k, ~) - 6 a(i, k, f). From Lemma 1, (6) follows. ~ Definition 3 Let fA(i I E) be the length of a shortest path in G, constrained to exclude arcs in set E E Ai. Lemma 3 Consider a Lagrangian solution XA for a given A. If constraint j* is violated because consumption exceeds what is available, i.e., LHS(j*)> b(j*), then the step size in step 3 of the MAM can be computed A = m in mA(i,k', ) fA(i I-{(k,)}EN,.) - fA(i) A2 min min I(k',g')E S. a(i, kc, C) -a (Z, V, f a(i, k', ') {(k,) l x(i,k,)=l} S = { (k',') | k' C N,.a, a(i, ', ') < a(i, k, )}. Proof: Consider xx(i, k, ) = 1, i C I(j*) and k C Nij.. Increase cx(i, k,) until another path in G2, not containing (k, A) C A&, emerges as an alternative to the current shortest path. Suppose this occurs at increment 6, which can be either zero or positive. Since the step 3 of the MIAM requires a positive step size, assume 6 > 0. There are two possibilities for the new path; it will either 1) pass through one of the nodes in Nij*, or 2) skip all the nodes in Nij*. 7

In the first case, say the new path includes arc (k', f') E Ni3. for which XA(i, k', C) = 0. Then, 6 must satisfy fA(i) + 6a(i, k, j) = fA (i, kI',') + 6a(i, k',c). From Lemma 1 OA(i, k', C ) = 6[a(i, k, ) - a(i, k', ')]. A sufficient condition for 6 > 0 is a(i, k', C') < a(i, k, f), that is, if the i-th problem is to use resource j*, it should consume less than what it is currently consuming. In the second case, similarly, 6 must satisfy fA(i) + 6 a(i, k, ~) fA(Z I {(k, )eN23*)k.EN The value of A(j*) is increased until either case occurs. * The MAM is a dual ascent procedure in that it monotonically increases the value of L(A). This property is established below. Lemma 4 (Monotonicity) Letj* be a violated resource constraint in iteration t. Adjusting A'(j*) by A > 0 yields L(At'1) > L(At). Proof: If the violation is because LHS(j*)> b(j*), increasing A(j*) at the end of iteration t increases both components of L(At) in (4). First component increases because each fAt(i), AE I:(j'), increases by A x a(i, k, L), where xAt(i, k, ) = 1, k E Ni-* The second component increases by A x b(j*). Hence, L(A'+') = L(At) + A a(i, k, 7)Xt(i,kj) - Ab(j) = L(At) + A[LHS(j*) - b(j*)]. Similarly, if the violation is because LHS(j')< b(j*), decreasing A(j*) at the end of iteration t decreases both components of L(At) in (4). Hence, L(A'1+) = L(At) - A ~ a(i, k, j) x\t(i, k, j) + Ab(j*) = L(At) - A[b(j*) - LHS(j*)]. iEA (it) 8

In either case, the Lagrangian function strictly improves. * In step 2 of the MAM, an ascent direction is chosen as a violated resource constraint. Let JA be the set of violated resource constraints for a given A. Two popular rules for selecting j* E JA are a) first ascent [8, 12, 13], which scans J\ in a predetermined order and selects j* as the first encountered, and b) steepest ascent, which scans J\ and selects ja as follows. Corollary 1 (Steepest ascent) Let A(j) be the step size as determined by either Lemma 2 or 3 for an ascent direction j E JA. The steepest ascent direction j* satisfies j- = argmax { A(j) x LHS(j)- b(j)l }. jeJx Proof: Follows from Lemma 4. Determining the steepest ascent direction requires the computation of both terms in (7) for all j E J\. The first term is obtained basically by a table search, but the second term calls for solving a shortest path problem with some nodes deleted. In problems where all arcs having tail nodes in set j have their head nodes in set j +1, the second term in (7) does not need to be computed, and hence, the steepest ascent improvement is possible with little extra computation. For example, shortest path formulations of certain knapsack problems have this structure. More discussion of this issue is given in Section 4.4. Implementation of this general approach requires structural information from the underlying problem. The next section gives examples of this approach applied to several such structures: equipment replacement with capital budgets [19, 17], multiple item capacitated lot sizing, pavement maintenance scheduling [18], and the generalized assignment problem. 9

4 Applications 4.1 Equipment Replacement with Capital Budgets Equipment replacement decisions typically involve a) which equipment to install, and b) how long to use it. The problem is to find a chain of serial replacements that minimizes the total discounted cost over n periods. Suppose there are m pieces of equipment with a limited capital budget encompassing all replacements in each period. If serial replacements are modeled by network constraints while periodic budgets are resources, our general resource constrained shortest path formulation directly applies to this problem as follows. For a single asset, consider a directed graph where nodes correspond to the beginning of time periods and arcs correspond to the replacement decisions. Associated with each arc are three parameters: equipment type (technology), discounted cost (arc length), and installation cost (resource usage) of the replacement. An arc from node k to e > k represents a particular technology to be acquired in period k and salvaged in period ~. Without resource constraints, a single equipment's replacement problem is solved by finding a shortest path from node 1 to node 7 + 1, as illustrated in Figure 3 for a three-period problem. Since time periods define states, we have Nj = {j} for all i,j. See [17] for implementation details and computational experiments with large replacement problems. To briefly summarize, problems with up to 500 pieces of equipment and 20 periods were solved in, on the average, 178 seconds on an IBM RS/6000 model 320 to within 0.5% of optimality with an average budget violation of under 1%. 4.2 Multiple Item Capacitated Lot Sizing Consider the problem of determining the quantity and timing of production for several products over a planning horizon so as to satisfy a known demand in each period and minimize 10

Figure 3: Shortest path representation of equipment replacement and lot sizing problems. the sum of the production and inventory costs without incurring backlogs. Production costs consist of a fixed (setup) and a variable cost component, whereas the inventory costs are proportional to the quantity and time carried. A production capacity is imposed in each Ieriod. See [21] for a review of this literature. If t he resource constraints (production capacity) are relaxed, each item's lot sizing problein (can l)e solved )by \Vagner-Whitin's shortest path algorithm [25]. The underlying network st irlct lte for this problem is identical to that of the equipment replacement problem in that t 1(e odles correspond to the beginning of time periods and arcs correspond to the lot sizing (lec(isiolls (see Figure 3). An arc (k, f) represents a decision to supply the demand require1merlits for p)eriod k, k + 1,..., C - 1 by production in period k. Two parameters are specified for ('d(li arc: cost of production and inventory holding (arc length) and resource usage of the Irodulllction. IIence, our general MANI can be directly applied. A major drawback with this approachl is that it restricts itself to schedules satisfying the Wagner-Whitin property, which stat es that the demand in a period is satisfied either entirely from production in the period 0o firoml 1roduction in a prior period. The optimal solution may not satisfy this property. 11

4.3 Pavement Maintenance Scheduling The problem of scheduling road pavement maintenance is of serious concern in practice because of the rate at which pavement deteriorates to unacceptable levels. The pavement condition can be improved by selecting a maintenance alternative ranging from simple routine maintenance such as pothole patching and chip sealing to major maintenance practices such as reconstruction and rehabilitation [3, 10, 24]. The selection of a maintenance alternative is not a straightforward task because of the differences in cost and effectiveness. The least expensive alternative may not be the best because it allows the pavement to deteriorate faster in subsequent periods. Hence, while the cost of a maintenance alternative depends mainly on the pavement's condition, the overall cost of maintaining a street pavement over time is a function of both timing and type of maintenance alternatives. The problem is further complicated by the periodic budget limitations. Most government agencies work to an annual budget process which imposes budgets on pavement maintenance programs. Consider a street segment with a current pavement condition. The decision maker may eitlher let it deteriorate further by applying only routine maintenance or choose to install one of the mIajor maintenance alternatives to improve the pavement condition. We as-ume that both deterioration and improvement rates are deterministic and known with cerL,<.ilty once the )pav\ement condition and the choice of maintenance alternative are specified. A street segment's problem has a network structure similar to the ones shown in Figure 1. Nodes correspond to pairs (time period, pavement condition) and arcs correspond to maintenance decisions. A maintenance decision consists of the type of maintenance alternative and its life. Associated with each arc are two parameters: length which is the discounted cost of the maintenance decision over its life, and resource usage which is the required investment. An arc from node (tl, c1) to (t2, c2) is selected only if its maintenance alternative is installed 12

in period t1 when the pavement condition is c1, leading to condition c2 in period t2 and performing only routine maintenance between tl and t2. A single segment's problem is solved by finding a shortest path from a node in the current period to a node in the horizon period. See [18] for details and computational experiments with large maintenance problems. To briefly summarize, problems with up to 200 street segments and 20 periods were solved in, on the average, 244 seconds on an IBM RS/6000 model 320 to within 0.1% of optimality with an average budget violation of under 0.1%. 4.4 Generalized Assignment Problem The generalized assignment problem (GAP) seeks to optimally assign n tasks to m agents such that each task is assigned to exactly one agent but each agent is constrained only by the amount of a resource. Let Vij be the cost of assigning task j to agent i, wij be the resource required by agent i to perform task j, and b be the resource available to agent i. Suppose a 0-1 variable, yj, is set to one if task j is assigned to agent i, zero otherwise. Then, an integer programming formulation for the GAP is: TmT n minimize E vij Yi j (8) i=1 j=l n subject to E wj yi < b i = 1,...,m (9) j=1 Eyi- i j=l,...,n ((10) i=1 yij E {0,1} all i,j. (11) GAP has many applications and many algorithms were developed for its solution, see [4] for a recent survey. A common solution technique has been branch-and-bound with lower bounds obtained by various relaxations. A popular MAM was developed by Fisher, Jaikumar. and Van Wassenhove [8] for the Lagrangian dual obtained by relaxing the multiplechoice constraints (10). Let A(j) be the multiplier associated with multiple-choice con 13

straint j. Then L(A) = min l,,,i,,,,,,,,,,,)_ >: x ( 12) L(A) = mi { Z ijy j | y satisfies (9) and (11) }- A(j). (12) y [ z 3 3 where j = j + A(j). Later, Guignard and Rosenwein [12, 13] suggested several enhancements over this MAM but the basic structure remained the same. We will refer to the enhanced algorithm as the traditional MAM in subsequent discussions. For a given A, Lagrangian solution x\ is obtained by solving m shortest path problems. This is possible because each capacity constraint in (9) has a knapsack structure which lends itself to a shortest path formulation. A knapsack problem is to select from various possible items that fit in a knapsack while minimizing a cost measure [23]. Suppressing the i-index in the variables for clarity, let vj and wj be the value and weight of item j, respectively. The knapsack can carry up to b units of weight. Set yj = 1 if item j is put in the knapsack, otherwise yj = O. Also let sj = 1 - y, with zero value and weight. Then we have n min E -v yj j=1 subject to n Ewyj y< b j=l yj +j = 1 j =,...,n yj, sj e {0,1} Vj Knapsack problems can be solved as shortest path problems [6, 19, 16]. Consider a directed graph in which nodes are ordered pairs [j, ], where j enumerates items and 13 enumerates the knapsack capacity (/ = O,..., b). Arcs represent variable selection decisions such that an arc selecting item j must be from node [j - 1, - wj] to node [j, /]. Arc lengths are assigned the objective values of corresponding variables. Add a dummy source node and, using dummy arcs, connect it to the tail nodes of the arcs for the first item. Similarly, add a 14

RHS 2 1 source 0 0 1 2 variable Figure 4: Shortest path representation of a 0-1 knapsack problem. dummy sink node and, using dummy arcs, connect it to the head nodes of the arcs for the last item, n. All dummy arcs have zero lengths. Then, the knapsack problem is solved by finding a shortest path from the source node to the sink node. To illustrate, suppose we have two items which are valued 4 and 5 units and weigh 1 and 2 units, respectively. The knapsack can carry 2 units of weight. A shortest path graph for this problem is shown in Figure 4. Note that the diagonal arcs correspond to selecting item j > 0 (hence setting yj = 1), whereas horizontal arcs correspond to not selecting item j > 0 (hence setting sj =1). The traditional MAM uses the following approach for solving (12). For xA, let pj = yij for all j and JA be the set of violated multiple choice constraints. For j E Jx, the method finds.i the least decrease (increase) in A(j) required for setting Y- = 1 (yij = 0) in an optiniumn knapsack solution of row i if pj = 0 (pj > 1). A candidate step size is given by either A(j) = min2i{j6j}, where the min2 operator selects the second smallest element of its set, as suggested in [8] or A(j) = min-{f6-} as suggested in [12, 13]. Both min and min2 15

operators are over alli, if pj = 0 {i | yj = 1}, if pj > 1 If A(j) > 0, it is accepted as the step size, A. Otherwise, another j C Jx is tried. If no strictly positive step size is found, the algorithm stops. Lemma 5 Let j be a violated multiple-choice constraint forx x. (a) When A(j) = min2f{ 6j}, adjusting A(j) by A(j) improves the lower bound by j, j, if p 0 (13) (pj - 2)A(j) + 6., if pj >1 (b) When A(j) = minj{3-j}, adjusting A(j) by A(j) improves the lower bound by A(j), if p =0 (14) (p3 - 1)A(j), if pj > 1 Proof: See [16] for a derivation of (13). The result (14) follows directly from Lemma 4. * Note that when min2 operator is used in determining the step size, the MAM is no longer monotonic ascent. The procedure suggested in [8, 12, 13] to determine 6&j quantities is as follows. Let - = Ej 'ijyij- Suppose we removed variable yij from knapsack i. We will call the remaining problem with (n - 1) variables a restricted knapsack. Let ZR(/) be the optimum objective value of the restricted knapsack when its right hand side capacity is /. Now, if pj = 0 and yj = 0, the least decrement in vij that would cause yij = 1 in an alternative optimum solution is given by optimum solution of knapsack i is given by j = Z (bi) - z. 16

Table 1: Summary table Traditional Karabakal-Bean Knapsack problems solved at initialization m 2m Knapsack problems solved in each iteration O(mn) O(m) Steepest ascent? No Yes This procedure implies that the number of shortest path problems solved to determine A range from i7n to m x n, hence it is 0(mn). The procedure implied by Corollary 2 below solves 2177 problems, hence it is O(m). Corollary 2 Suppose multiple-choice constraint j is violated. Define 0[i, (j - 1,/3), (j, 32)] (as Ilf slack of an arc from (j - 1, /i) to (j, 2), where 0 < /1, /2 < bg, in the directed graph of k naaps.ack i. Th en, min { [i (j- 13 - w ),(j, )] }, if pj = 0 i=uj,=..... 6 b't rmin {O[i(j-1,/3)(j,1)] ) if pj >,I=0_.....,l~)j/)}if p7 >1 Proof: Flollows from Lemma 3. * 1 li( ill)rovenment over the traditional method is due to the "slack of an arc" (Definition 2) \whichl;\aoi(ls all the restricted knapsack solutions. In addition, with Sij quantities readily availalble as a table, and the bound improvement results of Lemma 5, it is easy to select a dlirection/step length pair to guarantee a steepest ascent improvement of L(A). Table 1 shows i1 complarison of the complexity of the two methods. 17

5 Conclusions We describe an effective heuristic for solving multiple shortest path problems under coupling resource constraints. The heuristic is a MAM that solves a Lagrangian dual formulation. Starting with a solution obtained by relaxing the resource constraints, the MAM reduces the resource violations systematically until a feasible or acceptable solution is obtained. This MAM calculates the step size along a given ascent direction efficiently due to the "slack of an arc" concept. With this feature, developing the steepest ascent MAMs is computationally feasible in certain applications. Implementation of this procedure is discussed for equipment replacement with capital budgets, multi-item capacitated lot sizing, and pavement maintenance schedulinig. The steepest ascent feature is illustrated using the generalized assignment problem. References [1] Aneja, Y. P., V. Aggarwal, and P. K. Nair, "Shortest Chain Subject to Side Constraints," NAetworks. 13 (1983). 295-302. [2] Beasley. J. E. and N. Christofides, "An Algorithm for the Resource Constrained Shorl!est Path Problem." Networks, 19 (1989), 379-394. [3] Carnahan. J. V., "Analytical Framework for Optimizing Pavement Maintenance,"' Journal of Transportation Engineering, 114 (1988), 307-322. [4] Cattrysse, D. G. and L. N. Van Wassenhove, "A Survey of Algorithms for the Generalized Assignment Problem," European Journal of Operations Research, 60 (1992), 260-272. [5] Chan. T. J. and C. A. Yano C, "A Multiplier Adjustment Approach for the Set Partitioning Problem." Operations Research, 40 (1992), S40-S47. [6] Denardo, E. V., Dynamic Programming: Models and Applications, Prentice Hall Inc. (1982). 18

[7] Fisher, M. L., "The Lagrangian Relaxation Method for Solving Integer Programming Problems," Management Science, 27 (1981), 1-18. [8] Fisher, M. L., R. Jaikumar, and L. N. Van Wassenhove, "A Multiplier Adjustment Method for the Generalized Assignment Problem," Management Science, 32 (1986), 1095-1103. [9] Geoffrion, A. M., "Lagrangian Relaxation for Integer Programming," Mathematical Programming Study, 2, (1974) 82-114. [10] Golabi, K., R. B. Kulkarni, and G. B. Way, "A Statewide Pavement Management System," Interfaces, 12 (1982), 5-21. [11] Gopalan, R., R. Batta, and M. H. Karwan, "The Equity Constrained Shortest Path Problem," Computers and Operations Research, 17 (1990), 297-307. [12] Guignard, M. and M. B. Rosenwein, "An Improved Dual Based Algorithm for the Generalized Assignment Problem," Operations Research, 37 (1989), 658-663. [13] Guignard, M. and M. B. Rosenwein, "An Application-Oriented Guide for Designing Lagrangean Dual Ascent Algorithms," European Journal of Operations Research, 43 (1989), 197-205. [14] Handler, G. Y. and I. Zang, "A Dual Algorithm for the Constrained Shortest Path Problem," etwuorks, 10 (1980), 293-310. [15] Kaplan, S., "Solution of the Lorie-Savage and Similar Integer Programming Problems by the Generalized Lagrange Multiplier Method," Operations Research, 14 (1966), 1130-1136. [16] Karabakal, N., "A Survey of Multiplier Adjustment Methods for the Generalized Assignment Problem," Technical Report, Department of Industrial and Operations Engineering, The University of Michigan, Ann Arbor, 1995. 19

[17] Karabakal, N., J. C. Bean and J. R. Lohmann, "Solving Large Replacement Problems With Budget Constraints," Technical Report, Department of Industrial and Operations Engineering, The University of Michigan, Ann Arbor, 1993. [18] Karabakal, N., J. C. Bean and J. R. Lohmann, "Scheduling Pavement Maintenance with Deterministic Deterioration and Budget Constraints," Technical Report, Department of Industrial and Operations Engineering, The University of Michigan, Ann Arbor, 1994. [19] Karabakal, N., J. R. Lohmann, and J. C. Bean, "Parallel Replacement Under Capital Rationing Constraints," Management Science, 40 (1994), 305-319. [20] Lee, I.-S., "On Sensitivity Analysis for Shortest-Path Dynamic Programming Models," Working Paper, Graduate School of Management, University of California, Los Angeles, 1986. [21] Maes, J. and L. Van Wassenhove, "Multi-Item Single-Level Capacitated Dynamic Lot-Sizing Heuristics: A General Review," Journal of Operational Research Society, 39 (1988), 991-1104. [22] Neebe, A. W, "An Improved Multiplier Adjustment Procedure for the Segregated Storage Problem," Journal of Operational Research Society, 38 (1987), 815-825. [23] NMartello, S. and P. Toth, Knapsack Problems: Algorithms and Computer Implementations, John Wiley and Sons, 1990. [24] Ritchie. S., C. Yeh, J. Mahoney, and N. Jackson, "Surface Condition Expert System for Pavement Rehabilitation Planning," Journal of Transportation Engineering, 113 (1987), 155 -167. [25] Wagner, H. M. and T. Whitin, "Dynamic Version of the Economic Lot Sizing Model," Management Science, 5 (1958), 89-96. 20