Accession Number:

AD1021100

Title:

Valid Inequalities for Mixed Integer Linear Programs

Descriptive Note:

OSTP Journal Article

Corporate Author:

Carnegie Mellon University Pittsburgh United States

Personal Author(s):

Report Date:

2006-07-01

Pagination or Media Count:

41.0

Abstract:

This tutorial presents a theory of valid inequalities for mixed integer linear sets. It introduces the necessary tools from polyhedral theory and gives a geometric understanding of several classical families of valid inequalities such as lift-and-project cuts, Gomory mixed integer cuts, mixed integer rounding cuts, split cuts and intersection cuts, and it reveals the relationships between these families. The tutorial also discusses computational aspects of generating the cuts and their strength.

Subject Categories:

  • Operations Research

Distribution Statement:

APPROVED FOR PUBLIC RELEASE