Course Details

Canonical formulations and their equivalence. Examples of LP models: production mix, shortest paths, max flows, bipartite matching, min-cost flows, multicommodity flows; models of exponential size: minimum-spanning trees, general weighted matching. Farkas' lemma and variants; theorems of the alternative. Karush-Kuhn-Tucker optimality conditions for LP; geometric interpretation. Duality theory; von Neumann's min-max theorem; polyhedral games; generic primal-dual method; Fourier-Motzkin elimination for systems of linear inequalities; worst-case behavior. Polyhedra and polyhedral cones; vertices, edges, facets; recessive directions; basic feasible solutions and extreme points. Representation theorem. Fundamental theorem of LP. Theorems of Weyl, Carathéodory, and Helly. The (revised) simplex method: rank-one updates and pivots; monotonicity; degeneracy, cycling; finite termination: lexicographic and Bland's rules. Worst-case behavior. The (revised) dual and primal-dual simplex methods. Starting bases and pivot selection strategies. Basis-matrix factorizations. Bounded and free variables. Applications and extensions: min-norm and min-error solutions of linear systems of equations; data fitting; pattern separation; fractional programming; sensitivity analysis and parametric LP; worst-case behavior. Total unimodularity; elements of network simplex methods. Exploiting structure: column generation; the cutting stock problem; knapsack problem. Block-angular LPs: Dantzig-Wolfe decomposition; row generation; Lagrangian relaxation. Elements and theoretical significance of the ellipsoid method; minimization of submodular functions. Introduction to interior-point methods: Karmarkar's algorithm; logarithmic potential function; projective transformation; complexity analysis and precision; affine variants.