ORIE 6300: Mathematical Programming I

Fall 2014

Instructor Information

Instructor: David P. Williamson
Office: Rhodes 236
Office hours: M 2:30-3:30, Wed 11-12, and by appointment in Rhodes 236
Office phone: 255-4883
Email: My three initials AT cs.cornell.edu
 
Teaching Assistant: Chaoxu Tong
Office: Rhodes 296
Office hours: T 3-4, Th 4:30-5:30, in Rhodes 424
Email: 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.
Aug 28 Standard form linear programs and their duals. Taking a dual.
Sept 2 Polyhedra and polytopes.
Sept 4 Proof that bounded polyhedra are polytopes. Separating hyperplane theorem.
Sept 9 Combinatorial applications of duality. Fractional covering and packing. Maximum flow and minimum s-t cuts.
Sept 11 An introduction to AMPL. (Software)
Sept 16 Polars. Proof that polytopes are bounded polyhedra. Farkas' Lemma.
Sept 18 Strong duality. Optimality conditions.
Sept 23 Optimality conditions.
Sept 25 The Simplex Method. Some issues.
Sept 30 An example of the Simplex Method. Finding an initial feasible basic solution.
Oct 2 Finding an initial feasible basic solution. The complexity of a pivot.
Oct 7 Pivot rules. Bland's anticycling rule.
Oct 9 Klee-Minty cubes and the Hirsch conjecture. Varieties of simplex method: capacitated simplex.
Oct 16 Varieties of simplex method: Dual simplex. Sensitivity analysis.
Oct 21 Solving large-scale linear programs: The cutting-stock problem and column generation.
Oct 23 Solving large-scale linear programs: The Dantzig-Wolfe decomposition.
Oct 28 Good algorithms.
Oct 30 The ellipsoid method.
Nov 4 The ellipsoid method: termination.
Nov 6 Interior point methods: the affine scaling direction.
Nov 11 Interior point methods: the central path, potential reduction.
Nov 13 Interior point methods: path-following methods.
Nov 18 Introduction to NP-completeness.
Nov 20 NP-completeness reductions.
Nov 25 Introduction to conic programming.
Dec 2 Conic programming and strong duality.
Dec 4 Semidefinite programming.

Recitations

Aug 27 Linear algebra review.
Sept 3 The facility location dual.
Sept 10 No recitation.
Sept 17 Feasibility and unboundedness.
Sept 24 Pointed polyhedra.
Oct 1 The transportation problem and network simplex.
Oct 8 Uncapacitated network flow and network simplex.
Oct 15 A bound on the diameter of a polyhedron.
Oct 22 No recitation.
Oct 29 Approximation algorithms for the knapsack problem.
Nov 5 The traveling salesman problem.
Nov 12 The minimum-cost spanning tree problem.
Nov 19 Lagrangean relaxation and the traveling salesman problem.
Dec 3 Approximation algorithms for the traveling salesman problem.

Problem Sets

Lecture Notes from Previous Semesters