Computational Experiments with Cross and Crooked Cross Cuts
In this paper, we study whether cuts obtained from two simplex tableau rows at a time can strengthen the bounds obtained by Gomory mixed-integer (GMI) cuts based on single tableau rows. We also study whether cross and crooked cross cuts, which generalize split cuts, can be separated in an effective...
| Main Authors: | , , |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | en_US |
| Published: |
Institute for Operations Research and the Management Sciences (INFORMS)
2015
|
| Online Access: | http://hdl.handle.net/1721.1/99206 https://orcid.org/0000-0003-4335-7248 |
| _version_ | 1811074055264010240 |
|---|---|
| author | Dash, Sanjeeb Gunluk, Oktay Vielma, Juan Pablo |
| author2 | Sloan School of Management |
| author_facet | Sloan School of Management Dash, Sanjeeb Gunluk, Oktay Vielma, Juan Pablo |
| author_sort | Dash, Sanjeeb |
| collection | MIT |
| description | In this paper, we study whether cuts obtained from two simplex tableau rows at a time can strengthen the bounds obtained by Gomory mixed-integer (GMI) cuts based on single tableau rows. We also study whether cross and crooked cross cuts, which generalize split cuts, can be separated in an effective manner for practical mixed-integer programs (MIPs) and can yield a nontrivial improvement over the bounds obtained by split cuts. We give positive answers to both these questions for MIPLIB 3.0 problems. Cross cuts are a special case of the t-branch split cuts studied by Li and Richard [Li Y, Richard J-PP (2008) Cook, Kannan and Schrijvers's example revisited. Discrete Optim. 5:724–734]. Split cuts are 1-branch split cuts, and cross cuts are 2-branch split cuts. Crooked cross cuts were introduced by Dash, Günlük, and Lodi [Dash S, Günlük O, Lodi A (2010) MIR closures of polyhedral sets. Math Programming 121:33–60] and were shown to dominate cross cuts by Dash, Günlük, and Molinaro [Dash S, Günlük O, Molinaro M (2012b) On the relative strength of different generalizations of split cuts. IBM Technical Report RC25326, IBM, Yorktown Heights, NY]. |
| first_indexed | 2024-09-23T09:42:25Z |
| format | Article |
| id | mit-1721.1/99206 |
| institution | Massachusetts Institute of Technology |
| language | en_US |
| last_indexed | 2024-09-23T09:42:25Z |
| publishDate | 2015 |
| publisher | Institute for Operations Research and the Management Sciences (INFORMS) |
| record_format | dspace |
| spelling | mit-1721.1/992062022-09-26T13:16:03Z Computational Experiments with Cross and Crooked Cross Cuts Dash, Sanjeeb Gunluk, Oktay Vielma, Juan Pablo Sloan School of Management Vielma, Juan Pablo In this paper, we study whether cuts obtained from two simplex tableau rows at a time can strengthen the bounds obtained by Gomory mixed-integer (GMI) cuts based on single tableau rows. We also study whether cross and crooked cross cuts, which generalize split cuts, can be separated in an effective manner for practical mixed-integer programs (MIPs) and can yield a nontrivial improvement over the bounds obtained by split cuts. We give positive answers to both these questions for MIPLIB 3.0 problems. Cross cuts are a special case of the t-branch split cuts studied by Li and Richard [Li Y, Richard J-PP (2008) Cook, Kannan and Schrijvers's example revisited. Discrete Optim. 5:724–734]. Split cuts are 1-branch split cuts, and cross cuts are 2-branch split cuts. Crooked cross cuts were introduced by Dash, Günlük, and Lodi [Dash S, Günlük O, Lodi A (2010) MIR closures of polyhedral sets. Math Programming 121:33–60] and were shown to dominate cross cuts by Dash, Günlük, and Molinaro [Dash S, Günlük O, Molinaro M (2012b) On the relative strength of different generalizations of split cuts. IBM Technical Report RC25326, IBM, Yorktown Heights, NY]. United States. Office of Naval Research (Grant N000141110724) 2015-10-08T13:49:41Z 2015-10-08T13:49:41Z 2014-06 2013-03 Article http://purl.org/eprint/type/JournalArticle 1091-9856 1526-5528 http://hdl.handle.net/1721.1/99206 Dash, Sanjeeb, Oktay Gunluk, and Juan Pablo Vielma. “Computational Experiments with Cross and Crooked Cross Cuts.” INFORMS Journal on Computing 26, no. 4 (November 2014): 780–797. https://orcid.org/0000-0003-4335-7248 en_US http://dx.doi.org/10.1287/ijoc.2014.0598 INFORMS Journal on Computing Creative Commons Attribution-Noncommercial-Share Alike http://creativecommons.org/licenses/by-nc-sa/4.0/ application/pdf Institute for Operations Research and the Management Sciences (INFORMS) MIT web domain |
| spellingShingle | Dash, Sanjeeb Gunluk, Oktay Vielma, Juan Pablo Computational Experiments with Cross and Crooked Cross Cuts |
| title | Computational Experiments with Cross and Crooked Cross Cuts |
| title_full | Computational Experiments with Cross and Crooked Cross Cuts |
| title_fullStr | Computational Experiments with Cross and Crooked Cross Cuts |
| title_full_unstemmed | Computational Experiments with Cross and Crooked Cross Cuts |
| title_short | Computational Experiments with Cross and Crooked Cross Cuts |
| title_sort | computational experiments with cross and crooked cross cuts |
| url | http://hdl.handle.net/1721.1/99206 https://orcid.org/0000-0003-4335-7248 |
| work_keys_str_mv | AT dashsanjeeb computationalexperimentswithcrossandcrookedcrosscuts AT gunlukoktay computationalexperimentswithcrossandcrookedcrosscuts AT vielmajuanpablo computationalexperimentswithcrossandcrookedcrosscuts |