ORIE 6300: Mathematical Programming I

Fall 2014

Instructor Information

Instructor: David P. Williamson Rhodes 236 M 2:30-3:30, Wed 11-12, and by appointment in Rhodes 236 255-4883 My three initials AT cs.cornell.edu Chaoxu Tong Rhodes 296 T 3-4, Th 4:30-5:30, in Rhodes 424 ct423 AT cornell.edu

Overview

The course meets Tuesdays and Thursdays in Hollister 320 from 1:25-2:40 PM. There is a recitation section that meets Wednesdays 3:30-4:30PM in Hollister 320.

This course gives a rigorous treatment of the theory and computational techniques of linear programming and its extensions, including formulation, duality theory, algorithms, sensitivity analysis, network flow problems and algorithms, theory of polyhedral convex sets, systems of linear equations and inequalities, Farkas' lemma, and exploiting special structure in the simplex method and computational implementation. Topics covered will include the ellipsoid method, interior-point methods, and computational complexity issues related to optimization problems.

Handouts

Handout 1: Course Information

Scribing materials

LaTeX macros for scribing and problem sets

Lectures

 Aug 26 Introduction to linear programming and duality. Standard form linear programs and their duals. Taking a dual. Polyhedra and polytopes. Proof that bounded polyhedra are polytopes. Separating hyperplane theorem. Combinatorial applications of duality. Fractional covering and packing. Maximum flow and minimum s-t cuts. An introduction to AMPL. (Software) Polars. Proof that polytopes are bounded polyhedra. Farkas' Lemma. Strong duality. Optimality conditions. Optimality conditions. The Simplex Method. Some issues. An example of the Simplex Method. Finding an initial feasible basic solution. Finding an initial feasible basic solution. The complexity of a pivot. Pivot rules. Bland's anticycling rule. Klee-Minty cubes and the Hirsch conjecture. Varieties of simplex method: capacitated simplex. Varieties of simplex method: Dual simplex. Sensitivity analysis. Solving large-scale linear programs: The cutting-stock problem and column generation. Solving large-scale linear programs: The Dantzig-Wolfe decomposition. Good algorithms. The ellipsoid method. The ellipsoid method: termination. Interior point methods: the affine scaling direction. Interior point methods: the central path, potential reduction. Interior point methods: path-following methods. Introduction to NP-completeness. NP-completeness reductions. Introduction to conic programming. Conic programming and strong duality. Semidefinite programming.

Recitations

Aug 27 Linear algebra review. The facility location dual. No recitation. Feasibility and unboundedness. Pointed polyhedra. The transportation problem and network simplex. Uncapacitated network flow and network simplex. A bound on the diameter of a polyhedron. No recitation. Approximation algorithms for the knapsack problem. The traveling salesman problem. The minimum-cost spanning tree problem. Lagrangean relaxation and the traveling salesman problem. Approximation algorithms for the traveling salesman problem.