Derrick Stolee
J. L. Doob Research Assistant Professor
Department of Mathematics
University of Illinois at Urbana-Champaign

Home

Teaching

Papers

Presentations

Software

Other

MATH 482 - Linear Programming

Spring 2013

Room: 443 Altgeld Instructor: Derrick Stolee
Time: MWF 11:00-11:50am Office: 226 Illini
Office Hours: T 1:00-3:00pm, R 2:00-4:00pm Email: stolee@illinois.edu
Textbook: Combinatorial Optimization: Algorithms and Complexity by C. Papadimitriou and K. Steiglitz

Syllabus

Video Notes

Software Information

Exams

The exams will be on Thursdays from 7-9pm in Altgeld 145 on:
  • Exam 1: February 28th.
  • Exam 2: April 25th.
  • Exam 3: (Make-Up) Week of April 29.

Homeworks

Homework 1Solutions
Homework 2Solutions
Homework 3, Data for Problem 5Solutions, (Solutions to Problem 5 pending)
Homework 4Solutions
Homework 5Due 04/17

Topics Discussed

  1. 01/14 - Linear Programs, solving graphically, different forms.
  2. 01/16 - Standard and Canonical Forms, Bases, Basic Feasible Solutions.
  3. 01/18 - Moving Between Basic Feasible Solutions, Organization of Tableau.
  4. 01/23 - Video Assignment: The Single-Stage Simplex Algorithm
  5. 01/25 - Review of Simplex, Bland's Pivoting Rule, Simplex Example.
  6. 01/28 - Two-Stage Simplex, Example, Intro to Duality, Two-Stage Simplex Example.
  7. 02/01 - More Duality, Complementary Slackness, Farkas' Lemma.
  8. 02/04 - Geometric Farka's Lemma, Shortest path in digraphs as LP, Dual of shortest paths.
  9. 02/06 - More on dual of shortest paths and complementary slackness, dual information in tableau, start of dual simplex algorithm.
  10. 02/08 - Dual Simplex Pivots and Dual Simplex Algorithm, Dual Simplex Example.
  11. 02/11 - Game theory for zero-sum games. Game Theory Example.
  12. 02/13 - Max Flow Problem, Edge-centric LP, Path-centric LP, linear combinations of paths and cycles.
  13. 02/15 - Revised Simplex, 2-Phase Revised Simplex. Revised 2-Phase Simplex Example
  14. 02/18 - Finish 2-Phase Revised Simplex. Revised Simplex for the Max-Flow Problem.
  15. 02/20 - Solving Linear Programs using Sage and GLPK. LP Software Listing
  16. 02/22 - Lab Day
  17. 02/25 - Max Flow/Min Cut.
  18. 02/27 - The Primal-Dual Algorithm.
  19. 03/01 - The Primal-Dual Algorithm for Shortest Paths.
  20. 03/04 - The Primal-Dual Algorithm for Max-Flow. $f$-Augmenting paths.
  21. 03/06 - The Ford-Fulkerson Algorithm and the Max-Flow/Min-Cut Theorem.
  22. 03/08 - More discussion of $f$-augmenting paths. Dijkstra's Algorithm for Shortest Paths.
  23. 03/11 - All-pairs shortest paths and the Floyd-Warshall Algorithm.
  24. 03/13 - Integer Programs, Mixed Integer Programs, Traveling Salesman Problem, Sage Example, PDF Example.
  25. 03/15 - Proof of TSP Constraint Equivalence, Scheduling Problems.
  26. 03/27 - Strength of ILP, NP-Completeness, ILP is NP-Hard.
  27. 03/29 - Total unimodularity and integer solutions to LPs.
  28. 04/01 - Cutting plane algorithms, Gomory Cuts.
  29. 04/03 - Lexicographic ordering of vectors, Finiteness of Gomory Cuts.
  30. 04/05 - Sage examples of Gomory Cuts: Book Example, Big Example, All Cuts Example.
Plan for the rest of the semester:
  • Gomory Cut Algorithm (Chapter 14).
  • Branch and Bound and Dynamic Programming (Chapter 18).
  • Local Search (Chapter 19).