Carnegie Mellon University

Integer Programming

Course Number: 47830

This is a graduate-level course in integer programming.

The material from 47-834 Linear Programming is a prerequisite.

The following topics will be covered:

  • Scope and applicability of integer programming.
  • Formulations.
  • The knapsack problem, covering and packing, the traveling salesman problem.
  • Complexity and problem reductions.
  • Solutions methods: enumeration and convexification. Branch and bound, branch and cut.
  • Combinatorial optimization.
  • Polyhedral theory.
  • Cutting planes.
  • Gomory-Chvátal theory.
  • The mixed integer Gomory cut.
  • Intersection cuts and the corner polyhedron.
  • Disjunctive programming: optimization over unions of polyhedra.
  • Higher dimensional representations.
  • Lift-and-project.
  • Valid inequalities for structured integer programs.
  • Minimal cover inequalities.
  • Lifting functions.
  • Superadditivity.
  • Sequence independent liftings.
  • Flow cover inequalities. Reformulations and relaxations.
  • Lagrangian relaxation.
  • Dantzig-Wolfe reformulation.
  • Benders decomposition.


Degree: PhD
Concentration: Operations Research
Academic Year: 2023-2024
Semester(s): Mini 3
Required/Elective: Elective
Units: 6


Lecture: 160min/wk