Optimization Online


Computational Experiments with Cross and Crooked Cross Cuts

Sanjeeb Dash (sanjeebd***at***us.ibm.com)
Oktay Gunluk (gunluk***at***us.ibm.com)
Juan Pablo Vielma (jvielma***at***pitt.edu)

Abstract: In a recent paper, Dash, Dey and Gunluk (2010) showed that many families of inequalities for the two-row continuous group relaxation and variants of this relaxation are cross cuts or crooked cross cuts, both of which generalize split cuts. Li and Richard (2008) recently studied t-branch split cuts for mixed-integer programs for integers t >= 1. Split cuts are just 1-branch split cuts, and cross cuts are 2-branch split cuts. In this paper, we study whether cross and crooked cross cuts can be separated in an effective manner for practical MIPs, and can yield a non-trivial improvement over the bounds obtained by split cuts. We also study whether such cuts obtained from two simplex tableau rows at a time can strengthen the bounds obtained by GMI cuts based on single tableau rows. We give positive answers to both these questions for MIPLIB 3.0 problems.

Keywords: Mixed-integer programs, split cuts, crooked cross cuts, two-row cuts, continuous group relaxation

Category 1: Integer Programming ((Mixed) Integer Linear Programming )

Category 2: Integer Programming (Cutting Plane Approaches )


Download: [PDF]

Entry Submitted: 06/22/2011
Entry Accepted: 06/22/2011
Entry Last Modified: 06/22/2011

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society