This course introduces modeling concepts, theory, algorithms, computational strategies, and applications of linear programming (LP). The course is intended for computer science students, and students from other disciplines, such as mathematics, statistics, operations research, engineering, business administration, and economics. The material covered in this course provides the background required for reading the literature in this field.
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.
Five problem sets, selected readings from the literature, a midterm and a final exam, or as specified in the Class URL (upper left) for this semester.