Prerona Chatterjee

Linear Programming and Combinatorial Optimisation

• Introductory course for incoming graduate students and senior undergraduate students.
• Class Timings: Mondays and Wednesdays from 5:30 PM to 7:00 PM.
• Location: M2
• 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)

 

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

 

Lecture Summary

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

• Lecture 1 (Aug 03, 2026): Formulating problems as an LP, objective functions and constraints.
• Lecture 2 (Aug 05, 2026): More examples of formulating computational problems as LPs.
• Lecture 3 (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 4 (Aug 19, 2026): Basic Feasible Solutions and Vertices of the Feasible Region
• Lecture 5 (Aug 21, 2026):
• Lecture 6 (Aug 24, 2026):
• Lecture 7 (Aug 28, 2026):

Week 5: Duality Theory

• Lecture 8:
• Lecture 9:

Week 6 and 7: Minimax Theorems and the Primal Dual Method

• Lecture 10:
• Lecture 11:
• Lecture 12:
• Lecture 13:

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

• Talk 1:
• Talk 2:
• Talk 3:
• Talk 4:
• Talk 5:
• Talk 6:
• Talk 7:

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

Week 11: Ellipsoid and Interior Point Methods

• Lecture 14:
• Lecture 15:

Weeks 12, 13 and 14: Semi-definite Programming

• Lecture 16:
• Lecture 17:
• Lecture 18:
• Lecture 19:
• Lecture 20:
• Lecture 21: