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: Linear programming by Howard Karloff


Evaluation

There will be two quizzes, midsem and endsem.

Lectures

  1. Jan 6: Overview of the course, linear programs in general and standard form, examples, linear algebra basics (vector space, linear independence, affine space, dimension, rank of a matrix), geometry basics (hyperplane, halfspace, polyhedron, polytope), convex combination and convexity Ref: Sections 1.1 to 1.3 [HK]
  2. Jan 8: Basic and basic feasible solutions, every vertex is a bfs and vice versa, every vertex has n tight constraints and vice versa, degenerate bfs. (Section 1.4 [HK])
  3. Jan 13: Either the LP is unbounded or optimum is attained at a vertex, every point in a polytope is a convex combination of at most n+1 vertices (Section 1.4 [HK])
  4. Jan 15: Simplex algorithm: moving from bfs to bfs, choosing a profitable column (Section 2.1, 2.2 of [HK])
  5. Jan 20: Simplex algorithm: geometric interpretation, working with tableaux, complexity of simplex
  6. Jan 22: Introduction to duality: dual of an LP, weak and strong duality with proofs, example: bipartite matching and vertex cover as primal-dual pairs
  7. Jan 27: Leftover topic: Degeneracy and cycling in simplex: Bland's rule and proof (Section 2.3 of [HK] and Section 5.8 of [MG])