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šk, 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