|Aug. 29||Introduction. Examples of linear and integer programs. Solution by graphical inspection. Linear programs in abstract form.||Lecture notes 1.
"The algorithms that runs the world" article.
|Aug. 31 - Sep. 7||Applications. Maximum flow. Combinatorial (reverse) auctions. Zero-sum games. Markov decision processes. (Kemeny) rank aggregation. Sudoku.||Lecture notes 2.|
|Sep. 12||Using the GNU Linear Programming Kit and its modeling language.||Lecture notes 3. Also from class: sudoku.mod, wdp.mod. GNU Linear Programming Kit
(GLPK) (including documentation). Possibly
useful notes from IBM.
|Sep. 14||Duality. Weak duality, strong duality, complementary slackness.||Lecture notes 4.|
|Sep. 19, 21||Duality in applications.||Lecture notes 5.|
|Sep. 26||Guest lecture: Josh Letchford. Linear and integer programming in game theory.||Slides: pptx, pdf.|
|Sep. 28, Oct. 3, 5||The simplex algorithm.||Lecture notes 6.|
|Oct. 10||Homework review.|
|Oct. 12||Guest lecture: Dima Korzhyk. Commitment to correlated strategies.||Slides: pptx, pdf.|
|Oct. 17, 19||Network flow problems.||Lecture notes
|Oct. 26||Guest lecture: Angelina Vidali. (Automated) mechanism design.||Mechanism design slides,
automated mechanism design
Automated mechanism design chapter.
|Oct. 31, Nov. 2||Constraint and column generation. The cutting stock problem.||Lecture notes 8.|
|Nov. 7, 14||An illustrative example: the core and network flows.||Lecture notes 9.|
|Nov. 9||Homework review.|
|Nov. 16||Branch and bound.||Lecture notes 10.|
|Nov. 16||Valid inequalities/cutting planes.||Lecture notes 11.|
|Nov. 26||Project presentations. Pablo, Yuqian, Branka.|
|Nov. 28||Project presentations. Animesh, Garrett, Ergys+Mayuresh.|
|Nov. 30||Project presentations. Marisabel, Michael, Seyed.|