# Linear Programming and Combinatorial Optimization

## Jan - May 2022

 Instructor : B Srivathsan

## Course Description

Linear Programming: Basic theory, Simplex algorithm, Duality

Combinatorial Optimization: Optimization problems modeled as integer linear programs, LP-approximations, Primal-dual methods

A polynomial-time algorithm for LPs: Ellipsoid method and its applications

Applications of LP: Zero-sum games

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

## Lecture Hours

Tuesday and Thursday: 9:10 AM to 10:25 AM via Zoom

Enrol in the Moodle page for the link to the lectures

## Evaluation and exam schedule

Two quizzes (30%) + Mid-semester exam (30%) + End-semester exam (40%)

Quiz 1: February 15, 9:10 AM to 10:25 AM

Mid-sem: Week of March 14 - 18

Quiz 2: April 12, 9:10 AM to 10:25 AM

End-sem: Week of May 9 - 13

## Problem Sets

Problem Sheet 1     Problem Sheet 2     Problem Sheet 3    Problem Sheet 4

## Lectures

 Lecture number Date Topic Additional reading Linear Programming 1 25.01.2022 (Tue) Introduction to linear programs, examples, general form vs equational form Slides Video Chapters 1 and 2 of [1] 2 27.01.2022 (Thu) Basic feasible solutions, an informal introduction and a formal definition Slides Video Chapter 4 of [1] 3 01.02.2022 (Tue) Basic feasible solutions; optimum occurs at a bfs when cost is bounded Slides Video Chapter 4 of [1] 4 03.02.2022 (Thu) Simplex method Slides Video Chapter 5 of [1] 5 08.02.2022 (Tue) Simplex method: degeneracy, finding an initial feasible basis, formalizing the notion of a tableau Slides Video Chapter 5 of [1] 6 10.02.2022 (Thu) Simplex method: proof of correctness (assuming termination) and a geometric interpretation Slides Video Chapter 5 of [1] 7 17.02.2022 (Thu) Simplex method: Bland's rule and proof of termination Slides Video Chapter 5 of [1] 8 24.02.2022 (Thu) Dual of an LP, weak duality theorem Slides Video Chapter 6.1, 6.2 of [1] 9 01.03.2022 (Tue) Strong duality: proof via simplex; Farkas' lemma statement and geometric interpretation Slides Video Chapter 6.3, 6.4 of [1] 10 03.03.2022 (Thu) Farkas' lemma variants; proof of duality using Farkas' lema Slides Video Chapter 6.4 of [1] 11 08.03.2022 (Tue) Proof of Farkas' lemma; Application of LP: Zero-sum games Slides Video Chapter 6.7 and 8.1 of [1] 12 10.03.2022 (Thu) Zero-sum games: maxmin equals minmax using strong duality (Pre-recorded) Slides Video Chapter 6.7 and 8.1 of [1] Combinatorial Optimization 13 29.03.2022 (Tue) Integer Linear Programs, Discussion about complexity, Totally unimodular matrices Video Chapter 8.2 of [1] 14 01.04.2022 (Fri) König's theorem; Non-bipartite case: min vertex cover and max independent set Slides Video Chapter 8.2 and 3 of [1] 15 05.04.2022 (Tue) Complementary slackness; Introduction to primal-dual algorithms Video Lecture 15 from [2] 16 07.04.2022 (Thu) Primal-dual algorithm for shortest paths (Pre-recorded) Slides Video Lecture 22 of [2], Chapter 3.4 and 5.4 of [3] 17 12.04.2022 (Tue) Primal-dual algorithm for minimum spanning trees I (Pre-recorded) Slides Video Lecture 20, 21 of [2] 18 14.04.2022 (Thu) Primal-dual algorithm for minimum spanning trees II (Pre-recorded) Slides Video Lecture 20, 21 of [2] 19 18.04.2022 (Tue) Primal-dual algorithm for minimum vertex cover (Pre-recorded) Slides Video These notes 20 20.04.2022 (Thu) Matching polytope and Fractional matching polytope; M equals FM for bipartite graphs; Half-integrality of FM Video These notes 21 26.04.2022 (Thu) Half-integrality of FM; Adding odd-set constraints to get M = FM. Video These notes 22 05.05.2022 (Thu) Half-integrality of FM; Adding odd-set constraints to get M = FM (contd.) Video These notes