Linear Programming and Combinatorial Optimization

Jan - May 2025


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

Previous version: 2022

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: 10:30 AM to 11:45 AM at LH802

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%)

Problem Sets

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

Lectures

Lecture number Date Topic Additional reading
Linear Programming
1 07.01.2025 (Tue) Introduction to linear programs, examples, general form vs equational form Slides Video Chapters 1 and 2 of [1]
2 09.01.2025 (Thu) Basic feasible solutions, an informal introduction and a formal definition Slides Video Chapter 4 of [1]
3 21.01.2025 (Tue) Basic feasible solutions; optimum occurs at a bfs when cost is bounded Slides Video Chapter 4 of [1]
4 23.01.2025 (Thu) Simplex method Slides Video Chapter 5 of [1]
5 30.01.2025 (Tue) Simplex method: degeneracy, finding an initial feasible basis, formalizing the notion of a tableau Slides Video Chapter 5 of [1]
6 04.02.2025 (Tue) Simplex method: Bland's rule and proof of termination Slides Video Chapter 5 of [1]
7 06.02.2025 (Thu) Simplex method: proof of correctness (assuming termination) and a geometric interpretation (pre-recorded) Slides Video Chapter 5 of [1]
8 11.02.2025 (Tue) Dual of an LP, weak duality theorem Slides Video Chapter 6.1, 6.2 of [1]
13.02.2025 (Thu) Quiz 1
9 18.02.2025 (Tue) Strong duality: proof via simplex; Farkas' lemma statement and geometric interpretation Slides Video Chapter 6.3, 6.4 of [1]
10 20.02.2025 (Thu) Farkas' lemma variants; proof of duality using Farkas' lema, proof of Farkas's lemma Slides Video Chapter 6.4, 6.7 of [1]
11 25.02.2025 (Tue) Applications of LP:zero-sum games Slides

Slides 		Video

Video 		Chapter 8.1 of [1]
Combinatorial Optimization
13 11.03.2025 (Tue) Integer Linear Programs, Discussion about complexity, Totally unimodular matrices Video Chapter 8.2 of [1]
14 18.03.2025 (Tue) König's theorem; Non-bipartite case: min vertex cover and max independent set Slides Video Chapter 8.2 and 3 of [1]
15 20.03.2025 (Thu) Complementary slackness; Introduction to primal-dual algorithms Video Lecture 15 from [2]
16 25.03.2025 (Tue) Primal-dual algorithm for shortest paths Slides Video Lecture 22 of [2], Chapter 3.4 and 5.4 of [3]
17 27.03.2025 (Thu) Primal-dual algorithm for minimum spanning trees I Slides Video Lecture 20, 21 of [2]
18 01.04.2025 (Tue) Primal-dual algorithm for minimum spanning trees II Slides Video Lecture 20, 21 of [2]