Abstract | ||
---|---|---|
We prove that any minimal valid function for the k-dimensional infinite group relaxation that is continuous piecewise linear with at most k + 1 slopes and does not factor through a linear map with nontrivial kernel is extreme. This generalizes a theorem of Gomory and Johnson for k = 1 and of Cornuejols and Molinaro for k = 2. |
Year | DOI | Venue |
---|---|---|
2013 | 10.1137/110848608 | SIAM JOURNAL ON OPTIMIZATION |
Keywords | Field | DocType |
integer programming,cutting planes,corner polyhedron,group relaxation,subadditive functions | Kernel (linear algebra),Discrete mathematics,Mathematical optimization,Infinite group,Integer programming,Linear map,Piecewise linear function,Mathematics | Journal |
Volume | Issue | ISSN |
23 | 2 | 1052-6234 |
Citations | PageRank | References |
14 | 0.75 | 14 |
Authors | ||
4 |
Name | Order | Citations | PageRank |
---|---|---|---|
Amitabh Basu | 1 | 331 | 27.36 |
Robert Hildebrand | 2 | 69 | 7.82 |
Matthias KöPpe | 3 | 191 | 20.95 |
Marco Molinaro | 4 | 164 | 18.75 |