Unit 3: Duality
Oct 1: Lecture 5
Contents:
- Derivation:
- Bounding approach
- Multipliers approach
- Duality Recipe
- Theory:
- Weak duality theorem
- Strong duality theorem
Resources:
- Slides: [PDF]
- LN pp 36-52: [PDF]
- Reading about duality derivation: [F sec 5.1-5.5]
- Reading about the bounding approach and multipliers: [MG sc 6.1-6.3]; [HL sc 6.1-6.4]
Oct 3: Lecture 6
Contents:
- Complementary slackness theorems (Slides from lec 5)
- Derivation:
- Lagrangian Relaxation approach
- Applications:
- Dual Simplex
Resources:
- Slides: [PDF]
- LN pp 52-56: [PDF]
- Reading about dual simplex: [F sec 5.6-5.8]; [Va sc 7.1]; [CL ch 2]