Doctoral thesis (Dissertations and theses)
Multi-row approaches to cutting plane generation
Poirrier, Laurent
2012
 

Files


Full Text
thesis.pdf
Author postprint (1.32 MB)
Download

All documents in ORBi are protected by a user license.

Send to



Details



Keywords :
Integer Programming; Cutting Planes; Multi-row Cuts
Abstract :
[en] This thesis focuses on the use of cutting-plane techniques to improve general-purpose mixed-integer linear programming solvers. The first topic covered here is a fast separation method for two-row cuts. Two-row cuts are intersection cuts from two rows of a simplex tableau describing the LP relaxation of the problem. This type of cuts recently gathered a lot of attention from the scientific community following a paper by Andersen, Louveaux, Weismantel and Wolsey describing the facets of the underlying two-row model and providing an intuitive geometric classification the the derived cuts. The specificity of the approach adopted here is that it does not rely on an "infinite relaxation" point of view and generate intersection cuts from fixed lattice-free sets. Instead, given a fractional point, it aims at always finding a most violated facet-defining inequality for the two-row model. This can be achieved by optimizing over the polar set of the integer hull of the model. A fast way of performing this is provided, by means of a polyhedron that is equivalent to the polar for that purpose, but has a more compact representation. Moreover, a row-generation algorithm is developed in order to avoid the costly computations of integer hulls of two-dimensional cones. An implementation of the resulting algorithm performs separation of two-row cuts in a few milliseconds on average, on the standard MIPLIB 3 and 2003 testsets. While this two-row separator is quick, the measurements of the computational usefulness of the cuts do not yield satisfactory results. Since all the cuts generated are facet-defining, this might suggest that the underlying two-row models are too weak. This observation prompted the second part of this thesis, an attempt to evaluate the strength of various multi-row relaxations, on small instances, using a generic separator. To that end, a separator is developed, which is able to compute facet-defining inequalities from arbitrary (yet reasonably small) mixed-integer sets. A row-generation approach is again adopted, but this time the slave part consists in the resolution of a mixed-integer problem instead of a closed-form oracle. Some interesting computational tricks are developed, in order to speedup the inherently hard computations.
Research center :
Systems and Modeling
Montefiore Institute - Montefiore Institute of Electrical Engineering and Computer Science - ULiège
Disciplines :
Mathematics
Electrical & electronics engineering
Author, co-author :
Poirrier, Laurent ;  Université de Liège - ULiège > Montefiore Institute > Discrete Optimization > Form. doct. sc. ingé. (élec. & électro. - Bologne)
Language :
English
Title :
Multi-row approaches to cutting plane generation
Defense date :
18 December 2012
Number of pages :
125
Institution :
ULiège - Université de Liège
Degree :
PhD
Promotor :
Louveaux, Quentin ;  Université de Liège - ULiège > Montefiore Institute of Electrical Engineering and Computer Science
President :
Sepulchre, Rodolphe ;  Université de Liège - ULiège > Montefiore Institute of Electrical Engineering and Computer Science
Jury member :
Boigelot, Bernard  ;  Université de Liège - ULiège > Montefiore Institute of Electrical Engineering and Computer Science
Crama, Yves  ;  Université de Liège - ULiège > HEC Recherche > HEC Recherche: Business Analytics & Supply Chain Management
Cornuéjols, Gérard
Dey, Santanu
Salvagnin, Domenico
Name of the research project :
Belgian Network DYSCO (Dynamical Systems, Control, and Optimization)
Funders :
ULiège - Université de Liège [BE]
Interuniversity Attraction Poles Programme, initiated by the Belgian State, Science Policy Office
Available on ORBi :
since 22 November 2012

Statistics


Number of views
132 (34 by ULiège)
Number of downloads
142 (16 by ULiège)

Bibliography


Similar publications



Contact ORBi