  


The Triangle Closure is a Polyhedron
Amitabh Basu(abasumath.ucdavis.edu) Abstract: Recently, cutting planes derived from maximal latticefree convex sets have been studied intensively by the integer programming community. An important question in this research area has been to decide whether the closures associated with certain families of latticefree sets are polyhedra. For a long time, the only result known was the celebrated theorem of Cook, Kannan and Schrijver who showed that the split closure is a polyhedron. Although some fairly general results were obtained by Andersen, Louveaux and Weismantel [An analysis of mixed integer linear sets based on lattice point free convex sets, Math. Oper. Res. 35, (2010) pp. 233256], some basic questions have remained unresolved. For example, maximal latticefree triangles are the natural family to study beyond the family of splits and it has been a standing open problem to decide whether the triangle closure is a polyhedron. In this paper, we resolve this by showing that the triangle closure is indeed a polyhedron, and its number of facets can be bounded by a polynomial in the size of the input data. Keywords: MixedInteger Programming, Polyhedral Structure, Cutting Plane Algorithms Category 1: Integer Programming (Cutting Plane Approaches ) Citation: Download: [PDF] Entry Submitted: 11/07/2011 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  