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).
Instructor:
Contact:Terman 311, ashishg @ stanford.edu, 650 724 1463
Office
Hours: Tue 3:00-5:00 pm
Course Assistant:
Brad
Null
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
msande212-spr0506-staff@lists.stanford.edu
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).
Timetable
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
Detailed Syllabus
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
NP-completeness
Integer
Programs: branch and bound methods and relaxations
Special
topic: stable marriages (time permitting)
- Please subscribe to the class mailing list
msande212-spr0506-guests @ lists.stanford.edu using majordomo (see http://lists.stanford.edu
for more information).
- We would prefer to have the SCPD students on
campus for the project presentations, but at the very least, two members
from each group should be there. So please take this into account while
forming groups.
- If you need help finding a project group, please
let the CA know a week before the project groups are due (send him your
preferences for the projects, and also whether you will be able to come to
campus for project presentations).
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.
- Tell us about yourself (due 4/11/2006)
- A brief introduction to
AMPL
- AMPL examples from the
discussion section
- HW 1 -- given 4/15, due
4/25 in class
- Project descriptions
- HW 2 -- given 5/2, due
5/9 in class
- HW 1 solutions -- not
available online
- Practice problems for
the midterm
- HW 2 solutions -- not
available online
- HW 3 -- given 5/16, due
5/25 in class
- HW 4 -- given 5/30, due
6/7 in class
- HW 3 solutions -- not
available online
- Midterm solutions -- not
available online
- Practice problems for
the final
- HW 4 solutions -- not
available online
- Hints for practice problems -- not
available online
