A (k+1)-SLOPE THEOREM FOR THE k-DIMENSIONAL INFINITE GROUP RELAXATION

作者：Basu Amitabh^*; Hildebrand Robert; Koeppe Matthias; Molinaro Marco

来源：SIAM Journal on Optimization, 2013, 23(2): 1021-1040.

DOI：10.1137/110848608

• integer programming
• cutting planes
• corner polyhedron
• group relaxation
• subadditive functions

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.

• 出版日期2013