Network Optimization Lagrangian Relaxation 1

Lagrangian Relaxation I never missed the opportunity to remove obstacles in the way of unity. —Mohandas Gandhi On bounding in optimization In solving network flow problems, we not only solve the problem, but we provide a guarantee that we solved the problem. Guarantees are one of the major contributions of an optimization approach. But what can we do if a minimization problem is too hard to solve to optimality? Sometimes, the best we can do is to offer a lower bound on the best objective value. If the bound is close to the best solution found, it is almost as good as optimizing. 2 Overview Decomposition based approach. Start with x Easy constraints x Complicating Constraints. Put the complicating constraints into the objective. We will obtain a lower bound on the optimal solution for minimization problems. In many situations, this bound is close to the optimal solution value. 3 An Example: Constrained Shortest Paths Given: a network G = (N,A) cij cost for arc (i,j) tij traversal time for arc (i,j) Z* = Min s. t. ¦ ¦ ¦ xij c xij ( i , j )A ij j xij  ¦ j x ji t xij d T ( i , j ) A ij ­ 1 if i = s ° ® 1 if i = t ° 0 otherwise ¯ Complicating constraint 0 or 1 for all (i, j)  A 4 Example Find the shortest path from node 1 to node 6 with a transit time at most 10 2 (1,10) 1 (1,1) i 4 (2,3) (5,7) (10,3) j (1,7) (10,1) (1,2) (cij,tij) 6 (2,2) 3 (12,3) 5 5 Shortest Paths with Transit Time Restrictions ‹ ‹ Shortest path problems are easy. Shortest path problems with transit time restrictions are NP-hard. We say that constrained optimization problem Y is a relaxation of problem X if Y is obtained from X by eliminating one or more constraints. We will “relax” the complicating constraint, and then use a “heuristic” of penalizing too much transit time. We will then connect it to the theory of Lagrangian relaxations. 6 Shortest Paths with Transit Time Restrictions Step 1. (A relaxation approach). Solve the problem without the complicating constraint. If the solution satisfies the complicating constraint, then it is optimal for the original problem. ¦ ¦ xij c xij ( i , j ) A ij j xij  ¦ j x ji ­ 1 if i = s ° ® 1 if i = t ° 0 otherwise ¯ 0 or 1 for all ( i , j )  A 7 What is the shortest path from node 1 to node 6? 2 (1,10) 1 (1,1) 4 (2,3) (1,7) (10,1) (1,2) (5,7) (10,3) 6 (2,2) 3 (12,3) 5 8 The shortest path is 1-2-4-6 The transit time of 1-2-4-6 is 18. 2 (1,10) 1 (1,1) 4 (2,3) (1,7) (10,1) (1,2) (5,7) (10,3) (2,2) 3 (12,3) 5 6 To reduce the transit time of the shortest path, we put a penalty proportional to transit time. Suppose that we charge a toll of $1 per unit transit time. 9 What is the new shortest path from 1 to 6? 2 11 1 2 4 8 5 11 3 6 12 13 4 3 15 The modified cost of 1-2-5-6 is 20. The transit time is 15. The cost is 5. 1-2-5-6 is still not feasible. 5 We increase the toll to $2 10 What is the new shortest path from 1 to 6? The path 1-2-5-6 is still an optimal path. 2 21 1 3 4 15 8 12 5 6 19 16 6 3 18 5 11 And there is an alternative shortest path. The modified costs of 1-2-5-6 is 35. 2 21 1 3 4 15 8 12 5 6 19 16 6 3 18 5 1-3-2-5-6 is also optimal And it is optimal for the original problem as well! The transit time of 1-3-2-5-6 is 10. The cost is 15. 12 A parametric analysis Toll Weighted Sum Cost Transit Time Weighted Sum - 10 * Toll 0 3 3 18 3 1 20 5 15 10 2 35 5 15 15 3 45 15 10 15 4 55 15 10 15 5 64 24 8 14 6 72 24 8 12 7 80 24 8 10 8 88 24 8 8 9 96 24 8 6 10 104 24 8 4 13 Weighted Sum 120 100 80 60 40 20 0 0 2 4 6 Toll 8 10 Parametric analysis of Tolls 30 25 Cost 20 Transit Time 15 10 Weighted Sum 10 * Toll 5 - 0 0 2 4 6 8 10 Toll 15 On Bounding We could charge any non-negative toll on P transit times. For a path P, let cP = ¦(i,j)P cij tP = ¦(i,j)P tij For fixed P and P, let cP(P) = ¦(i,j)P [cij + P tij] Bounding Principle. Suppose that P t 0 and that P is the minimum cost path with respect to modified costs cP(P). Then cP(P) - P T is a lower bound on the length of the constrained shortest path. 16 Towards the Lagrangian Relaxation z* = min s.t. ¦ ¦ ¦ xij c xij ( i , j ) A ij j xij  ¦ j x ji t xij d T ­ 1 if i = s ° ® 1 if i = t ° 0 otherwise ¯ ( i , j ) A ij 0 or 1 for all (i, j)  A For each P t 0, replace the objective by: z(P) = min ¦ ¦ c xij  P ( ¦ ( i , j )A t ij xij  T ) ( i , j )A ij ( i , j ) A (cij  P t ij ) xij  PT Then z(P) ” z* for P t 0 because ¦ t xij d T ( i , j ) A ij 17 The Lagrangian Relaxation L(P) = min s.t. ¦ ¦ xij ( i , j ) A j (cij  P t ij ) xij  PT xij  ¦ j x ji ­ 1 if i = s ° ® 1 if i = t ° 0 otherwise ¯ 0 or 1 for all ( i , j )  A The Lagrangian relaxation was obtained by penalizing the constraint and then eliminating (relaxing) the constraint. Theorem. L(P) ” z(P) ” z* 18 Application to constrained shortest path ¦ L(P) = min ( i , j ) A (cij  P t ij ) xij  PT Let c(P) be the cost of path P P Let c ( P ) be the modified cost of path P Corollary. Suppose P* is a shortest path for the problem with modified costs, and suppose P c ( P*) c( P*)  PT Then P* is optimal. Proof. c P ( P*)  PT L( P ) d z* d c( P *) c P ( P*)  PT . 19 The Lagrangian Relaxation Technique z* min cx s.t. Ax b x X P L( P ) min cx  P ( Ax  b ) P(P) s.t. x  X Lemma 16.1. For all vectors P, L(P) ” z*. 20 The Lagrangian Multiplier Problem (with equality constraints) L( P ) min cx  P ( Ax  b ) P(P) s.t. x  X Lemma 16.1. For all vectors P, L(P) ” z*. A bound for a minimization problem is better if it is higher. The problem of finding the best bound is called the Lagrangian multiplier problem. L* max( L( P ) : P  \ n ) Lemma 16.2. For all vectors P, L(P) ” L* ” z*. 21 The Optimality Test Property 16.3 (Optimality test). If L(P) = L* = z* = cx, then x is optimal for the original problem, and P is optimal for the Lagrangian multiplier problem. More typically, a Lagrangian bound is useful when it shows that a solution is close to being optimal. 22 Summary 1. Each solution value L(P) is a lower bound on the optimum objective value. 2. L* is the best (highest) lower bound. 3. If L(P) = cx, then L* = z* = cx. (This is not guaranteed to happen.) 4. L* (or some good lower bound) is useful in heuristics and in branch and bound. Sometimes it can be used to give a short proof of optimality. 23 Lagrangian Relaxation and Inequality Constraints z* = Min cx subject to Ax d b, (Pd) x  X. L(P) = Min cx + P(Ax - b) subject to Lemma. L(P) d (Pd(P)) x  X, z* for P t 0. The Lagrange Multiplier Problem: maximize (L(P) : P t 0). Suppose L* denotes the optimal objective value, and suppose x is feasible for Pd and P t 0. Then L(P) d L* d z* d cx. 24 Travelling Salesman Problem (TSP) INPUT: n cities, denoted as 1, . . . , n cij = travel distance from city i to city j OUTPUT: A minimum distance tour. 25 Representing the TSP problem A collection of arcs is a tour if There are two arcs incident to each node The red arcs (those not incident to node 1) form a spanning tree in G\1. 1 26 A Lagrangian Relaxation for the TSP Let A(j) be the arcs incident to node j. Let X denote all 1-trees, that is, there are two arcs incident to node 1, and deleting these arcs leaves a tree. z * = min ¦ ¦ e ce x e eA(j) xe 2 for each j 1 to n P x X L( P ) = min P c ¦ e e xe  2 n x X P where for e = (i,j), ce P(P) ce  P i  P j 27 More on the TSP This Lagrangian Relaxation was formulated by Held and Karp [1970 and 1971]. Seminal paper showing how useful Lagrangian Relaxation is in integer programming. The solution to the Lagrange Multiplier Problem gives an excellent solution, and it tends to be “close” to a tour. 28 An optimal spanning tree for the Lagrangian problem L(P*) for optimal P* usually has few leaf nodes. 1 Towards another Lagrangian Relaxation 1 S In a tour, the number of arcs with both endpoints in S is at most |S| - 1 for |S| < n 30 Another Lagrangian Relaxation for the TSP z * = min ¦cx ¦ x e e e eA(j) ¦ L( P ) = min eS 2 for each j e 1 to n xe d | S | 1 for each strict subset S of N P c ¦ e e xe  2 n ¦ ¦ eS e xe d | S | 1 for each strict subset S of N xe n P where for e = (i,j), ce ce  P i  P j A surprising fact: this relaxation gives exactly the same bound as the 1-tree relaxation for each P. 31 Generalized assignment problem See example 16.8 in, Ross, G.T., and R.M. Soland. A Branch and Bound Algorithm for the Generalized Assignment Problem, Mathematical Programming, 8, 1975, pp. 91103. 32 Facility Location Problem See example 16.9 in, Erlenkotter, D. A dual-based procedure for uncapacitated facility location. Operations Research 1978; 26(6): pp. 992-1009. 33 A pictorial representation 34 A possible solution 35 Class Exercise Formulate the facility location problem as an integer program. Assume that a customer can be served by more than one facility. Suggest a way that Lagrangian Relaxation can be used to help solve this problem. Let xij be the amount of demand of customer i served by facility j. Let yj be 1 if facility j is opened, and 0 otherwise. 36 The facility location model Minimize ¦¦ c ij iI jJ subject to ¦x ij xij  ¦ F j y j jJ 1 for all i  I d K j yj for all j  J jJ ¦d x i ij iI 0 d xij d 1 for all i  I and j  J yj for all j  J 0 or 1 37 Summary of the Lecture Lagrangian Relaxation z Illustration using constrained shortest path z Bounding principle z Lagrangian Relaxation in a more general form z The Lagrangian Multiplier Problem z Lagrangian Relaxation and inequality constraints z Very popular approach when relaxing some constraints makes the problem easy Applications z TSP z Generalized assignment z Facility Location 38 Next Lecture Review of Lagrangian Relaxation Lagrangian Relaxation for Linear Programs Solving the Lagrangian Multiplier Problem z Dantzig-Wolfe decomposition 39