IE 403: Integer Programming

Instructor:

Nick Sahinidis (nikos@uiuc.edu)

Course Objectives:

Offer an in depth study of the general theory and methods of Integer Programming and Combinatorial Optimization. Will study modelling techniques, applications, algorithms, software.

Text:

Nemhauser and Wolsey: "Integer and Combinatorial Optimization," Wiley, 1988. Extensive additional material from research papers will be provided in class.

A General Bibliography on Optimization is available here

Credit:

1 unit. Course grade will be based on homework (40%), midterm (15%), take-home final exam (15%), paper presentation (15%) and computer project (15%).

Topics covered:

  1. Preliminaries (2 lectures):
    • Introduction
    • Modelling with Integer Variables.
  2. Foundations (6 lectures):
    • Computational Complexity
    • Linear Programming
    • Graph Theory
    • Total Unimodularity
    • Polyhedral Theory.
  3. General Solution Methods (8 lectures)
    • Cutting Planes
    • Branch and Bound
    • Implicit Enumeration
    • Benders Decomposition
    • Lagrangian Relaxation
  4. Special structures (7 lectures):
    • Knapsack Problem
    • Lot Sizing and Variable Disaggregation
    • Uncapacitated Facility Location and Constraint Disaggregation
    • Travelling Salesman
    • Fixed charge
    • Set Covering/Packing/Partitioning
    • Mixed-Integer Nonlinear Programming
  5. Projects (3 lectures)
    • Integer Programming Software Packages (BARON, CPLEX, GAMS, OSL)
    • Paper presentations

To Sigma Optimization Teaching Activities