Chvatal-Gomory-tier cuts for general integer programs

In this paper, we introduce a new class of cutting planes called Chvatal-Gomory (CG)-tier cuts. These cuts are predicated on a scaling parameter d and an integer tier-level parameter p, where 1⩽p⩽d. The cut generation process begins by scaling a given source row by d and deriving a standard Chvatal-Gomory (CG) cut at level one, but then repeats this process a total of p times, each time using the previous cut as a source row along with a scaling parameter value that is successively decremented by one. We derive a closed-form expression for this cut depending on the parameters p and d, so that the resulting CG-tier cut can be composed directly without actually implementing the foregoing recursive process. Furthermore, we study the variational properties of the cut coefficients as a function of the parameters d and p in order to facilitate a prescription of these parameter values for constructing strong CG-tier cuts that tighten the representation along specified desired dimensions. Several examples are provided to offer insights into the strength and nature of these cuts, including an illustration that these cuts can produce strong valid inequalities that are not obtainable via rank-one CG cuts. This paper focuses on the underlying derivation and structure of this class of CG-tier cuts; a follow-on study will address related implementation and computational issues.