Cut-Generating Functions for Integer Variables
研究了整数线性规划中不放松非负约束的割生成函数，推广了Gomory和Johnson关于极小割生成函数的经典结果，并证明了极端割生成函数的2-斜率定理。
For an integer linear program, Gomory’s corner relaxation is obtained by ignoring the nonnegativity of the basic variables in a tableau formulation. In this paper, we do not relax these nonnegativity constraints. We generalize a classical result of Gomory and Johnson characterizing minimal cut-generating functions in terms of subadditivity, symmetry, and periodicity. Our result is based on the notion of generalized symmetry condition. We also prove a 2-slope theorem for extreme cut-generating functions in our setting, in the spirit of the 2-slope theorem of Gomory and Johnson.