Course Page

Integer Programming

Course Number:

47830


Faculty

Gérard Cornuéjols, gc0v@andrew.cmu.edu


Program

PHD


Concentrations

Operations Research or Statistics


Course Description

Integer programming: scope and applicability. Formulations. Combinatorial optimization. Relaxations. Linear programs with integer solutions. Outline of solutions methods: enumeration and convexification. Complexity and problem reductions. Optimization and separation. Branch and bound, implicit enumeration. Cutting planes. Gomory-Chvátal theory. The mixed integer Gomory cut. The problem of convergence and stalling. Disjunctive programming: optimization over unions of polyhedra. Higher dimensional representations. Disjunctive cuts. Lift-and-project.

Format

Lecture: 100min/wk and Recitation: 50min/wk


Pre-requisites

None