ORIE 6300: Mathematical Programming I

Fall 2008

Instructor Information

Instructor: David P. Williamson
Office: Rhodes 236
Office hours: M 11-12, Thurs 1:30-2:30, and by appointment
Office phone: 255-4883
Email: My three initials AT cs.cornell.edu
Teaching Assistant: Maurice Cheung
Office: Rhodes 291
Office hours: Wednesdays 4:30-5:30, Thursdays 4:30-5
Email: myc26 AT cornell.edu


The course meets Tuesdays and Thursdays in Hollister 320 from 10:10-11:25 AM. There is a recitation section that meets Wednesdays 3:30-4:30PM in Hollister 401 Rhodes 253 Hollister 401.

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.


Handout 1: Course Information

Scribing materials

LaTeX macros for scribing


Aug 28 Introduction to linear programming and duality.
Sept 2 Standard form linear programs and their duals. Taking a dual.
Sept 4 Combinatorial applications of duality. Fractional covering and packing. Maximum flow and minimum s-t cuts.
Sept 9 Maximum flow and minimum s-t cuts. Extreme points, vertices, basic feasible solutions, and their equivalence.
Sept 11 Polytopes. Proof that bounded polyhedra are polytopes.
Sept 16 Polars. Proof that polytopes are bounded polyhedra.
Sept 23 Farkas' Lemma. Proof of strong duality.
Sept 25 Complementary slackness. Optimality conditions.
Sept 30 Optimality conditions revisited. The Simplex Method.
Oct 2 The Simplex Method. Some issues.
Oct 7 An example of the Simplex Method. Finding an initial feasible basic solution.
Oct 9 Finding an initial feasible basic solution. The complexity of a pivot.
Oct 16 Pivot rules. Bland's anticycling rule.
Oct 21 Klee-Minty cubes and the Hirsch conjecture. Varieties of simplex method: capacitated simplex.
Oct 23 Varieties of simplex method: Dual simplex. Sensitivity analysis.
Oct 28 Sensitivity analysis. Solving large-scale linear programs: The cutting-stock problem.
Oct 30 Solving large-scale linear programs: The cutting-stock problem.
Nov 4 Solving large-scale linear programs: Dantzig-Wolfe decompositions. Polynomial-time algorithms.
Nov 6 Introduction to the ellipsoid method.
Nov 11 P, NP, co-NP, and NP-completeness.
Nov 13 NP-completeness and reductions.
Nov 18 The ellipsoid method: calculating the next ellipsoid.
Nov 20 The ellipsoid method: termination.
Nov 25 Interior point methods: the affine scaling direction.
Dec 2 Interior point methods: the central path, Newton direction.
Dec 4 Interior point methods: A primal-dual short-step algorithm.


Sept 3 Linear algebra review.
Sept 10 The facility location dual.
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 The assignment problem.
Oct 29 The traveling salesman problem.
Nov 5 The minimum-cost spanning tree problem.
Nov 12 Lagrangean relaxation and the traveling salesman problem.
Nov 19 Approximation algorithms for the traveling salesman problem.
Dec 3 Approximation algorithms for the knapsack problem.

Problem Sets

Lecture Notes from Previous Semesters