Academics
  /  
Courses
  /  
Descriptions
IEMS 457: Integer Programming


VIEW ALL COURSE TIMES AND SESSIONS

Prerequisites

IE 450-1 or equivalent

Description

Methods for NP-hard discrete optimization problems, including general methods like branch-and-bound and cutting planes, as well as special purpose branch-and-cut methods. 

Learning Objectives

Students will be able to develop good models for optimization problems that involve discrete variables and combinatorial constraints. They will learn the foundations of integer and combinatorial optimization, and apply polyhedral theory to design effective algorithms to solve large-scale integer programs in practice. They will be able to implement the algorithms designed using modeling and optimization software such as AMPL, CPLEX and Gurobi.

Topics

  • Strength of formulations
  • Polyhedra, facets, convex hull, polarity
  • Optimization and separation
  • Relaxations, duality
  • Total unimodularity, total dual integrity
  • Theory of valid inequalities, lifting
  • Branch-and-bound, branch-and-cut

Materials

Integer and Combinatorial Optimization, by G. L. Nemhauser and L. A. Wolsey, John Wiley, 1999

Prerequisites

IE 450-1 or equivalent