Prerequisite: IE 609 or Equivalent or Instructor's consent
Contents
1. Effective modelling in integer programming: Modelling with integer variables: correct formulations; optimality, relaxation, bounds, search, branch-and-bound; choices in modelling: strong formulations, extended formulations, preprocessing of formulations.
2. Polyhedra and integer programming: Describing polyhedra with extreme points and extreme rays; affine independence, dimensions and faces of polyhedra; facets of polyhedra; projection of polyhedra onto subspaces; the polar of polyhedra; equivalence of separation and optimization for polyhedra; connections between polyhedra and integer programming.
3. Relaxation and decomposition methods for large{scale problems: Lagrangian relaxation and subgradient optimization; Dantzig � Wolfe decomposition and column generation; Benders decomposition.
4. Cutting plane methods for unstructured problems: Gomory and Chv�tal-Gomory cuts; Integer and mixed-integer rounding; Disjunctive cuts: lift-and-project cuts, split cuts, intersection cuts; the group approach to integer programming.
5. Cutting plane methods for structured problems: Valid inequalities for set packing and 0�1 knapsack problems and their separation; clique and odd-cycle inequalities; cover inequalities; sequential and sequence-independent lifting (with examples in the context of cover inequalities); applications in airline crew scheduling, production lot-sizing, facility location, and network design.
References
- G. L. Nemhauser and L. A. Wolsey, Integer and Combinatorial Optimization, Wiley, 1999.
- L. A. Wolsey, Integer Programming, Wiley, 1998
- A. Schrijver, Theory of Linear and Integer Programming, Wiley, 1998.
- Y. Pochet and L.A. Wolsey, Production Planning by Mixed Integer Programming, Springer, 2006.
- D. Bertsimas and R. Weismantel, Optimization over Integers, Dynamics Ideas, 2005.
- Several journal papers that exemplify the progress of integer programming over the last two decades.