## 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

- Jan 3: Introduction to linear programming, examples (Chapter 1 of [MG])
- Jan 5: Expressing computational problems as linear programs (Chapter 2 of [MG])
- Jan 18: Linear programs in equational form, Basic feasible solutions, convexity and convex polyhedra (Chapter 4 of [MG])
- 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])
- 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])
- Jan 25: Simplex continued: unboundedness, degeneracy, finding initial BFS using artificial variables (Sections 5.2,5.3,5.4 of [MG])
- 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