Skip to main content

IE 716: Integer Programming: Theory and Computations

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.