A (k+1)-Slope Theorem for the k-Dimensional Infinite Group Relaxation
Preprint
Abstract
We prove that any minimal valid function for the k-dimensional infinite group relaxation that is piecewise linear with at most k+1 slopes and does not factor through a linear map with non-trivial kernel is extreme. This generalizes a theorem of Gomory and Johnson for k=1, and Cornuejols and Molinaro for k=2.Keywords
All Related Versions
This publication has 9 references indexed in Scilit:
- Unique Minimal Liftings for Simplicial PolytopesMathematics of Operations Research, 2012
- Corner polyhedron and intersection cutsSurveys in Operations Research and Management Science, 2011
- A counterexample to a conjecture of Gomory and JohnsonMathematical Programming, 2010
- Maximal Lattice-Free Convex Sets in Linear SubspacesMathematics of Operations Research, 2010
- Mingling: mixed-integer rounding with boundsMathematical Programming, 2009
- Valid inequalities based on simple mixed-integer setsMathematical Programming, 2005
- T-space and cutting planesMathematical Programming, 2003
- Some continuous functions related to corner polyhedra, IIMathematical Programming, 1972
- Some polyhedra related to combinatorial problemsLinear Algebra and its Applications, 1969