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...

Full description

Saved in:
Bibliographic Details
Published in:INFORMS journal on computing 2014-09, Vol.26 (4), p.780-797
Main Authors: Dash, Sanjeeb, Gunluk, Oktay, Vielma, Juan Pablo
Format: Article
Language:English
Subjects:
Computational mathematics
cutting planes
Cutting stock problem
elementary closures
Engineering research
Integer programming
Methods
mixed integer programming
Relaxation methods (Mathematics)
Studies
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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].
ISSN:1091-9856
1526-5528
1091-9856
DOI:10.1287/ijoc.2014.0598