Optimization Online


A probabilistic analysis of the strength of the split and triangle closures

Amitabh Basu(abasu***at***math.ucdavis.edu)
Gerard Cornuejols(gc0v***at***andrew.cmu.edu)
Marco Molinaro(molinaro***at***cmu.edu)

Abstract: In this paper we consider a relaxation of the corner polyhedron introduced by Andersen et al., which we denote by RCP. We study the relative strength of the split and triangle cuts of RCP's. Basu et al. showed examples where the split closure can be arbitrarily worse than the triangle closure under a `worst-cost' type of measure. However, despite experiments carried out by several authors, the usefulness of triangle cuts in practice has fallen short of its theoretical strength. In order to understand this issue, we consider two types of measures between the closures: the `worst-cost' one mentioned above, where we look at the weakest direction of the split closure, and the `average-cost' measure which takes an average over all directions. Moreover, we consider a natural model for generating random RCP's. Our first result is that, under the worst-cost measure, a random RCP has a weak split closure with reasonable probability. This shows that the bad examples given by Basu et al. are not pathological cases. However, when we consider the average-cost measure, with high probability both split and triangle closures obtain a very good approximation of the RCP. The above result holds even if we replace split cuts by the simple split or Gomory cuts. This gives an indication that split/Gomory cuts are indeed as useful as triangle cuts.

Keywords: cutting planes, split cuts, intersection cuts, probabilistic analysis

Category 1: Integer Programming (Cutting Plane Approaches )

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


Download: [Postscript]

Entry Submitted: 10/21/2010
Entry Accepted: 10/22/2010
Entry Last Modified: 10/21/2010

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 Programming Society