Magíster en Gestión de Operaciones / Ingeniero Civil Industrial / 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.
| Identifer | oai:union.ndltd.org:UCHILE/oai:repositorio.uchile.cl:2250/114463 |
| Date | January 2013 |
| Creators | Serrano Musalem, Felipe |
| Contributors | Espinoza González, Daniel, Facultad de Ciencias Físicas y Matemáticas, Departamento de Ingeniería Industrial, Correa Haeussler, José, Matamala Vásquez, Martín, Goycoolea Guzmán, Marcos |
| Publisher | Universidad de Chile |
| Source Sets | Universidad de Chile |
| Language | English |
| Detected Language | English |
| Type | Tesis |
| Rights | Attribution-NonCommercial-NoDerivs 3.0 Chile, http://creativecommons.org/licenses/by-nc-nd/3.0/cl/ |
Page generated in 0.0018 seconds