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

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

0.00 Avg rating0 Votes
Article ID: iaor20116376
Volume: 214
Issue: 1
Start Page Number: 15
End Page Number: 26
Publication Date: Oct 2011
Journal: European Journal of Operational Research
Authors: , ,
Keywords: cutting plane algorithms
Abstract:

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.

Reviews

Required fields are marked *. Your email address will not be published.