á Linear programming
o Modeling a problem as a linear program (LP)
o Geometry of the LP solutions
o The Simplex Algorithm and its performance
o Linear programming duality
á Combinatorial Optimization
o Network flows and maximum-flow minimum-cut theorem
o Assignment problem, bipartite matching and HallÕs theorem
á Advanced topics
o Zero-sum games and LP duality; Generalizations to Nash equilibria
o Market allocations and price equilibria
o Stochastic and online optimization
We will also discus several applications mostly from electronic commerce and finance.
á Instructor: Professor Amin Saberi
á Teaching assistants:
o Nicolas Poulallion
o Jessica Su
o Arthus de Saint Chaffray
If you are taking this class for credit, you should use discussions/lectures, problem sessions, office hours and the online discussion forum on Piazza to ask your questions. This policy helps us answer your questions quicker and more efficiently, and has the added benefit that other students can also see the question and answer.
For questions that are specific to you (and only for those questions), please email the course staff at firstname.lastname@example.org. If you are not taking this class for credit at Stanford, you can subscribe to our guest e-mail list, email@example.com via mailman.
Textbook: We will use lecture notes by Benjamin Van Roy and Kahn Mason (typically referred to as VRM), and occasionally supplement it with additional notes. The following are good reference texts, which are 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
Each week there will be a problem session on Friday from 2:15pm to 3:30pm, which will cover conceptual problems that will also be helpful with the homework that may have been released that week. The labs are an integral part of your learning experience and the material covered there may be required for the homework and the exams.
Laptops: while not strictly required, a laptop with Excel 2010 or later and more than 2 hours of battery capacity will be very useful.
Group A: First name starting with A – H: Shriram 366 with Nicolas
Group B: First name starting with I – Z: 370–370 with Jessica
á Pr. Saberi: Mondays, 3:30pm – 5pm, Huang 309
á Jessica Su: Mondays, 8pm – 9:30pm, Thornton 210
á Arthus de Saint Chaffray: Tuesdays, 10:30am – 11:30am, Spilker 143
á Nicolas Poulallion: Tuesdays, 6:30pm – 8pm, Thornton 210
The Grading Policy is the following:
á Homework – 25%
á Team project – 25%
á Midterm – 20%
á Final – 30%
The Midterm will be held in-class on Wednesday, February 11th. It will be a 75-minute closed-book exam. The syllabus for the midterm will be everything covered in class in the first five weeks. We can arrange for an alternate time for the midterm only if it is requested by the student affairs.
The Final will be held on Monday, March 16th in 370–370 from 12:15pm to 3:15pm as instructed by the registrarÕs office. It will be open books and open notes. We can arrange for an alternate time for the final only if it is requested by the student affairs.
The prerequisite for this class is familiarity with linear algebra at the level of Math 51. You can refresh your memory by reviewing Chapter 2 of VRM. A more introductory exposition is available at Khan Academy.
á Lecture 8: Applications: Online Advertising, Radiation Therapy
á Lecture 9: Applications: Finance
á Lecture 10: Applications: Finance, Part 2
á Lecture 11: Graph Theory, Hall's Marriage Theorem
á Lecture 12: Network Flows (VRM Sections 5.1 and 5.2)
á Lecture 13: Network Flows II, Applications [see also: VRM Section 5.3]
á Lecture 14: Network Flows and Applications III
á Lecture 15: NP-Completeness, Approximation Algorithms
á Lecture 16: Market Algorithms
You should deposit your homework in MS&E 111 drop-off box located in Huang basement before 12:30pm on the due date. Late assignments will receive no credit; no exception will be made. Please familiarize yourself with the Stanford Honor Code.
Here are the project guidelines. The due date of the project is Tuesday, March 17th at 11:59pm.
á Lecture notes by Benjamin Van Roy and Kahn Mason.