1 of 17

TNK104 Applied Optimization

Lecture 8

based on the slides provided by Nikolaos Pappas

Relaxation and Bounding, Part II

Tatiana Polishchuk,

Associate Professor,

Linköping University, KTS

https://www.itn.liu.se/~tatpo46/

​

2 of 17

Lagrangian Relaxation

2

TNK104 Applied Optimization I

3 of 17

3

TNK104 Applied Optimization I

Lagrangian Relaxation (cont’d)

​

​

4 of 17

Lagrangian Relaxation for Knapsack

4

TNK104 Applied Optimization I

5 of 17

Lagrangian Relaxation for Knapsack (cont’d)

5

TNK104 Applied Optimization I

Another example of 2D knapsack to consider (HW5!)

​

6 of 17

Lagrangian Dual

6

TNK104 Applied Optimization I

7 of 17

Lagrangian Dual (cont’d)

7

TNK104 Applied Optimization I

  • The Lagrangian dual (for minimization) is concave and piece-wise linear

​

L(λ)

One-dimensional case

  • The function is implicit
  • Not differentiable everywhere

λ

8 of 17

Solving the Lagrangian Dual

8

TNK104 Applied Optimization I

λ

​

​

  • Exploring the function structure: Collect and accumulate the line segments iteratively (finite convergence but computationally heavy)
  • Search by “jumping” from one point to another (subgradient optimization with asymptotic convergence)
  • Collect the segments, but keep only those (bundle) near the current point

L(λ)

9 of 17

Subgradient Optimization

9

TNK104 Applied Optimization I

10 of 17

Subgradient Optimization (cont’d)

10

TNK104 Applied Optimization I

11 of 17

Lagrangian Relaxation for Constrained Shortest Path

11

TNK104 Applied Optimization I

12 of 17

Lagrangian Relaxation for Constrained Shortest Path (cont’d)

12

TNK104 Applied Optimization I

For illustration, let’s enumerate all paths:

1-2-4-6

13 of 17

Lagrangian Relaxation for Constrained Shortest Path (cont’d)

13

TNK104 Applied Optimization I

Acknowledgement: Example and figure from Ahuja et al. Network Flows: Theory, Algorithms, and Applications, Prentice Hall, 1993.

¸

The Lagrangian dual function

L(λ)

for the path 1-2-4-6

f = 3 - 4 λ

to draw:

λ = 0 f = 3

λ = 1 f = 7

14 of 17

Sample Result of Subgradient Optimization

14

TNK104 Applied Optimization I

Iteration

  • The value is not monotonously improving
  • Larger instances require higher number of iterations

L(λ)

15 of 17

Uncapacitated Facility Location

15

TNK104 Applied Optimization I

16 of 17

Uncapacitated Facility Location (cont’d)

16

TNK104 Applied Optimization I

17 of 17

Self-Study Material

​

Read:

LP relaxation https://drive.google.com/file/d/1aRUOmOFvLBvpyn7-jQ3YkvTiyRQ3RApL/view?usp=sharing

Lagrangian Duality https://people.eecs.berkeley.edu/~elghaoui/Teaching/EE227A/lecture7.pdf

Lagrangian relaxation Chapters 16 and 17 in the book Network Flows

https://drive.google.com/file/d/1Lj4HlJ2se4d0zyz_K027J9roMKhmZSm1/view?usp=sharing

Lagrangian duality and TSP relaxation

https://drive.google.com/file/d/1Y0G3yn2PA4FHbZMWLSvOuYbdsi8ZlSB8/view?usp=sharing

Example 2d Knapsack (lagrangian relaxation)

​

Video lectures:

Lagrangian relaxation https://youtu.be/8rbuxKvm6Bg

​

Youtube videos:

​

Lagrangian relaxation https://youtu.be/hQ4UNu1P2kw

Duality weak and strong: review https://youtu.be/bPLNyYFLLT4

Lagrangian duality https://youtu.be/4OifjG2kIJQ

Matchings https://youtu.be/chdr2aj4FUc

Subgradient https://youtu.be/urbBxgc7_DE

​

​

​

​

​

​