On Families of Split Cuts that Can Be Generated Efficiently

Split cuts represent the most widely used class of cutting planes currently employed by state-of-the-art branch-and-cut solvers for mixed integer linear programming. Rank-1 cuts often have better numerical properties than higher rank cuts. In this paper, we study several heuristics to generate new families of strong rank-1 split cuts, by considering integer linear combinations of the rows of the simplex tableau, and deriving the corresponding mixed-integer Gomory cuts. In particular, we propose several cut generation algorithms that share the following aims: reducing the number of nonzeroes, obtaining small coefficients, generating orthogonal cuts. A key idea is that of selecting a subset of the variables, and trying to generate a cut which cuts deeply on those variables. We show that variables with small reduced cost are good candidates for this purpose, yielding cuts that close a larger integrality gap. On a set of test instances where standard split cut generators close on average 28.8 % of the integrality gap in the first pass, we can close 35.3 % by investing 10 times as much cut generation time. Incorporating our new split cuts into a branch-and-cut algorithm yields an improvement in the overall performance: except on very easy instances