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