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.

Topics include:

  • 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).

12 Credits

Image Credit: Giacomo Nannicini