Linear Programming and Combinatorial Optimization

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

[MG] Understanding and Using Linear Programming by Jiřì Matoušek, Bernd Gärtner
[SV] Notes by Prof. Sundar Vishwanathan

Announcements

Next class will be on Jan 18th in the usual slot, no class on Jan 11th and Jan 13th

Lectures


  1. Jan 3: Introduction to linear programming, examples (Chapter 1 of [MG])
  2. Jan 5: Expressing computational problems as linear programs (Chapter 2 of [MG])
  3. Jan 18: Linear programs in equational form, Basic feasible solutions, convexity and convex polyhedra (Chapter 4 of [MG])
  4. Jan 20: Recap of basic concepts from linear algebra: vector spaces, linear combinations, basis, dimension, row space, column space, and null space of a matrix, row rank=column rank (Appendix of [MG])
  5. Jan 20: Vertex of the feasible region of an LP, basic feasible solutions and optimality, execution of the simplex method (Chapter 4 and Section 5.1 of [MG])
  6. Jan 25: Simplex continued: unboundedness, degeneracy, finding initial BFS using artificial variables (Sections 5.2,5.3,5.4 of [MG])
  7. Jan 27: Formal description of simplex method, pivot rules, efficiency and Klee-Minty example (Sections 5.5,5.6,5.6,5.9 of [MG])
    Several references e.g. this one give examples for cycling
  8. Feb 1: Simplex doesn't cycle: Proof of Bland's rule (Section 5.8 of [MG])

    9. Feb 3: Class cancelled due to Tessellate
  9. Feb 8: LP duality: Construction of dual and weak duality (Section 6.1,6.2 from [MG])
  10. Feb 15: Proof of LP duality from simplex method, statement of Farka's lemma (Section 6.3 of [MG])
  11. Feb 17: Relation between strong duality and Farka's lemma (Section 6.4 of [MG])

    12. Midsem week


  12. Mar 1: Complementary slackness, primal-dual method, a primal-dual algorithm for directed shortest paths Ref
  13. Mar 3: Primal-dual algorithm (Kruskal's) for minimum spanning trees Ref

    14. Mar 8: Class cancelled due to Prof. Howard Straubing's lecture
  14. Mar 10: Introduction to network flows, Max-flow min-cut theorem via LP duality, introduction to matchings (Ref: Algorithms by Dasgupta, Papadimitrou, Vazirani)
  15. Mar 15: Bipartite matching and vertex cover as primal-dual pairs, Algorithmic proof of König's theorem (Ref)
  16. Mar 17: Integrality of bipartite perfect matching polytope (Ref: same as above)
  17. Mar 22: 1/2-integrality of vertex cover polytope and 2-approximation by rounding, weighted vertex cover 2-approximation by primal-dual (Ref and this)
  18. Mar 24: Integrality of non-bipartite perfect matching polytope (ref)
  19. Mar 29: Total unimodularity (Ref: relevant parts of Chapter 19 of Schrijver's book titled Theorey of Linear and Integer Programming)
  20. Mar 31: Strongly vs weakly polynomial-time, introduction to ellipsoid algorithm (Ref: Section 7.1 of [MG], these notes)
  21. Apr 5: Details of ellipsoid algorithm (Ref: same as above)
  22. Apr 12: 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)
  23. Apr 19: A brief overview of interior point methods (Section 7.2 of Matousek's book), Complexity of ILP (Reference)