Prerona Chatterjee

Linear Programming and Combinatorial Optimisation

• Introductory course for incoming graduate students and senior undergraduate students.
• Class Timings: Wednesdays from 5:30 PM to 6:30 PM; Fridays from 2:00 PM to 3:00 PM and 3:15 PM to 4:15 PM.
• Location: M2
• TAs: Suryendu Mondal, Praveen Kumaran P
• Lecture Notes: Link. (Please send me an email for viewing permission.)

 

References

• Understanding and Using Linear Programming (Jiří Matoušek , Bernd Gärtner)
• Combinatorial Optimization: Algorithms and Complexity (Christos H. Papadimitriou, Kenneth Steiglitz)
• Lecture notes on "Topics in Linear Programming" (Rajat Mittal)
• Lecture notes on the "Ellipsoid Method" (Michel Goemans)

 

Grading

• Assignments (take-home) - 20%
• Mid-sem (in-class) - 30%
• Seminar (in groups, in-class) - 10%
• End-sem (in-class) - 40%

 

Problem Sets

• Assignment 1
• Midsem

 

Lecture Summary

Week 1: Formulating problems as an LP and basics of LP

• Lectures 1 and (1 + 0.5) (Aug 03, 2026): Formulating problems as an LP, objective functions and constraints.
• Lectures (2 - 0.5) and 3 (Aug 05, 2026): More examples of formulating computational problems as LPs.
• Lecture 4 (Aug 07, 2026): Basics of Linear Programming, Convexity.

Week 2: No classes since I will be away for an ICTS workshop.

Weeks 3 and 4: The Simplex Algorithm and Basics of Duality

• Lecture 5 (Aug 19, 2026): Basic Feasible Solutions and Vertices of the Feasible Region
• Lectures 6 and 7 (Aug 21, 2026): Optimality at Basic Feasible Solutions, the Simplex Method through examples.
• Lecture 8 (Aug 24, 2026): The Simplex Algorithm, Bland's Pivot Rule.
• Lectures 9 and 10 (Aug 28, 2026): Correctness and Complexity of the Simplex Algorithm with Bland's Pivot Rules, Introduction to Duality.

Week 5: The Duality Theorem and Farkas' Lemma

• Lecture 11 (Aug 31, 2026): The Duality Theorem and its proof via Simplex Method.
• Lecture 12 (Sep 2, 2026): Farkas' Lemma and its equivalent variants.
• Lectures 13 and 14 (Sep 4, 2026): Proof of Duality via Farkas' Lemma, Completeness of CP Proof System via Farkas' Lemma, Minimally Infeasible Systems.

Weeks 6 and 7: Farkas' Lemma, Ellipsoid Method and Interior Point Methods

• Lecture 15 (Sep 7, 2026): Proof of Farkas' Lemma via Minimally Infeasible Systems.
• Lecture 16 (Sep 9, 2026): Ellipsoid Method.
• Lecture 17 (Sep 11, 2026): Details of Ellipsoid Algorithm when vertices of the polytope are a subset of {0,1}^n.
• Lecture 18 (Sep 14, 2026): Basics of Interior Point Methods.
• Lecture by TAs (Sep 16, 2026): Doubt clearing session for midsem.

Weeks 8 and 9: Student Talks: More Applications of Duality

• Talk 1 (Oct 5, 2026): Zero Sum Games (Amolika, Aneesh, Subham M)
• Talk 2 (Oct 6, 2026): Matchings and Vertex Covers in Bipartite Graphs (Anikt, Himanshu, Indrajeet, Yashpal)
• Talk 3 (Oct 7, 2026): Machine Scheduling (Bhuban, Kaustav, Srijit, Vedansh)
• Talk 4 (Oct 9, 2026): ILP and Approximation Algorithms (Girija Sankar, Koushiki, Subham P)
• Talk 5 (Oct 12, 2026): Upper Bounds on Codes (Aaditya, Pula Karan, Satyajit, Sayandeep)
• Talk 6 (Oct 13, 2026): Sparse Solutions of Linear Systems (Prayas, Sattvik, Vishal)
• Talk 7 (Oct 14, 2026): Transversals of d-Intervals (Ann, Gayatri, Mayuri)
• Talk 8 (Oct 15, 2026): Smallest Balls and Convex Programming (Karan G, Kanishk, Manas, Niketan)

Week 10: No classes since I will be visiting IIT Bombay.

Weeks 11 and 12: Minimax Theorems and the Primal Dual Method

Weeks 13 and 14: Basics of Semi-definite Programming