# Linear Optimization

## Apr - Jul 2021

 Instructor : B Srivathsan

## Course Description

Basics: Writing Linear Programs, Integer Linear Programs

Algorithms for LPs: Simplex, Primal-dual algorithm

Duality

Applications of LP: zero-sum games, matchings and vertex covers in graphs

## 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

## Problem Sets

Problem Set 1     Problem Set 2     Problem Set 3    Problem Set 4    Problem Set 5    Problem Set 6

## Lectures

 Lecture 1 13.04.2021 Linear Programming problem, Examples Chapters 1 and 2 of [1] Slides Video Lecture 2 17.04.2021 Solving LPs in 2 dimensions; Integer Linear Programs; LP relaxation; Maximum weight matching Chapters 1 and 3 of [1] Slides Video Lecture 3 20.04.2021 ILP Vs LP relaxation: Minimum vertex cover, Maximum independent set Chapter 3 of [1] Slides Video Lecture 4 04.05.2021 Equational form; Some linear algebra basics Chapter 4.1 of [1] Lecture 3 of [2] Slides Video Lecture 5 06.05.2021 Dimension of the nullspace of A in terms of row rank and column rank Lectures 4 and 6 of [2] Slides Video Lecture 6 11.05.2021 Basic feasible solutions Chapter 4.2 of [1] Slides Video Lecture 7 13.05.2021 Discussion of Problem Sheets 1 and 2 Slides Video Lecture 8 18.05.2021 Convex polyhedra, vertices, extreme points and basic feasible solutions Chapter 4.3 and 4.4 of [1] Lectures 7, 8, 9 of [2] Slides Video Lecture 9 20.05.2021 The Simplex method Chapter 5.1, 5.2 and 5.3 of [1] Slides Video Lecture 10 22.05.2021 The Simplex method - finding initial feasible basis, formalization Chapter 5.4, 5.5 and 5.6 of [1] Slides Video Lecture 11 25.05.2021 The Simplex method - proof of termination when Bland's pivoting rule is used Chapter 5.7, 5.8 of [1] Slides Video Lecture 12 27.05.2021 Dual of an LP, Weak duality theorem Chapter 6.1, 6.2 of [1] Slides Video Lecture 13 01.06.2021 Proof of duality using Simplex Chapter 6.3 of [1] Slides Video Lecture 14 03.06.2021 Discussion of Problem Set 3 Slides Video Lecture 15 08.06.2021 Some clarifications about bfs and extreme points Slides Video Lecture 16 10.06.2021 Geometric interpretation of duality Slides Video Lecture 17 15.06.2021 Complementary Slackness Lecture 15 from [2] Slides Video Lecture 18 Combinatorial optimization, introduction to primal-dual algorithms, a primal-dual algorithm for shortest paths Lecture 22 of [2], Chapter 3.4 and 5.4 of [3] Slides Video Lecture 19 A primal-dual algorithm for minimum spanning trees - I Lecture 20, 21 of [2] Slides Video Lecture 20 A primal-dual algorithm for minimum spanning trees - II Lecture 20, 21 of [2] Slides Video Lecture 21 A primal-dual 2-approximation algorithm for minimum vertex cover These notes Slides Video Lecture 22 Applications of LP: Zero-sum games I (model definition, pure strategies) Section 8.1 of [1] Slides Video Lecture 23 Applications of LP: Zero-sum games II (randomized strategies, maxmin and minmax) Section 8.1 of [1] Slides - Part 1    Slides - Part 2 Video - Part 1     Video - Part 2