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).
Be able to:
- model decision making problems using linear optimization with possibly integer-valued variables,
- understand the geometry of linear problems and derivation of fundamental theorems related to linear programming,
- solve linear optimization problems using specialized algorithms such as the simplex method and its variants including the network simplex algorithm,
- solve mixed integer linear programs using specialized software and design customized algorithms,
- understand different classes of problems and be able to deduce hardness results for new problems.
Successful students should be able to achieve the following:
- Formulate Linear Programs (LPs) and be able to transform any LP into standard form.
- Write the dual LP of any given LP and understand the economic interpretation ofthe dual.
- Define a vertex, extreme point, basic (feasible) solution, convex hull, convex cone, polyhedron, norm-ball, ellipsoid, extreme ray, local optimal solution, global optimal solution.
- 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.
- Apply the simplex algorithm and its variants (revised simplex, dual simplex, network simplex, and etc.).
- Define a node, edge, graph, tree, path, network and formulate network flow theorems.
- Find the shortest path and minimum spanning tree of a network.
- Find a maximum flow and a minimum cut of a given network.
- Solve integer programs using branch-and-bound and branch-and-cut.
- Define NP-hardness and be familiar with basic results and reductions.
Image Credit: Giacomo Nannicini