15.082 and 6.855J Lagrangian RelaxationI never missed the opportunity to remove obstacles in the way of unity.—Mohandas Gandhi2On bounding in optimizationIn 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.3OverviewDecomposition based approach.Start with Easy constraintsComplicating Constraints.Put the complicating constraints into the objective and delete them from the constraints.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.4An Example: Constrained Shortest PathsGiven: a network G = (N,A)cijcost for arc (i,j)tijtraversal time for arc (i,j)( , )ij iji j Acxz* = Mins. t. xijjxji1 if i = 1 1 if i = n 0 otherwisej0 or 1 for all ( , )ijx i j A( , )ij iji j At x TComplicating constraint5Example$1,10$1,1$1,7$2,3$10,3$12,3$2,2$1,2$10,1$5,7124536Find the shortest path from node 1 to node 6 with a transit time at most 10$cij, tiji j6Shortest 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.7Shortest Paths with Transit Time RestrictionsStep 1. (A Lagrangian relaxation approach). Penalize violation of the constraint in the objective function. xijjxji1 if i = s 1 if i = t 0 otherwisej0 or 1 for all ( , )ijx i j A( , )ij iji j At x TComplicating constraint cijxij(i, j) Atijxij(i, j) ATz(λ) = MinNote: z*(λ) ≤ z* ∀λ ≥ 08Shortest Paths with Transit Time RestrictionsStep 2. Delete the complicating constraint(s) from the problem. The resulting problem is called the Lagrangian relaxation. cijtijxij(i, j) AT xijjxji1 if i = 1 1 if i = n 0 otherwisej0 or 1 for all ( , )ijx i j A( , )ij iji j At x TComplicating constraintL(λ) = MinNote: L(λ) ≤ z(λ) ≤ z* ∀λ ≥ 09What is the effect of varying λ?Case 1: λ = 0 1124536251010111212P = 1-2-4-6 c(P) = 3 P = c(P) = t(P) = 18 t(P) = $1,10$1,1$1,7$2,3$10,3$12,3$2,2$1,2$10,1$5,7124536cij+ λ tijjiQuestion to classIf λ = 0, the min cost path is found.What happens to the (real) cost of the path as λ increases from 0?What path is determined as λ gets VERY large?What happens to the (real) transit time of the path as λ increases from 0? 10cij+ λ tijji11Let λ = 1Case 2: λ = 1 P = 1-2-5-6 c(P) = 5 P = c(P) = t(P) = 15 t(P) = 112851315431112124536$1,10$1,1$1,7$2,3$10,3$12,3$2,2$1,2$10,1$5,712453612Let λ = 2Case 3: λ = 2 P = 1-2-5-6 c(P) = 5 P = c(P) = t(P) = 15 t(P) = 2131581618651219124536$1,10$1,1$1,7$2,3$10,3$12,3$2,2$1,2$10,1$5,712453613And alternative shortest path when λ = 2 2131581618651219124536P = 1-3-2-5-6 c(P) = 15 t(P) = 10 $1,10$1,1$1,7$2,3$10,3$12,3$2,2$1,2$10,1$5,7124536P = c(P) = t(P) =14Let λ = 5Case 4: λ = 5 P = 1-3-2-4-5-6 c(P) = 24 P = c(P) = t(P) = 8 t(P) = 2131581618651219124536$1,10$1,1$1,7$2,3$10,3$12,3$2,2$1,2$10,1$5,712453615A parametric analysisTollmodified cost CostTransitTimeModified cost -10λ0 ≤ λ ≤ ⅔ 3 + 18λ 3 18 3 + 8λ⅔ ≤ λ ≤ 2 5 + 15λ 5 15 5 + 3λ2 ≤ λ ≤ 4.5 15 + 10λ 15 10 154.5 ≤ λ < ∞ 24 + 8λ 24 8 24 - 2λThe best value of λ is the one that maximizes the lower bound.A lower bound on z*0204060801001200 2 4 6 8 10modified cost05101520253035400 5 10modified costs - 10TCostsModified Cost – 10λTransit Timesλ λ17The Lagrangian Multiplier ProblemL* = max {L(λ) : λ ≥ 0}. Theorem. L( ) ≤ L* ≤ z*.L( ) = mins.t. xijjxji1 if i = 1 1 if i = n 0 otherwisej0 or 1 for all ( , )ijx i j A (cijtij)xijT(i, j) ALagrangian Multiplier Problem18Application to constrained shortest pathL( ) = min (cijtij)xijT(i, j) ALet c(P) be the cost of path P that satisfies the transit time constraint. Corollary. For all λ, L(λ) ≤ L* ≤ z* ≤ c(P).If L(λ’) = c(P), then L(λ’) = L* = z* = c(P). In this case, P is an optimal path and λ’ optimizes the Lagrangian Multiplier Problem.More on Lagrangian relaxationsGreat technique for obtaining bounds.Questions?1. How can one generalize the previous ideas?2. How good are the bounds? Are there any interesting connections between Lagrangian relaxation bounds and other bounds?3. What are some other interesting examples?19In 1784, there was a US state that was later merged into another state. Where was this state?The state was called Franklin. Four years later it was merged into Tennessee.In the US, it is called Spanish rice. What is it called in Spain? Spanish rice is unknown in Spain. It is called “rice” in Mexico.Why does Saudi Arabia import sand from other countries?Their desert sand is not suitable for construction.Mental Break20In Tokyo it is expensive to place classified ads in their newspaper. How much does a 3-line ad cost per day?More than $3,500.Where is the largest Gothic cathedral in the world?New York City. It is the Cathedral of Saint John the Divine.The Tyburn Convent is partially located in London’s smallest house. How wide is the house?Approximately 3.5 feet, or a little over 1 meter.Mental Break2122The Lagrangian Relaxation Technique (Case 1: equality constraints)P* min z cx Ax bxXs.t. L( ) min cx (Ax b)xXP(μ)s.t.Lemma 16.1. For all vectors μ, L(μ) ≤ z*.23The Lagrangian Multiplier Problem (obtaining better bounds)( ) min ( )L cx Ax bxXP(μ)s.t.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.* max( ( ): )nLLLemma 16.2. For all vectors μ, L(μ) ≤ L* ≤ z*.Corollary. If x is feasible for the original problem and if L(μ) = cx, then L(μ) = L* = z* = cx. In this case x is optimal for the original problem and
View Full Document