Graduate course in linear optimization

Key words:

The geometry of linear optimization, the simplex method, duality, revised simplex, dual simplex, parametric LP, sensitivity analysis, degeneracy, pivoting rules and modern implementations of the simplex method, the simplex method for upper bounded variables, decomposition principle, primal-dual algorithm, complexity, ellipsoid method, interior point methods, iterative methods for linear inequalities and LP, vector optima

Credits:

12 hp in the PhD program

Literature:

K G Murty: Linear Programming (Wiley, 1983) (main course book, [M])
C H Papadimitriou & K Steiglitz: Combinatorial Optimization (Prentice Hall, 1982) (primal-dual algorithm, [PS])
R J Vanderbei: Linear Programming (Springer, 2008) (interior point methods, [V])

A few selected articles on modern LP theory and methodology are also included

Examination:

Exercises, oral examination; a project can be done for further credits.

Reading list by topic:

M, Chapter 1 (Formulation of Linear Programs)
Exercises: 1, 5, 8-11, 16, 20, 26, 29, 34, 36-37, 39, 45, 47
M, Chapter 2 (The Simplex Method)
Exercises: 1-5, 24-25, 27-30, 32-42
M, Chapter 3 (The Geometry of the Simplex Method)
Exercises: 1-9, 11, 14-15, 17-18, 22, 25-28, 30, 33, 36, 38, 40, 42-44, 49, 55-56, 58, 75 (1-140)
Topics for oral exam: The Representation Theorem; Theorems 3.1, 3.2, 3.3, 3.6, 3.7 (with Corollaries); Faces and Facets; The requirement space; Read about "external pivoting" after reading 3.15; The Fourier-Motzkin elimination method (Section 3.17); Equivalent LPs (Section 3.18)
M, Chapter 4 (Duality in Linear Programming)
Exercises: 1, 6, 8-18, 24, 26-27, 33-34, 38, 43, 48, 52, 55 (1-52)
Topics for oral exam: Weak and strong duality (Theorems 4.3 and 4.5); Complementarity (Theorem 4.7); Saddle-point property (Section 4.6.2); Farkas' Lemma and variants (Theorems 4.9, 4.10, 4.11), alternative proof of Farkas' Lemma using the Separation Theorem, relations to strong duality; Uniqueness characterizations (Section 4.7)
Additional topic: Nonlinear perturbations of linear programs [see also Section 4.8] [Mangasarian & Meyer, "Nonlinear perturbation of linear programs", SIAM J Control Optim, 1979; Robinson, "Local structure of feasible sets in nonlinear programming, Part II: Nondegeneracy", Math Programming Study 22, 1984]
V, Section 10.5 (Strict complementarity)
Exercise: 4
M, Chapter 5 (Revised (Primal) Simplex Method)
Exercises: 1b-c, 2-3, 6, 8
M, Chapter 7 (Numerically Stable Forms of the Simplex Method)
Additional topics: Modern simplex methods (starting bases, pivoting rules, etc.) [Kennington & Mohamed, "An efficient dual simplex optimizer for generalized networks", in R. Barr, R. Helgason, and J. Kennington, editors, Interfaces in Computer Science and Operations Research, pages 153-182. Kluwer Academic Publishers, Norwell, MA 02061, 1997, 147-62; Maros, "A general pricing scheme for the simplex method", Annals of OR, 124, 2003, 193-203]
Topics for oral exam: [to be chosen]
M, Chapter 6 (The Dual Simplex Method)
Exercises: 1-2, 4-6, 10
Topics for oral exam: Equivalence between the primal and dual simplex methods (Section 6.6)
PS, Chapters 5-7 (Primal-dual algorithm)
M, Chapter 8 (Parametric Linear Programs)
Exercises: 2-3, 5, 8, 10, 11, 12a-c, 13, 16, 18
Topics for oral exam: Properties of the optimal value and solution (Theorems 8.1, 8.2, 8.3, 8.4, 8.5, 8.7, 8.9, 8.10, 8.11, 8.12, 8.13, 8.14, 8.15, 8.16)
M, Chapter 9 (Sensitivity Analysis)
Exercises: 6-7, 10, 12, 14, 18, 20, 23, 25
M, Chapter 10 (Degeneracy in Linear Programming)
Exercises: 1, 2, 4, 6, 7, 15
Topics for oral exam: Basis paths (Theorem 10.3); Bland's rule (Theorem 10.7)
M, Chapter 11 (Bounded-Variable Linear Programs)
Exercises: 1-3a, 7, 12
Topics for oral exam: GUB constraints (Section 11.7)
M, Chapter 12 (The Decomposition Principle of Linear Programming)
Additional topic: Dantzig-Wolfe decomposition [Vanderbeck & Savelsbergh, "A generic view of Dantzig-Wolfe decomposition in mixed integer programming", Oper Res Letters, 34, 2006]
Topics for oral exam: Convergence requirements
M, Chapter 14 (Computational Complexity of the Simplex Algorithm)
Topics for oral exam: Exercises 14.5 and 14.11
M, Chapter 15 [orientation] (The Ellipsoid Method)
V, Part 3 (Interior point methods for LP)
Exercises: 16.2, 16.3, 17.3, 17.7, 20.1, 21.3
Topics for oral exam: Convergence analyses
M, Chapter 16 (Iterative Methods for Linear Inequalities and Linear Programs)
Topics for oral exam: Relations to subgradient methods
M, Chapter 17 [orientation] (Vector Minima)

Project (for further credits):

To be determined together with the student. It could for example be in the form of an implementation of a simplex method where comparisons are made between strategic choices within the method, or a special adaptation of it to a structured problem. Theoretical projects are also possible.