On the relative strength of split, triangle and quadrilateral cuts

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

On the relative strength of split, triangle and quadrilateral cuts

Full text

Pdf (504 KB)

Source

Symposium on Discrete Algorithms archive
Proceedings of the Nineteenth Annual ACM -SIAM Symposium on Discrete Algorithms table of contents

New York, New York

Pages 1220-1229

Year of Publication: 2009

Authors

Amitabh Basu	Carnegie Mellon University
Pierre Bonami	Université de Marseille, France
Gérard Cornuéjols	Carnegie Mellon University
François Margot	Carnegie Mellon University

Publisher

Society for Industrial and Applied Mathematics Philadelphia, PA, USA

Bibliometrics

Downloads (6 Weeks): 4, Downloads (12 Months): 33, Citation Count: 0

Additional Information:

abstract references index terms collaborative colleagues

Tools and Actions:	Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

ABSTRACT

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.

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	Kent Andersen , Quentin Louveaux , Robert Weismantel , Laurence A. Wolsey, Inequalities from Two Rows of a Simplex Tableau, Proceedings of the 12th international conference on Integer Programming and Combinatorial Optimization, June 25-27, 2007, Ithaca, NY, USA [doi>10.1007/978-3-540-72792-7_1]
	2	E. Balas, Intersection Cuts - A New Type of Cutting Planes for Integer Programming, Operations Research 19 (1971) 19--39.
	3	Egon Balas , Sebastián Ceria , Gérard Cornuéjols, A lift-and-project cutting plane algorithm for mixed 0-1 programs, Mathematical Programming: Series A and B, v.58 n.3, p.295-324, Feb. 25, 1993 [doi>10.1007/BF01581273]
	4	Egon Balas , Anureet Saxena, Optimizing over the split closure, Mathematical Programming: Series A and B, v.113 n.2, p.219-240, January 2008 [doi>10.1007/s10107-006-0049-5]
	5	V. Borozan and G. Cornuéjols, Minimal Valid Inequalities for Integer Constraints, technical report (July 2007), available at http://integer.tepper.cmu.edu/.
	6	W. Cook , R. Kannan , A. Schrijver, Chva´tal closures for mixed integer programming problems, Mathematical Programming: Series A and B, v.47 n.2, p.155-174, Jun. 1990 [doi>10.1007/BF01580858]
	7	G. Cornuéjols and F. Margot, On the Facets of Mixed Integer Programs with Two Integer Variables and Two Constraints, to appear in Mathematical Programming.
	8	H. Crowder, E. L. Johnson, M. Padberg, Solving Large-Scale Zero-One Linear Programming Problems, Operations Research 31 (1983) 803--834.
	9	Sanjeeb Dash , Oktay Günlük , Andrea Lodi, On the MIR Closure of Polyhedra, Proceedings of the 12th international conference on Integer Programming and Combinatorial Optimization, June 25-27, 2007, Ithaca, NY, USA [doi>10.1007/978-3-540-72792-7_26]
	10	S. S. Dey and L. A. Wolsey, Lifting Integer Variables in Minimal Inequalities Corresponding to Lattice-Free Triangles, IPCO 2008, Bertinoro, Italy (June 2008), Lecture Notes in Computer Science 5035, 463--476.
	11	D. Espinoza, Computing with multi-row Gomory cuts, IPCO 2008, Bertinoro, Italy (June 2008), Lecture Notes in Computer Science 5035, 214--224.
	12	Michel X. Goemans, Worst-case comparison of valid inequalities for the TSP, Mathematical Programming: Series A and B, v.69 n.2, p.335-349, Aug. 25, 1995
	13	R. E. Gomory, An Algorithm for Integer Solutions to Linear Programs, Recent Advances in Mathematical Programming, R. L. Graves and P. Wolfe eds., McGraw-Hill, New York (1963) 269--302.
	14	R. E. Gomory, Thoughts about Integer Programming, 50th Anniversary Symposium of OR, University of Montreal, January 2007, and Corner Polyhedra and Two-Equation Cutting Planes, George Nemhauser Symposium, Atlanta, July 2007.
	15	L. Lovász, Geometry of Numbers and Integer Programming, Mathematical Programming: Recent Developments and Applications, M. Iri and K. Tanabe eds., Kluwer (1989) 177--210.
	16	Hugues Marchand , Laurence A. Wolsey, Aggregation and Mixed Integer Rounding to Solve MIPs, Operations Research, v.49 n.3, p.363-371, May 2001 [doi>10.1287/opre.49.3.363.11211]
	17	R. R. Meyer, On the Existence of Optimal Solutions to Integer and Mixed Integer Programming Problems, Mathematical Programming 7 (1974) 223--235.
	18	A. Basu, P. Bonami, G. Cornuejols, F. Margot, On the Relative Strength of Split, Triangle and Quadrilateral Cuts, Optimization Online, http://www.optimization-online.org/DB.HTML/2008/08/2060.html
	19	G L. Nemhauser , L. A. Wolsey, A recursive procedure to generate all cuts for 0-1 mixed integer programs, Mathematical Programming: Series A and B, v.46 n.3, p.379-390, February 1990 [doi>10.1007/BF01585752]