Show simple item record

Professor Advisordc.contributor.advisorEspinoza González, Daniel 
Authordc.contributor.authorSerrano Musalem, Felipe 
Staff editordc.contributor.editorFacultad de Ciencias Físicas y Matemáticas
Staff editordc.contributor.editorDepartamento de Ingeniería Industrial
Associate professordc.contributor.otherCorrea Haeussler, José 
Associate professordc.contributor.otherMatamala Vásquez, Martín
Associate professordc.contributor.otherGoycoolea Guzmán, Marcos
Admission datedc.date.accessioned2013-10-10T19:05:14Z
Available datedc.date.available2013-10-10T19:05:14Z
Publication datedc.date.issued2013
Identifierdc.identifier.urihttps://repositorio.uchile.cl/handle/2250/114463
General notedc.descriptionMagíster en Gestión de Operaciones
General notedc.descriptionIngeniero Civil Industrial
Abstractdc.description.abstractSince 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.en_US
Lenguagedc.language.isoenen_US
Publisherdc.publisherUniversidad de Chileen_US
Type of licensedc.rightsAttribution-NonCommercial-NoDerivs 3.0 Chile*
Link to Licensedc.rights.urihttp://creativecommons.org/licenses/by-nc-nd/3.0/cl/*
Keywordsdc.subjectOptimización matemáticaen_US
Títulodc.titleSome experiments on separation with multi-row cutsen_US
Document typedc.typeTesis


Files in this item

Icon

This item appears in the following Collection(s)

Show simple item record

Attribution-NonCommercial-NoDerivs 3.0 Chile
Except where otherwise noted, this item's license is described as Attribution-NonCommercial-NoDerivs 3.0 Chile