Corner Polyhedron and Intersection Cuts

Abstract

Four decades ago, Gomory introduced the corner polyhedron as a relaxation of a mixed integer set in tableau form and Balas introduced intersection cuts for the corner polyhedron. A recent paper of Andersen, Louveaux, Weismantel and Wolsey has generated a renewed interest in the corner polyhedron and intersection cuts. We survey these two approaches and the recent developments in multi-row cuts. We stress the importance of maximal lattice-free convex sets and of the so-called infinite relaxation.

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Mar 01, 2011
Accession Number
ADA586444

Entities

People

  • Giacomo Zambelli
  • Gérard Cornuéjols
  • Michele Conforti

Organizations

  • Carnegie Mellon University

Tags

Communities of Interest

  • Air Platforms

DTIC Thesaurus Topics

  • Algebra
  • Boundaries
  • Computer Programming
  • Computer Science
  • Convex Sets
  • Equations
  • Evolutionary Algorithms
  • Geometry
  • Inequalities
  • Integer Programming
  • Integrals
  • Linear Programming
  • Mathematical Programming
  • Mathematics
  • Operations Research
  • Optimization
  • Political Science

Readers

  • Graph Algorithms and Convex Optimization.
  • Operations Research
  • Theoretical Analysis.