Publico General
Academicos e Investigadores
Profesionales y Empresas
USUARIO
CONTRASEÑA
recordar contraseña
Publicaciones
Título: Computing With Multi-Row Gomory Cuts
Autores: Daniel Espinoza
Tipo: Journal Paper
Referencia: Espinoza, D. (2008) Computing With Multi-Row Gomory Cuts. En Lodi, A., Panconesi, A. Rinaldi, G. (Eds.), Integer Programming and Combinatorial Optimization serie Lecture Notes in Computer Science, Springer Berlin, Heidelberg, 214-224.
Fecha: 2008
Abstract:  

Cutting planes for mixed integer problems (MIP) are nowadays an integral part of all general purpose software to solve MIP. The most prominent, and computationally significant, class of general cutting planes are Gomory mixed integer cuts (GMI). However finding other classes of general cuts for MIP that work well in practice has been elusive. Recent advances on the understanding of valid inequalities derived from the infinite relaxation introduced by Gomory and Johnson for mixed integer problems, has opened a new possibility of finding such an extension. In this paper, we investigate the computational impact of using a subclass of minimal valid inequalities from the infinite relaxation, using different number of tableau rows simultaneously, based on a simple separation procedure. We test these ideas on a set of MIPs, including MIPLIB 3.0 and MIPLIB 2003, and show that they can improve MIP performance even when compared against commercial software performance.

 


Dirección: Domeyko 2367, Santiago Centro, Chile    Teléfono: 562-26894429 / 562-26894403    E-Mail: contacto@sistemasdeingenieria.cl
El ISCI es una entidad inscrita en el Registro de Centros para la Realización de Actividades de Investigación o Desarrollo para fines de la Ley Nº 20.241, de Incentivo Tributario a la Inversión Privada en Investigación y Desarrollo
Iniciativa Científica Milenio FCFM CONICYT Iniciativa Científica Milenio CONICYT Programa de Financiamiento Basal FCFM Portada Portada