everything.study
I SY E 728

INTEGER OPTIMIZATION

3 credits.

Introduces optimization problems over integers, and surveys the theory behind the algorithms used in state-of-the-art methods for solving such problems. Special attention is given to the polyhedral formulations of these problems, and to their algebraic and geometric properties. Applicability of Integer Optimization is highlighted with applications in combinatorial optimization. Key topics include: formulations, relaxations, polyhedral theory, cutting planes, decomposition, enumeration. Students are strongly encouraged to have knowledge of Linear Programming (e.g., MATH/COMP SCI/I SY E/STAT 525 ), including algorithms, duality and polyhedral theory.

Topics

Topics explicitly listed in official catalogue description

Prerequisites & course information

Requisites: Graduate/professional standing Course Designation: Grad 50% - Counts toward 50% graduate coursework requirement Repeatable for Credit: No Last Taught: Spring 2026 Learning Outcomes: 1. Describe and explain the basics of polyhedral theory, which consists in the study of systems of linear inequalities both from an algebraic and a geometric point of view Audience: Graduate 2. Define perfect formulations and identify what properties are desirable in an integer programming formulation of a problem Audience: Graduate 3. Explain how valid inequalities can be used as cutting planes to strengthen integer programming formulations Audience: Graduate Learning Outcomes: 1. Describe and explain the basics of polyhedral theory, which consists in the study of systems of linear inequalities both from an algebraic and a geometric point of view Audience: Graduate 2. Define perfect formulations and identify what properties are desirable in an integer programming formulation of a problem Audience: Graduate 3. Explain how valid inequalities can be used as cutting planes to strengthen integer programming formulations Audience: Graduate

Sources
Catalogue variants