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

  7. [P] Feb 4: Duality from lower bounds, primal-dual algorithm for the shortest paths problem (Ref: Lectures 16 and 22 of [SV])
  8. [P] Feb 6: Informal introduction to integrality gap, Primal-dual algorithm for minimum spanning trees (Ref: Lectures 20, 21 of [SV])
  9. [S] Feb 11: Weak and strong duality, complementary slackness (Ref: Lecture 15 of [SV])
  10. [P] Feb 13: Bipartite matchings: Algorithmic proof of König's theorem (Ref)
  11. [P] Feb 15: Primal-dual algorithm for minimum cost perfect matching in bipartite graphs (Ref: Same as in the previous lecture)
  12. [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)

    13. Mar 4: Midsem discussion
  13. [P] Mar 6: Total unimodularity (Relevant parts from Chapter 19 of Scrijver's book (Theory of linear and integer programming))
  14. [P] Mar 8: Integrality of non-bipartite matching polytope (LP with odd-set constraints) (Ref)

    15. Module 3: Simplex method: Implementation, and complexity

  15. [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)
  16. [S] Mar 15: Simplex tableau - examples Handline Unboundedness (Ref: Sections 5.1, 5.2 from Matousek's book)
  17. [S] Mar 20: Exception handing in simplex: Degeneracy and Infeasibility (Reference: Sections 5.3 and 5.4 from Matousek's book)
  18. [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)
  19. [S] Mar 25: Bland's rule continued, Complexity of simplex: Klee-Minty examples
  20. [S] Mar 27: Farkas' lemma (Chapter 6)
  21. [S] Mar 29: Farkas' lemma and duality from Farkas' lemma

    22. Module 4: Polynomial-time algorithms for LP

  22. [P] Apr 3: Ellipsoid algorithm (Section 7.1 of Matousek's book and these notes)
  23. [P] Apr 8: Details of ellipsoid algorithm
  24. [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)
  25. [P] Apr 15: A brief overview of interior point methods (Section 7.2 of Matousek's book), Complexity of ILP (Reference)