Unpublished conference/Abstract (Scientific congresses and symposiums)
Cutting planes from lattice-point-free polyhedra
Louveaux, Quentin
200711th combinatorial optimization workshop
 

Files


Full Text
aussois07ql-final.pdf
Author preprint (781.31 kB)
Download

All documents in ORBi are protected by a user license.

Send to



Details



Keywords :
Mixed-integer programming; Cutting planes
Abstract :
[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.
Disciplines :
Computer science
Author, co-author :
Louveaux, Quentin ;  Université de Liège - ULiège > Dép. d'électric., électron. et informat. (Inst.Montefiore) > Système et modélisation : Optimisation discrète
Language :
English
Title :
Cutting planes from lattice-point-free polyhedra
Publication date :
January 2007
Event name :
11th combinatorial optimization workshop
Event place :
Aussois, France
Event date :
January 2007
By request :
Yes
Available on ORBi :
since 21 May 2012

Statistics


Number of views
35 (0 by ULiège)
Number of downloads
35 (0 by ULiège)

Bibliography


Similar publications



Contact ORBi