Linear Programming and Combinatorial Optimization

Jan - May 2022


Instructor :  B Srivathsan


Course Description

Linear Programming: Basic theory, Simplex algorithm, Duality

Combinatorial Optimization: Optimization problems modeled as integer linear programs, LP-approximations, Primal-dual methods

A polynomial-time algorithm for LPs: Ellipsoid method and its applications

Applications of LP: Zero-sum games

References

[1] Understanding and Using Linear Programming: Jiří Matoušek and Bernd Gärtner (Springer)

[2] Notes of Prof Sundar Vishwanathan (IIT Bombay) in this link

[3] Combinatorial Optimization: Algorithms and Complexity Papadimitriou and Steiglitz

Lecture Hours

Tuesday and Thursday: 9:10 AM to 10:25 AM via Zoom

Enrol in the Moodle page for the link to the lectures

Evaluation and exam schedule

Two quizzes (30%) + Mid-semester exam (30%) + End-semester exam (40%)

Quiz 1: February 15, 9:10 AM to 10:25 AM

Mid-sem: Week of March 14 - 18

Quiz 2: April 12, 9:10 AM to 10:25 AM

End-sem: Week of May 9 - 13

Problem Sets

Problem Sheet 1     Problem Sheet 2     Problem Sheet 3    Problem Sheet 4

Lectures

Lecture number Date Topic Additional reading
Linear Programming
1 25.01.2022 (Tue) Introduction to linear programs, examples, general form vs equational form Slides Video Chapters 1 and 2 of [1]
2 27.01.2022 (Thu) Basic feasible solutions, an informal introduction and a formal definition Slides Video Chapter 4 of [1]
3 01.02.2022 (Tue) Basic feasible solutions; optimum occurs at a bfs when cost is bounded Slides Video Chapter 4 of [1]
4 03.02.2022 (Thu) Simplex method Slides Video Chapter 5 of [1]
5 08.02.2022 (Tue) Simplex method: degeneracy, finding an initial feasible basis, formalizing the notion of a tableau Slides Video Chapter 5 of [1]
6 10.02.2022 (Thu) Simplex method: proof of correctness (assuming termination) and a geometric interpretation Slides Video Chapter 5 of [1]
7 17.02.2022 (Thu) Simplex method: Bland's rule and proof of termination Slides Video Chapter 5 of [1]
8 24.02.2022 (Thu) Dual of an LP, weak duality theorem Slides Video Chapter 6.1, 6.2 of [1]
9 01.03.2022 (Tue) Strong duality: proof via simplex; Farkas' lemma statement and geometric interpretation Slides Video Chapter 6.3, 6.4 of [1]
10 03.03.2022 (Thu) Farkas' lemma variants; proof of duality using Farkas' lema Slides Video Chapter 6.4 of [1]
11 08.03.2022 (Tue) Proof of Farkas' lemma; Application of LP: Zero-sum games Slides Video Chapter 6.7 and 8.1 of [1]
12 10.03.2022 (Thu) Zero-sum games: maxmin equals minmax using strong duality (Pre-recorded) Slides Video Chapter 6.7 and 8.1 of [1]
Combinatorial Optimization
13 29.03.2022 (Tue) Integer Linear Programs, Discussion about complexity, Totally unimodular matrices Video Chapter 8.2 of [1]
14 01.04.2022 (Fri) König's theorem; Non-bipartite case: min vertex cover and max independent set Slides Video Chapter 8.2 and 3 of [1]
15 05.04.2022 (Tue) Complementary slackness; Introduction to primal-dual algorithms Video Lecture 15 from [2]
16 07.04.2022 (Thu) Primal-dual algorithm for shortest paths (Pre-recorded) Slides Video Lecture 22 of [2], Chapter 3.4 and 5.4 of [3]
17 12.04.2022 (Tue) Primal-dual algorithm for minimum spanning trees I (Pre-recorded) Slides Video Lecture 20, 21 of [2]
18 14.04.2022 (Thu) Primal-dual algorithm for minimum spanning trees II (Pre-recorded) Slides Video Lecture 20, 21 of [2]
19 18.04.2022 (Tue) Primal-dual algorithm for minimum vertex cover (Pre-recorded) Slides Video These notes
20 20.04.2022 (Thu) Matching polytope and Fractional matching polytope; M equals FM for bipartite graphs; Half-integrality of FM Video These notes
21 26.04.2022 (Thu) Half-integrality of FM; Adding odd-set constraints to get M = FM. Video These notes
22 05.05.2022 (Thu) Half-integrality of FM; Adding odd-set constraints to get M = FM (contd.) Video These notes