|
|
|
|
|
|
1 |
|
|
|
|
|
|
|
Introduction
Ch. 1 |
|
|
|
|
|
|
|
|
|
|
|
2 |
|
|
|
Polyhedra; Extreme Points
Sec. 2.-2.2
HW 1 Due |
|
|
|
Degeneracy; Existence and Optimality of BFSs Sec. 2.3-2.6 |
|
|
|
|
|
|
|
|
|
|
|
3 |
|
|
|
Optimality Conditions; The Simplex Method
Sec. 3.1-3.2
HW 2 Due |
|
|
|
Simplex Method Implementations
Sec. 3.2-3.3 |
|
|
|
|
|
|
|
|
|
|
|
4 |
|
|
|
|
|
|
|
Anticycling, Phase I, Complexity
Sec. 3.4-3.5, 3.7 |
|
|
|
|
|
|
|
|
|
|
|
5 |
|
|
|
Duality; Proof Based on Simplex
Sec. 4.7
HW 3 Due |
|
|
|
Interpretation of Duality; Dual Simplex
Farkas Lemma
Sec. 4.4-4.6 |
|
|
|
|
|
|
|
|
|
|
|
6 |
|
|
|
Separating Hyperplanes and Duality
Sec. 4.7 |
|
|
|
Cones, Rays, Representation of Polyhedra
Sec. 4.8-4.9
HW 4 Due |
|
|
|
|
|
|
|
|
|
|
|
7 |
|
|
|
|
|
|
|
Sensitivity Analysis
Sec. 5.1-5.2, 5.4
Evening Exam (covers up to Sec. 4.6) |
|
|
|
|
|
|
|
|
|
|
|
8 |
|
|
|
Parametric Programming;
Delayed Column Generation; Cuttingplanes
Sec. 5.5, 6.1-6.3 |
|
|
|
Dantzig-Wolfe Decomposition
Sec. 6.4
HW 5 Due |
|
|
|
|
|
|
|
|
|
|
|
9 |
|
|
|
Interior Point Methods: Affine Scaling
Sec. 9.1-9.2 |
|
|
|
Other Interior Point Methods
Sec. 9.3-9.4 |
|
|
|
|
|
|
|
|
|
|
|
10 |
|
|
|
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 |
|
|
|
|
|
|
|
Duality in Networks; Shortest Path Problem
Sec. 7.6, 7.9
HW 7 Due |
|
|
|
|
|
|
|
|
|
|
|
12 |
|
|
|
In-Class Quiz (covers up to Sec. 7.5) |
|
|
|
Auction Algorithm
Sec. 7.8 |
|
|
|
|
|
|
|
|
|
|
|
13 |
|
|
|
Integer Programming Formulations
Sec. 101-10.2
HW 8 Due |
|
|
|
Cutting Plane Methods
Branch & Bound
Sec. 11.1-11.2 |
|
|
|
|
|
|
|
|
|
|
|
14 |
|
|
|
Integer Programming Duality;
Lagrangean Relaxation
Sec. 11.4 |
|
|
|
Integer Programming Techniques
Sec. 11.3, 11.5, 11.6
HW 9 Due |
|
|
|
|
|
|
|
|
|
|
|
15 |
|
|
|
Introduction to NP-Completeness
Sec. 11.8 |
|
|
|
In-Class Quiz |
|
|
|
|
|