Minimal inequalities for an infinite relaxation of integer programs

DOI10.1137/090756375MaRDI QIDQ3084218zbMATH OpenOpenAlexFDO

Authors Amitabh Basu, Michele Conforti, Gérard Cornuéjols, Giacomo Zambelli

Publication date 15 March 2011

Published in SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1701.06540

zbMATH Keywords

integer programmingcutting planesmaximal lattice-free convex sets

Mathematics Subject Classification ID

Lattices and convex bodies in (n) dimensions (aspects of discrete geometry) (52C07) Mixed integer programming (90C11)

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'asz 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.

Recommendations

• Maximal lattice-free convex sets in linear subspaces
• Minimal valid inequalities for integer constraints
• On maximal S-free convex sets
• Maximal lattice-free polyhedra: finiteness and an explicit description in dimension three
• A geometric perspective on lifting

Cited in

(34)

• On maximal S-free convex sets
• Unique lifting of integer variables in minimal inequalities
• Nonunique lifting of integer variables in minimal inequalities
• On the practical strength of two-row tableau cuts
• Maximal quadratic-free sets
• Maximal quadratic-free sets
• Maximal S-free convex sets and the Helly number
• Composite lifting of group inequalities and an application to two-row mixing inequalities
• Strengthening lattice-free cuts using non-negativity
• Outer-product-free sets for polynomial optimization and oracle-based cuts
• Approximation of corner polyhedra with families of intersection cuts
• A characterization of maximal homogeneous-quadratic-free sets
• Minimal valid inequalities for integer constraints
• Maximal lattice-free convex sets in linear subspaces
• Equivariant perturbation in Gomory and Johnson's infinite group problem. I: The one-dimensional case
• Cut-generating functions and S-free sets
• On sublinear inequalities for mixed integer conic programs
• The strength of multi-row models
• Sufficiency of cut-generating functions
• Geoffrion's theorem beyond finiteness and rationality
• Operations that preserve the covering property of the lifting region
• On the implementation and strengthening of intersection cuts for QCQPs
• A geometric approach to cut-generating functions
• Relaxations of mixed integer sets from lattice-free polyhedra
• Relaxations of mixed integer sets from lattice-free polyhedra
• Two dimensional lattice-free cuts and asymmetric disjunctions for mixed-integer polyhedra
• Computational experiments with cross and crooked cross cuts
• Intersection cuts for single row corner relaxations
• On the implementation and strengthening of intersection cuts for QCQPs
• Intersection Disjunctions for Reverse Convex Sets
• Maximal lattice-free polyhedra: finiteness and an explicit description in dimension three
• Towards a characterization of maximal quadratic-free sets
• An algorithm for the separation of two-row cuts
• Intersection cuts -- standard versus restricted

This page was built for publication: Minimal inequalities for an infinite relaxation of integer programs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3084218)