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, where our procedure is too slow to bring advantage, on average we can save 23% computing time on instances which are solved, and close more integrality gap on unsolved instances in a fixed amount of time.