This Article Full Text (PDF) References Alert me when this article is cited Alert me if a correction is posted Services Email this article to a friend Similar articles in this journal Alert me to new issues of the journal Download to citation manager Google Scholar Articles by Borozan, V. Articles by Cornuéjols, G.

Minimal Valid Inequalities for Integer Constraints

LIF, Faculté des Sciences de Luminy, Université de Marseille, 13288 Marseille, France
Tepper School of Business, Carnegie Mellon University, Pittsburgh, Pennsylvania 15213, and LIF, Faculté des Sciences de Luminy, Université de Marseille, 13288 Marseille, France
borozan.valentin{at}gmail.com
gc0v{at}andrew.cmu.edu, http://integer.tepper.cmu.edu

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.

Key Words: integer programming; lattice-free convex set; corner polyhedron
History: Received: July 18, 2007; revision received: August 26, 2008;