Valid Inequalities for Mixed Integer Linear Programs

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.

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Jul 01, 2006
Accession Number
AD1021100

Entities

People

  • Gérard Cornuéjols

Organizations

  • Carnegie Mellon University

Tags

Communities of Interest

  • Air Platforms
  • C4I

DTIC Thesaurus Topics

  • Algorithms
  • Coefficients
  • Computer Programming
  • Convex Sets
  • Electronic Mail
  • Equations
  • Evolutionary Algorithms
  • Inclusions
  • Inequalities
  • Integer Programming
  • Linear Programming
  • Linear Systems
  • Mathematical Programming
  • Nonlinear Systems
  • Polynomials
  • Theorems

Readers

  • Operations Research
  • Theoretical Analysis.