
Introduction to
Optimization (MS&E 111) Topicsá
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 maximumflow minimumcut theorem o Assignment problem, bipartite matching and HallÕs theorem á
Advanced
topics o Zerosum 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. Course Staffá 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 msande111win1415staff@lists.stanford.edu. If you are not taking this class for credit at Stanford, you can subscribe to our guest email list, msande111win1415guests@lists.stanford.edu via mailman. Course TextTextbook: 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 Problem SessionsEach 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 á Section 2 + Excel spreadsheet
Office Hoursá 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 Grading PolicyThe Grading Policy is the following: á Homework – 25% á Team project – 25% á Midterm – 20% á Final – 30% MidtermThe Midterm will be held inclass on Wednesday, February 11^{th}. It will be a 75minute closedbook 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. á Midterm, Solutions, Distribution FinalThe Final will be held on Monday, March 16^{th} 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. PrerequisitesThe 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. Lecturesá Lecture 1: Introduction to Optimization [see also: VRM, chapter 1] á Lecture 2 and 3: Geometric Properties [see also: VRM, sections 3.1 to 3.3] á Lecture 4: Simplex Algorithm, Linear Classification [see also: VRM, sections 3.7] á Lecture 5: Duality Theory [see also: VRM, sections 4.1.3, 4.1.4 and 4.2.1] á Lecture 6: Complementary Slackness and Sensitivity Analysis [see also: VRM, sections 4.1.1, 4.1.2, 4.2.3 and 4.2.4] á Lecture 7: ZeroSum Games [see also: VRM, section 4.4] á 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: NPCompleteness, Approximation Algorithms á Lecture 16: Market Algorithms HomeworkYou should deposit your homework in MS&E 111 dropoff 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. á Homework 1, due on January 14^{th} [Solutions] á Homework 2, due on January 28^{th }[Solutions] á Homework 3, due on February 11^{th} [Solutions] á Homework 4, due on February 25^{th} [Solutions] á Homework 5, due on March 11^{th }[Solutions]
ProjectHere are the project guidelines. The due date of the project is Tuesday, March 17^{th} at 11:59pm. Resourcesá Lecture notes by Benjamin Van Roy and Kahn Mason. á MITÕs Gilbert StrangÕs course on linear algebra, in particular lectures 115. DonÕt forget the video lectures. 



