Minimal inequalities for an infinite relaxation of integer programs

Abstract

We show that maximal $S$-free convex sets are polyhedra when $S$ is the set of integral points in some rational polyhedron of ${\mathbb{R}}^n$. This result extends a theorem of Lovász characterizing maximal lattice-free convex sets. Our theorem has implications in integer programming. In particular, we show that maximal $S$-free convex sets are in one-to-one correspondence with minimal inequalities.

Cited by in corpus (2)

• A geometric approach to cut-generating functions
• Unique lifting of integer variables in minimal inequalities