MS&E 111/ENGR 62. Introduction to Optimization
Autumn 2008, Stanford University
Lectures: MW 2:15-3:30, Herrin T175
Lab/discussion section: F 2:15-3:30, 380-380Y
 
STAFF

Please send email to msande111-aut0809-staff@lists.ouruniversity.edu unless you need to very specifically contact a CA or the instructor

Instructor: Ashish Goel, ashishg@ouruniversity.edu. Terman 311. Cell phone number: 650 814 1478. Office hours Thurs 3:00-4:00 pm (Oct 23rd - Dec 4th); office hours on exam week are rescheduled to Tues 5:00pm-6:30pm (Dec 9th)

Course assistants:
Benjamin Yolken, yolken@ouruniversity.edu. Office hours: Mon 6:00-7:00 pm (Terman 324)
Qi Qi, kaylaqi@ouruniversity.edu. Office hours: Wed 5:30-6:30 pm (Terman 395)
Lawrence Chow, llchow@ouruniversity.edu. Office hours: Sun 5:00-6:00 pm (Terman 323)

If you are auditing the class, please subscribe to msande111-aut0809-guests.
ESSENTIAL CLASS INFORMATION

Course Objective: To learn the basics of linear programming; applying linear programming to various real life problems; introduction to network flows; introduction to dynamic programming; Excel examples.

Textbook: There will be no formal required textbook. We will use lecture notes by Benjamin Van Roy and Kahn Mason, and occasionally supplement it with additional notes. The following are good reference texts and will be placed on reserve at the Engineering library.

  1. Introduction to Operations Research by Frederick S. Hillier and Gerald J. Lieberman
  2. Introduction to Linear Optimization by Dimitris Bertsimas and John N. Tsitsiklis
Laptops: While not strictly required, a laptop with Excel and more than 2 hours of battery capacity will be very useful.

Course load and exams: There will be six HWs, and we will count the best five. There will be a 75 minute in-class midterm on Oct 27th, a 2 hour comprehensive (i.e. everything included) final exam on Dec 10 at 12:15pm in room 200-002, and a 2 hour take home lab exam handed out between 2:15pm on Dec 10th and 2:15pm on Dec 11th. The lab exam will be available at http://www.stanford.edu/~ashishg/msande111/labexam during the specified times, and you will mail it back to Benji (at yolken@stanford.edu within 2 hours of downloading. All exams will be closed-book. Please be in class on time on exam days. The HWs, the midterm, and the final will each be worth 30 points. The lab exam will be worth another 15 points. This adds to 105 points -- if you get 100 or more (no exceptions, even if you get 99.9999) you will get an A+ .

Discussion section timetable: The sections on Fridays Oct 3, 10, 17, and Nov 7, 14, 21 will be lab sections. The section on Sep 26 will be an Excel tutorial. You are welcome to bring your laptop and try things along with the CAs. The sections on Oct 24 and Dec 5 will be review sessions for the exams. There will no sections on the remaining Fridays. The Friday sections will be over by 3:30, but you should feel free to hang around till 4:30 if you need any help about any part of the lab, if you have general Excel questions, or if you have questions about the HW.

Lab sections: The lab sections will open with a short demonstration by the CAs. Then you will do a small problem on your own (with a partner if you prefer) and check the answer against the one provided by the CAs. Please bring your own laptop (or share one with your partner). If you don't have a laptop, and can't find a partner who does, let us know and we will figure something out. The CAs will post the lab problems in advance. You are welcome to try them out at home instead of the lab section if you prefer. Attendance is optional, and you don't have to submit the results of the lab problems.

Collaboration policy for the HWs: You can discuss general strategies with other people but must solve all the problems yourself. You can do the Excel problems in the HWs with a partner if you wish; in that case your partner and you can submit just one copy of the Excel problem separate from the rest of the HW.

For Excel problems, submit the answer report (solution) from Excel and also your Linear Program formulation, with a brief description of the variables, and the constraints.

Extension policy for HWs: There will be no extensions for HWs except for documented medical reasons. The HWs will typically be posted on Monday during the weeks which have a lab section, and will be due next Monday in class. (Note: HW 6 will be out the Thu or the Fri before thanksgiving, and due after thanksgiving break).

List of topics with suggested reading (subject to change):
  1. Introduction to linear programming; the knapsack problem. Chapter 1 of Van Roy/Mason's notes (VRM 1), and section 1 of the supplemental notes (G.1)
  2. Matrix notation, graphical representation, and standard forms (VRM 2.1, 3.0,  3.1, G.2)
  3. Linear programming examples:  matchings (VRM 1.0.1, G.3), contingent claims (VRM 3.6, 2.4.1, 2.4.2), pattern classification (VRM 3.7)
  4. Some linear programming tricks: minimizing the max, maximizing the min, minimizing the absolute value (G.4)
  5. Convexity, basic feasible solutions, and optimality of basic feasible solutions (G.5, VRM 3.1-3.3), linear programming algorithms, the knapsack problem revisited (G.6.1)
  6. Production problems (VRM 3.5)
  7. Network flows: min-cost flow and the integrality of its basic feasible solutions; special cases of min-cost flow -- max-flow, shortest paths, matchings (VRM 5.1-5.2, G.7)
  8. Duality and complementary slackness (VRM 4.1-4.3), the knapsack problem revisited (G8.1-8.2)
  9. Network flows: duals of shortest paths (G8.3); the min-cut problem (VRM 5.3)
  10. Brief introduction to dynamic programming: knapsack, longest common subsequence (G9)
  11. Other examples and special topics (TBD)
LECTURE NOTES

The text by Benjamin Van Roy and Kahn Mason:
Supplementary notes by Ashish Goel (updated 12/3/2007; subject to change)

Other supplementary material:
HANDOUTS
HW solutions are handed out in class. Extra copies can be found in the folders outside Terman 395. Also, you can see last year's problem sets, labs, and practice exams if you need some advance practice problems. We wll not hand out solutions to these.

Homework Assignments:

Lab Handouts:

Other:
AVERAGES AND STANDARD DEVIATIONS