Practical strategies for generating rank-1 split cuts in mixed-integer linear programming

  • In this paper we propose practical strategies for generating split cuts, by considering integer linear combinations of the rows of the optimal simplex tableau, and deriving the corresponding Gomory mixed-integer cuts; potentially, we can generate a huge number of cuts. A key idea is to select subsets of variables, and cut deeply in the space of these variables. We show that variables with small reduced cost are good candidates for this purpose, yielding cuts that close a larger integrality gap. An extensive computational evaluation of these cuts points to the following two conclusions. The first is that our rank-1 cuts improve significantly on existing split cut generators (Gomory cuts from single tableau rows, MIR, Reduce-and-Split, Liftand-Project, Flow and Knapsack cover): onMIPLIB instances, these generators close 24% of the integrality gap on average; adding our cuts yields an additional 5%. The second conclusion is that, when incorporated in a Branch-and-Cut framework, these new cuts can improve computing time on difficult instances.

Download full text files

Export metadata

Additional Services

Share in Twitter Search Google Scholar
Metadaten
Author:Gerard Cornuéjols, Giacomo Nannicini
DOI:https://doi.org/10.1007/s12532-011-0028-6
ISSN:1867-2949
Parent Title (English):Mathematical Programming Computation
Publisher:Springer Science and Business Media LLC
Document Type:Article
Language:English
Year of Completion:2011
Tag:Software; Theoretical Computer Science
Volume:3
Issue:4
Page Number:38
First Page:281
Last Page:318
Mathematical Programming Computation :MPC 2011 - Issue 4
Verstanden ✔
Diese Webseite verwendet technisch erforderliche Session-Cookies. Durch die weitere Nutzung der Webseite stimmen Sie diesem zu. Unsere Datenschutzerklärung finden Sie hier.