Carnegie Mellon University

Integer Programming

Course Number: 47830

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.


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


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