## Linear Programming and Combinatorial Optimization (Jointly offered with B. Srivathsan)

The course aims to cover basics of linear programming, algorithms to find an optimum solution to a linear program, combinatorial optimization and applications of LP

### References

[SV] For initial part, these notes by Prof. Sundar Vishwanathan will be used.

### Evaluation

There will be two quizzes, midsem and endsem.

### Tutorials

1. Jan 7: Tutorial 1
2. Jan 18: Tutorial 2
3. Feb 8: Tutorial 3

### Lectures

([S] and [P] denote lectures by Srivathsan and Prajakta respectively.)

#### Module 1: Linear programming: Theory and simplex method

1. [S] Jan 2: Introduction, linear algebra basics: Gaussian elimination, vector spaces, subspaces, linear independence, basis, dimension (Ref: Lectures 1-3 from [SV])
2. [S] Jan 4: Linear algebra continued: null space of a matrix, rank-nullity theorem (Ref: Lectures 4-6 from [SV])
3. [S] Jan 9: Convex sets, extreme points, linear functions (Ref: Lectures 7,8 of [SV])
4. [S] Jan 11: Convex combinations, maximization of a linear function over a convex polytope (Ref: Lectures 9,10 of [SV])
5. [S] Jan 16: Simplex algorithm and its correctness (Ref: Lectures 11,12 of [SV])
6. [S] Jan 28: Duality: geometric interpretation (Ref: Lectures 13, 14 of [SV])
7. #### Module 2: Combinatorial optimization

8. [P] Feb 4: Duality from lower bounds, primal-dual algorithm for the shortest paths problem (Ref: Lectures 16 and 22 of [SV])
9. [P] Feb 6: Informal introduction to integrality gap, Primal-dual algorithm for minimum spanning trees (Ref: Lectures 20, 21 of [SV])
10. [S] Feb 11: Weak and strong duality, complementary slackness (Ref: Lecture 15 of [SV])
11. [P] Feb 13: Bipartite matchings: Algorithmic proof of König's theorem (Ref)
12. [P] Feb 15: Primal-dual algorithm for minimum cost perfect matching in bipartite graphs (Ref: Same as in the previous lecture)
13. [P] Feb 18: Minimum weight vertex cover: 2-approximation using the primal-dual method (Ref), half-integrality of the vertex-cover polytope (Section 3 of this)

14. Mar 4: Midsem discussion
15. [P] Mar 6: Total unimodularity (Relevant parts from Chapter 19 of Scrijver's book (Theory of linear and integer programming))
16. [P] Mar 8: Integrality of non-bipartite matching polytope (LP with odd-set constraints) (Ref)
17. #### Module 3: Simplex method: Implementation, and complexity

18. [S] Mar 13: LPs in Equational form, Basic feasible solutions, If optimal exists, it is obtained from a basic feasible solution (Reference: Sections 4.1 and 4.2 from book: Understanding and using Linear Programming, by Matousek and Gartner (2006 edition)
19. [S] Mar 15: Simplex tableau - examples Handline Unboundedness (Ref: Sections 5.1, 5.2 from Matousek's book)
20. [S] Mar 20: Exception handing in simplex: Degeneracy and Infeasibility (Reference: Sections 5.3 and 5.4 from Matousek's book)
21. [S] Mar 22: Formalizing the Simplex Tableau, each step gives a valid tableau, Bland's rule for pivoting (Reference: Sections 5.5 and 5.6)
22. [S] Mar 25: Bland's rule continued, Complexity of simplex: Klee-Minty examples
23. [S] Mar 27: Farkas' lemma (Chapter 6)
24. [S] Mar 29: Farkas' lemma and duality from Farkas' lemma
25. ### Module 4: Polynomial-time algorithms for LP

26. [P] Apr 3: Ellipsoid algorithm (Section 7.1 of Matousek's book and these notes)
27. [P] Apr 8: Details of ellipsoid algorithm
28. [P] Apr 10: Application of ellipsoid algorithm for solving LP with exponentially many constraints and polynomial-time separation oracle: Non-bipartite matching (Reference, also see Section 6.5 of this)
29. [P] Apr 15: A brief overview of interior point methods (Section 7.2 of Matousek's book), Complexity of ILP (Reference)