MS&E 212: Mathematical Programming and Combinatorial Optimization (Also, CME 208)
Meeting time: TTh 1:15-2:30, Skilling 191. Problem Session/make-up class: F 1:15-2:30, Skilling 191 (occasional).
Auditors/SCPD students, please subscribe to the class mailing list msande212-spr0506-guests @lists.stanford.edu using majordomo (see http://lists.stanford.edu for more information).
Contact:Terman 311, ashishg @ stanford.edu, 650 724 1463
Office Hours: Tue 3:00-5:00 pm
Contact: null @ stanford.edu
Office Hours: Thu 3:00-4:00 pm, Terman 491
Unless you want to specifically contact either the CA or the instructor, please use
Class Description: Combinatorial and mathematical programming (integer and non-linear) techniques for optimization. Topics: linear program duality and LP solvers; integer programming; combinatorial optimization problems on networks including minimum spanning trees, shortest paths, and network flows; matching and assignment problems; dynamic programming; linear approximations to convex programs; NP-completeness. Hands-on exercises.
Prerequisites: CS 106A or X; ENGR 62 or Math 103. Alternate pre-requisites: Programming knowledge in some high-level language, and exposure to either linear programming or linear algebra.
Required Textbook: Combinatorial Optimization; by Cook, Cunningham, Pulleybank, and Schrijver; Wiley 1997.
Recommended Textbooks: (1) Introduction to Operations Research; by Hillier and Lieberman; McGraw-Hill 8th edition, 2005. (2) AMPL: A Modeling Language for Mathematical Programming; by Fourer, Gay, and Kernighan; Duxbury Press 2002.
We have requested that these textbooks be placed on reserve in the Engineering library. In the past, most students have preferred to buy their textbooks online, so we have not ordered them at the bookstore. Let us know (for future reference) if you would have preferred to buy them at the bookstore.
Grading and Course-Load : There will be 4 HW assignments of 7.5% each. There will be a group project (3-4 students in each group) that will be worth 20%.The midterm will be worth 25%. And the final exam will be worth 30%. (I know it adds to more than 100–if you get more than 100, you will get an A+ in this class).
4/7/2006: Discussion section – AMPL tutorial and LP duality
4/13/2006: HW 1 handed out, due 4/21/2006
4/18/2006: Project descriptions handed out; project group choices due on 4/25/2006
4/25/2006: HW 2 handed out, due 5/4/2006
4/28/2006: Discussion section
5/11/2006: Discussion section
5/12/2006:In class midterm (90 minutes)
5/16/2006:Preliminary project report due; HW 3 handed out, due 5/25/2006
5/25/2006:HW 4 handed out, due 6/2/2006
6/2/2006: Project presentations
6/6/2006:Discussion section; final project reports due
Introductory material: Linear Program duality; LP solvers; Sorting and heaps; Integer Programs
Min-cost flow: vertex-optimal solutions and integrality; transportation, assignment, shortest paths, and max-flow as special cases
Combinatorial algorithms for shortest paths and spanning trees
Combinatorial algorithms for max-flow; the max-flow min-cut theorem and Hall’s theorem
Basic dynamic programming
Introduction to convex programming – separation oracles and semi-definite programming
Integer Programs: branch and bound methods and relaxations
Special topic: stable marriages (time permitting)
We will make scribed notes (prepared by a course assistant) for the lectures available a few days after each lecture. These are only accessible with an SuID. If you have problems accessing the notes, please let us know.