Back to Search
Start Over
A 3-Slope Theorem for the infinite relaxation in the plane
- Source :
- Mathematical Programming. 142:83-105
- Publication Year :
- 2012
- Publisher :
- Springer Science and Business Media LLC, 2012.
-
Abstract
- In this paper we consider the infinite relaxation of the corner polyhedron with 2 rows. For the 1-row case, Gomory and Johnson proved in their seminal paper a sufficient condition for a minimal function to be extreme, the celebrated 2-Slope Theorem. Despite increased interest in understanding the multiple row setting, no generalization of this theorem was known for this case. We present an extension of the 2-Slope Theorem for the case of 2 rows by showing that minimal 3-slope functions satisfying an additional regularity condition are facets (and hence extreme). Moreover, we show that this regularity condition is necessary, unveiling a structure which is only present in the multi-row setting.
Details
- ISSN :
- 14364646 and 00255610
- Volume :
- 142
- Database :
- OpenAIRE
- Journal :
- Mathematical Programming
- Accession number :
- edsair.doi...........e133045a8fa2ad87f865fdf6da236f0d