Linear Optimization

Jan - Apr 2020


Instructor :  B Srivathsan
 
TAs : Ashwani Anand (M.Sc Computer Science, first year)
A R Sricharan (M.Sc Computer Science, first year)


Course Description

Part 1: Introduction to Linear Programs, Simplex Algorithm

Part 2: Duality, Applications of LP, Advanced algorithms for LP (if time permits)


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

Problem Sets

Set 1       Set 2       Set 3

Lectures

Lecture 1 06.01.2020 Linear Programming problem, Examples Chapters 1 and 2 of [1]
Lecture 2 09.01.2020 More examples, motivation and introduction to integer linear progamming Chapter 2 of [1]
Lecture 3 14.01.2020 Integer linear programming and LP relaxation Chapter 3 of [1]
Lecture 4 16.01.2020 Equational form of LP

Recap of some linear algebra: row rank = col rank 		Chapter 4.1 of [1]

Lectures 1 - 6 of Prof. Sundar's notes [2]
Lecture 5 21.01.2020 Basic feasible solutions Chapter 4.2 of [1]
Lecture 6 23.01.2020 Problem solving session Problem Set 3
28.01.2020 Quiz 1
Lecture 7 30.01.2020 An algorithm for solving LP (preparation for simplex)
Lecture 8 04.02.2020 Simplex method Sections 5.1 and 5.2 of [1]
Lecture 9 06.02.2020 More on simplex: degenerate pivot steps, detecting infeasibility, formalization Sections 5.3, 5.4 and 5.5 of [1]
Lecture 10 11.02.2020 Pivoting rules, Proof of termination when Bland's rule is used

Convex sets, {x: Ax <= b} is convex, Linear functions 		Sections 5.7, 5.8 of [1]

Lecture 7 from [2]
Lecture 11 18.02.2020 Extreme points, Optimum occurs at an extreme point Lectures 8, 9, 10a from [2]
20.02.2020 Mid-semester Exam
Lecture 12 03.03.2020 Duality, Proof of duality via simplex Sections 6.1 and 6.3 of [1]
Lecture 13 05.03.2020 Exercises in Dualization Sections 6.2 of [1]
Lecture 14 10.03.2020 Farkas lemma and its variants Section 6.4 of [1]
Lecture 15 12.03.2020 Proof of duality via Farkas' lemma Section 6.4 of [1]

Part II of the course: Videos

Due to COVID-19, the second part of the course will continue through videos. This includes part of content taught after mid-semester examination.

Video 1 20.03.2020 Dual of an LP Link Section 6.1 of [1]     Notes
Video 2 24.03.2020 Dual of dual; Writing the duals for different LP forms Link Section 6.2 of [1]     Notes
Video 3 26.03.2020 Proof of duality via Simplex Link Section 6.3 of [1]     Notes Assignment 1 (due 31 March 2020, 5 PM)
Video 4 31.03.2020 Geometric interpretation of duality - Part 1 Link Lecture 11 from [2] Notes
Video 5 02.04.2020 Geometric interpretation of duality - Part 2 Link Lecture 13, 14 from [2] Notes
Video 6 07.04.2020 Complementary Slackness Link Lecture 15 from [2] Notes
09.04.2020 Assignment 2 (due 16 April 2020, 5 PM)
Video 7 14.04.2020 Applications of LP: Zero-sum games - Part 1 Link Section 8.1 of [1] Notes
Video 8 16.04.2020 Applications of LP: Zero-sum games - Part 2 Link Section 8.1 of [1] Notes
Video 9 21.04.2020 Applications of LP: Zero-sum games - Part 3 Link Section 8.1 of [1] Notes