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 maximum-flow minimum-cut theorem

o   Assignment problem, bipartite matching and Halls 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.

 

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 msande111-win1415-staff@lists.stanford.edu.  If you are not taking this class for credit at Stanford, you can subscribe to our guest e-mail list, msande111-win1415-guests@lists.stanford.edu via mailman.

 

Course Text

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

 

Problem Sessions 

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

 

      Section 1

      Section 2 + Excel spreadsheet

      Section 3

      Section 4 (+ appendix)

      Section 5

      Section 6

      Section 7

      Section 8

 

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 Policy

The Grading Policy is the following:

      Homework – 25%

      Team project – 25%

      Midterm – 20%

      Final – 30%

 

Midterm

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.

      Practice Midterm, Solutions

      Midterm, Solutions, Distribution

 

Final

The Final will be held on Monday, March 16th in 370–370 from 12:15pm to 3:15pm as instructed by the registrars 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.

      Practice Final + Solutions

 

Prerequisites

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. 

 

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: Zero-Sum 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: NP-Completeness, Approximation Algorithms

      Lecture 16: Market Algorithms

 

Homework

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.

      Homework 1, due on January 14th [Solutions]

      Homework 2, due on January 28th [Solutions]

      Homework 3, due on February 11th [Solutions]

      Homework 4, due on February 25th [Solutions]

      Homework 5, due on March 11th [Solutions]

 

Project

Here are the project guidelines. The due date of the project is Tuesday, March 17th at 11:59pm.

 

Resources

      Lecture notes by Benjamin Van Roy and Kahn Mason.

      MITs Gilbert Strangs course on linear algebra, in particular lectures 1-15. Dont forget the video lectures.