Pivot-and-reduce cuts: An approach for improving Gomory mixed-integer cuts

Gomory mixed-integer cuts are of crucial importance in solving large-scale mixed-integer linear programs. Recently, there has been considerable research particularly on the strengthening of these cuts. We present a new heuristic algorithm which aims at improving Gomory mixed-integer cuts. Our approach is related to the reduce-and-split cuts. These cuts are based on an algorithm which tries to reduce the coefficients of the continuous variables by forming integer linear combinations of simplex tableau rows. Our algorithm is designed to achieve the same result by performing pivots on the simplex tableau. We give a detailed description of the algorithm and its implementation. Finally, we report on computational results with our approach and analyze its performance. The results indicate that our algorithm can enhance the performance of the Gomory mixed-integer cuts.

► We propose a pivoting algorithm for improving the performance of the Gomory mixed-integer (GMI) cuts. ► The algorithm reduces the size of the coefficients of the continuous variables in the GMI cuts. ► We show that the algorithm successfully enhances the quality of the GMI cuts in terms of the distance cut off. ► In our experiments the improved cuts lead to a decrease in the running times and number of branching nodes explored.