  


A probabilistic analysis of the strength of the split and triangle closures
Amitabh Basu(abasumath.ucdavis.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 `worstcost' 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 `worstcost' one mentioned above, where we look at the weakest direction of the split closure, and the `averagecost' 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 worstcost 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 averagecost 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 ) Citation: Download: [Postscript] Entry Submitted: 10/21/2010 Modify/Update this entry  
Visitors  Authors  More about us  Links  
Subscribe, Unsubscribe Digest Archive Search, Browse the Repository

Submit Update Policies 
Coordinator's Board Classification Scheme Credits Give us feedback 
Optimization Journals, Sites, Societies  