This is a graduate level course on linear optimisation. It covers the theory of optimizing a linear function over a polyhedron, computational aspects of solving linear programs by the simplex method, graphs and the network simplex method, integer programming formulations, an overview of solution methods for integer programs, and applications.
- Linear programming formulations. Basic, nonbasic, feasible, infeasible, unbounded and optimal solutions.
- Pivoting, reduced costs, the primal simplex method. Convergence, degeneracy, cycling, anticycling devices. The fundamental theorem of linear programming.
- Duality theory. Complementary slackness. Economic interpretation of duality. Lagrangian relaxation.
- The revised simplex method. The dual simplex method.
- Sensitivity analysis.
- Systems of linear inequalities. Farkas’ Lemma, Theorems of the alternative.
- Ellipsoid method.
- Network models: max flow. The max-flow min-cut theorem. Combinatorial algorithms for network problems.
- Network simplex method.
- Integer programming formulations. Convex hull, total unimodularity, separation.
- Branch and Bound. Valid inequalities.
- The classes P and NP.
- Advanced topics (may vary from term to term).
Image Credit: Giacomo Nannicini