47-830 Integer Programming

6 units, Carnegie Mellon University

This is a graduate-level course in integer programming. 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.

Prerequisites: none listed

Offered: Spring 2027, Spring 2026

Courseweave needs JavaScript to show sections, workloads and planning tools.