Some experiments on separation with multi-row cuts
Professor Advisor
dc.contributor.advisor
Espinoza González, Daniel
Author
dc.contributor.author
Serrano Musalem, Felipe
Staff editor
dc.contributor.editor
Facultad de Ciencias Físicas y Matemáticas
Staff editor
dc.contributor.editor
Departamento de Ingeniería Industrial
Associate professor
dc.contributor.other
Correa Haeussler, José
Associate professor
dc.contributor.other
Matamala Vásquez, Martín
Associate professor
dc.contributor.other
Goycoolea Guzmán, Marcos
Admission date
dc.date.accessioned
2013-10-10T19:05:14Z
Available date
dc.date.available
2013-10-10T19:05:14Z
Publication date
dc.date.issued
2013
Identifier
dc.identifier.uri
https://repositorio.uchile.cl/handle/2250/114463
General note
dc.description
Magíster en Gestión de Operaciones
General note
dc.description
Ingeniero Civil Industrial
Abstract
dc.description.abstract
Since Andersen et al. there has been a lot of interest in multi-row cuts. However, computational study has been limited. Most research consider multi-row cuts deduced from only 2 rows and they use bounds on none or only on one type of variables, always relaxing integrality of non-basic variables when bounds are taken into account. Also, most applications aim to exact separation as well as using fixed convex lattice free bodies to separate.
In this work we try a numerical approach that allows us to look into more complex relaxations and we introduce an approximated separation hoping for a practical implementation to be possible. Extensively numerical analysis has been done to ensure numerical stability and minimize the creation of false cuts. Also, we incorporate some simple forms of taking advantage of integrality of non basic variables.
Once the rows of a tableau are obtained we search for a ``deep cut'' which we understand as a cut ($\alpha x \ge 1$) that minimizes $\norm{\alpha}$. To find it, we solve the dual using a column generation approach.
We tested both, $\l^1-$norm and $\l^2-$norm, where the latter one is treated using Ben-Tal and Nemirovsky approximation of the second order cone.
In order to speed up the process we seek for violated representations of fixed points.
Different criteria for row selection is tested: random selection, largest dot product and smallest dot product. To give a more complete idea about the strength of multi-rows cuts, we also generated all possible cuts using all combination of rows, but without aggregation of rows. We compare this to Balas computations of the split closure.
As for the experiments done in this work, we analyze the impact in the root node of the procedure (using various rounds) over MIPLIB3. Also, we select a good configuration and test its performance in branch and bound.