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