# 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