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 using majordomo (see for more information).


*  Staff and Contact Information

*  Essential Class Information

*  For SCPD students

*  Handouts

*  Scribed Notes

*  Grades




Staff and Contact Information



Ashish Goel

Contact:Terman 311, ashishg @, 650 724 1463

Office Hours: Tue 3:00-5:00 pm


Course Assistant:

Brad Null

Contact: null @

Office Hours: Thu 3:00-4:00 pm, Terman 491


Unless you want to specifically contact either the CA or the instructor, please use







Essential Class Information


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


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)






For SCPD students


  1. Please subscribe to the class mailing list msande212-spr0506-guests @ using majordomo (see for more information).
  2. 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.
  3. 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).






Scribed Notes


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.






  1. Tell us about yourself (due 4/11/2006)
  2. A brief introduction to AMPL
  3. AMPL examples from the discussion section
  4. HW 1 -- given 4/15, due 4/25 in class
  5. Project descriptions
  6. HW 2 -- given 5/2, due 5/9 in class
  7. HW 1 solutions -- not available online
  8. Practice problems for the midterm
  9. HW 2 solutions -- not available online
  10. HW 3 -- given 5/16, due 5/25 in class
  11. HW 4 -- given 5/30, due 6/7 in class
  12. HW 3 solutions -- not available online
  13. Midterm solutions -- not available online
  14. Practice problems for the final
  15. HW 4 solutions -- not available online
  16. Hints for practice problems -- not available online