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


Jan-Apr 2017 Adjunct Faculty
Sept-Dec 2015 Nannicini
Sept-Dec 2014 Ahipasaoglu, Nannicini
Sept-Dec 2013 Ahipasaoglu, Nannicini

Image Credit: Giacomo Nannicini