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

- 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]
- 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])
- 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])
- Jan 15: Simplex algorithm: moving
from bfs to bfs, choosing a profitable column (Section 2.1, 2.2 of [HK])
- Jan 20: Simplex algorithm: geometric interpretation, working with tableaux, complexity of simplex
- 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
- 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])