Reference : Cutting planes from lattice-point-free polyhedra
Scientific congresses and symposiums : Unpublished conference
Engineering, computing & technology : Computer science
Cutting planes from lattice-point-free polyhedra
Louveaux, Quentin mailto [Université de Liège - ULg > Dép. d'électric., électron. et informat. (Inst.Montefiore) > Système et modélisation : Optimisation discrète >]
11th combinatorial optimization workshop
January 2007
[en] Mixed-integer programming ; Cutting planes
[en] In this talk, we generalize the concept of a split (that leads to split cuts) to any lattice-point-free polyhedron. We show how we can generate cutting planes for a polyhedron from these objects. Associated to any lattice-point-free polyhedron, we define a "split-dimension" (which is equal to 1 in the case of a split in the usual sense). We then consider the operation of adding to a polyhedron all cutting planes that we can obtain from considering all the lattice-point-free polyhedra with a split-dimension lower or equal to d. We call the obtained object the "d-dimensional split closure" of the initial polyhedron. We discuss whether this object is again a polyhedron or not.
As an important illustration, we focus on objects of split-dimension equal to 1 or 2.

File(s) associated to this reference

Fulltext file(s):

Open access
aussois07ql-final.pdfAuthor preprint763 kBView/Open

Bookmark and Share SFX Query

All documents in ORBi are protected by a user license.