MS&E 111/ENGR 62. Introduction to Optimization
Autumn 2007, Stanford University
Lectures: MW 2:15-3:30, HEWLETT 201
Lab/discussion section: F 2:15-4:00, EDUC 128

STAFF

Please send email to msande111-aut0708-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 Tu 2-3:00 pm (starting Oct 2)

Course assistants:

Brad Null, null@ouruniversity.edu. Office hours: F 12:30-1:30, Terman 491.
Benjamin Yolken, yolken@ouruniversity.edu. Office hours: Th 5:30-6:30 pm, Terman 324.

If you are auditing the class, please subscribe to msande111-aut0708-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 seven HWs, and we will count the best six. There will be a 90 minute in-class midterm on Oct 29th, a 2 hour comprehensive (i.e. everything included) final exam on Dec 10 at 12:15pm, and a 2 hour take home lab exam handed out on Dec 10th. All exams will be closed-book. 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 5, 12, 19, and Nov 9, 16, 30 will be lab sections. The section on Sep 28 will be an Excel tutorial. You are welcome to bring your laptop and try things along with the CAs. The sections on Oct 26 and Dec 7 will be review sessions for the exams. The tutorial and the review sections will be from 2:15-3:30.

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. The lab sections will be over by 3:30, but you should feel free to hang around till 4:00 if you need any help about any part of the lab or if you have general Excel questions. 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 schedule a make-up section for you on Fri mornings. 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 be posted on Monday morning during the weeks which have a lab section, and will be due next Monday in class.

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. Two person zero-sum games (covered briefly, not part of exam syllabus)
  12. 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/7)

Other supplementary material:
HANDOUTS
  1. Homework 1
  2. Lab 1 (click here for the .xls we built during the lab)
  3. Homework 2
  4. Lab 2 (iris.xls, solutions spreadsheet)
  5. Homework 3
  6. Lab 3 (click here for an.xls solving this problem)
  7. Practice midterm (question 1 graph)
  8. Practice midterm solutions
  9. Homework 4 (currencies.xls)
  10. Lab 4 (telco_example.pdf, solutions spreadsheet)
  11. Homework 5
  12. Lab 5 (solutions)
  13. Homework 6 (blast.txt, largemaxflow.xls)
  14. Notes from discussion section on Monday, December 3 (section_notes.pdf)
  15. Practice problems for the final (revised)
  16. Solutions to practice problems for final
HW solutions are handed out in class. Extra copies can be found in the folders outside Terman 491.
AVERAGES AND STANDARD DEVIATIONS
HW/Exam
 Average
 Standard Deviation
 MAX
HW 1
 79
 13.4
 98
HW 2
 31
 7.9
 40
HW 3
 43
 13.4
 59
Midterm
 39
 10.9
 50
HW 4
 25
 9.1
 36
HW 5
 49
 6
 59
HW 6
 30
 11.0
 44
Final Exam
 40.0
 14.9
 62
Final Lab
 17.2
 3.6
 20
Total
 74.9
 23.5
 104.5

ANNOUNCEMENTS ARCHIVE