On the exact separation of mixed integer knapsack cuts

Ricardo Fukasawa, Marcos Goycoolea

Resultado de la investigación: Capítulo del libro/informe/acta de congresoContribución a la conferenciarevisión exhaustiva

6 Citas (Scopus)

Resumen

During the last decades, much research has been conducted deriving classes of valid inequalities for single-row mixed integer programming polyhedrons. However, no such class has had as much practical success as the MIR inequality when used in cutting plane algorithms for general mixed integer programming problems. In this work we analyze this empirical observation by developing an algorithm which takes as input a point and a single-row mixed integer polyhedron, and either proves the point is in the convex hull of said polyhedron, or finds a separating hyperplane. The main feature of this algorithm is a specialized subroutine for solving the Mixed Integer Knapsack Problem which exploits cost and lexicographic dominance. Separating over the entire closure of single-row systems allows us to establish natural benchmarks by which to evaluate specific classes of knapsack cuts. Using these benchmarks on Miplib 3.0 instances we analyze the performance of MIR inequalities. Computations are performed in exact arithmetic.

Idioma originalInglés
Título de la publicación alojadaInteger Programming and Combinatorial Optimization - 12th International IPCO Conference, Proceedings
EditorialSpringer Verlag
Páginas225-239
Número de páginas15
ISBN (versión impresa)9783540727910
DOI
EstadoPublicada - 2007
Evento12th International Conference on Integer Programming and Combinatorial Optimization, IPCO XII - Ithaca, NY, Estados Unidos
Duración: 25 jun. 200727 jun. 2007

Serie de la publicación

NombreLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volumen4513 LNCS
ISSN (versión impresa)0302-9743
ISSN (versión digital)1611-3349

Conferencia

Conferencia12th International Conference on Integer Programming and Combinatorial Optimization, IPCO XII
País/TerritorioEstados Unidos
CiudadIthaca, NY
Período25/06/0727/06/07

Huella

Profundice en los temas de investigación de 'On the exact separation of mixed integer knapsack cuts'. En conjunto forman una huella única.

Citar esto