Academic
Publications
On the relative strength of split, triangle and quadrilateral cuts

On the relative strength of split, triangle and quadrilateral cuts,10.1007/s10107-009-0281-x,Mathematical Programming,Amitabh Basu,Pierre Bonami,Gérar

On the relative strength of split, triangle and quadrilateral cuts   (Citations: 3)
BibTex | RIS | RefWorks Download
Integer programs defined by two equations with two free integer variables and nonnegative continuous variables have three types of nontrivial facets: split, triangle or quadrilateral inequalities. In this paper, we compare the strength of these three families of inequalities. In particular we study how well each family approximates the integer hull. We show that, in a well defined sense, triangle inequalities provide a good approximation of the integer hull. The same statement holds for quadrilateral inequalities. On the other hand, the approximation produced by split inequalities may be arbitrarily bad.
Journal: Mathematical Programming , vol. 126, no. 2, pp. 281-314, 2011
Cumulative Annual
View Publication
The following links allow you to view full publications. These links are maintained by other sources not affiliated with Microsoft Academic Search.
    • ...In [6] the authors showed a family of RCP’s whose split closure gets arbitrarily weaker than the triangle closure...
    • ...This generalizes the bad examples from [6] and shows that they are not as pathological as one could think...
    • ...Type 2 triangles (the same family which was considered in [6]) decreases with decreasing lattice width, on average...

    Amitabh Basuet al. A Probabilistic Analysis of the Strength of the Split and Triangle Clo...

Sort by: