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

Learning Objectives

Be able to:

  1. model decision making problems using linear optimization with possibly integer-valued variables,
  2. understand the geometry of linear problems and derivation of fundamental theorems related to linear programming,
  3. solve linear optimization problems using specialized algorithms such as the simplex method and its variants including the network simplex algorithm,
  4. solve mixed integer linear programs using specialized software and design customized algorithms,
  5. understand different classes of problems and be able to deduce hardness results for new problems.

Measurable Outcomes

Successful students should be able to achieve the following:

  1. Formulate Linear Programs (LPs) and be able to transform any LP into standard form.
  2. Write the dual LP of any given LP and understand the economic interpretation ofthe dual.
  3. Define a vertex, extreme point, basic (feasible) solution, convex hull, convex cone, polyhedron, norm-ball, ellipsoid, extreme ray, local optimal solution, global optimal solution.
  4. Prove the representation theorems for bounded and pointed polyhedra, the fundamental theorem of LP, the separating hyperplane theorem, Farkas lemma, and weak and strong duality theorems.
  5. Apply the simplex algorithm and its variants (revised simplex, dual simplex, network simplex, and etc.).
  6. Define a node, edge, graph, tree, path, network and formulate network flow theorems.
  7. Find the shortest path and minimum spanning tree of a network.
  8. Find a maximum flow and a minimum cut of a given network.
  9. Solve integer programs using branch-and-bound and branch-and-cut.
  10. Define NP-hardness and be familiar with basic results and reductions.

12 Credits
Prerequisites: –

Image Credit: Giacomo Nannicini