The Triangle Closure is a Polyhedron

Details The Triangle Closure is a Polyhedron The Triangle Closure is a Polyhedron

2011-11-08

arxiv.org/abs/1111.1780v1

Mathematics

Optimization and Control

27 pages

Scientific paper

Recently, cutting planes derived from maximal lattice-free 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 lattice-free 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. 233--256], some basic questions have remained unresolved. For example, maximal lattice-free 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.

Affiliated with

Also associated with

No associations

Rating

The Triangle Closure is a Polyhedron does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with The Triangle Closure is a Polyhedron, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and The Triangle Closure is a Polyhedron will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-52853