| Week of | Monday | Wednesday |
|---|---|---|
| 09/02/02 | Introduction
Ch. 1 |
|
| 09/09/02 | Polyhedra; extreme points
Sec. 2.-2.2 HW 1 Due |
Degeneracy; existence and optimality of BFSs
Sec. 2.3-2.6 |
| 09/16/02 | Optimality conditions; the simplex method
Sec. 3.1-3.2 HW 2 Due |
Simplex method implementations
Sec. 3.2-3.3 |
| 09/23/02 | VACATION - NO CLASS
|
Anticycling, phase I, complexity
Sec. 3.4-3.5, 3.7 |
| 09/30/02 | Duality; proof based on simplex
Sec. 4.7 HW 3 Due |
Interpretation of duality; dual simplex
Farkas lemma Sec. 4.4-4.6 |
| 10/07/02 | Separating hyperplanes and duality
Sec. 4.7 |
Cones, rays, representation of polyhedra
Sec. 4.8-4.9 HW 4 Due |
| 10/14/02 | VACATION - NO CLASS | Sensitivity analysis
Sec. 5.1-5.2, 5.4 Evening Exam (covers up to Sec. 4.6) |
| 10/21/02 | Parametric programming;
delayed column generation; cutting planes Sec. 5.5, 6.1-6.3 |
Dantzig-Wolfe decomposition
Sec. 6.4 HW 5 Due |
| 10/28/02 | Interior point methods: affine scaling
Sec. 9.1-9.2 |
Other interior point methods
Sec. 9.3-9.4 |
| 11/04/02 | Network problems and the simplex method
Sec 7.1-7.3 HW 6 DUE |
Negative cost cycle algorithm
Maximum flow problem Sec. 7.4-7.5 |
| 11/11/02 | VACATION - NO CLASS | Duality in networks; shortest path problem
Sec. 7.6, 7.9 HW 7 Due |
| 11/18/02 | In-class quiz (covers up to Sec. 7.5) | Auction algorithm
Sec. 7.8 |
| 11/25/02 | Integer programming formulations
Sec. 101-10.2 HW 8 Due |
Cutting plane methods
Branch & bound Sec. 11.1-11.2 |
| 12/02/02 | Integer programming duality;
Lagrangean relaxation Sec. 11.4 |
Integer programming techniques
Sec. 11.3, 11.5, 11.6 HW 9 Due |
| 12/09/02 | Introduction to NP-completeness
Sec. 11.8 |
In-class quiz |