Cut-Generating Functions for Integer Variables

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.