Minimal Valid Inequalities for Integer Constraints

Abstract

In this paper, we consider a semi-infinite relaxation of mixed-integer linear programs. We show that minimal valid inequalities for this relaxation correspond to maximal lattice-free convex sets, and that they arise from nonnegative, piecewise linear, positively homogeneous, convex functions.

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Aug 01, 2008
Accession Number
AD1021086

Entities

People

  • Gérard Cornuéjols
  • Valentin Borozan

Organizations

  • Carnegie Mellon University

Tags

Communities of Interest

  • Air Platforms

DTIC Thesaurus Topics

  • Boundaries
  • Computer Programming
  • Convex Sets
  • Equations
  • Homogeneity
  • Inclusions
  • Inequalities
  • Integer Programming
  • Integrals
  • Linear Programming
  • Theorems

Fields of Study

  • Mathematics

Readers

  • Operations Research