The precedence constrained knapsack problem: Separating maximally violated inequalities

Daniel Espinoza, Marcos Goycoolea, Eduardo Moreno

Producción científica: Contribución a una revistaArtículorevisión exhaustiva

10 Citas (Scopus)

Resumen

We consider the problem of separating maximally violated inequalities for the precedence constrained knapsack problem. Though we consider maximally violated constraints in a very general way, special emphasis is placed on induced cover inequalities and induced clique inequalities. Our contributions include a new partial characterization of maximally violated inequalities, a new safe shrinking technique, and new insights on strengthening and lifting. This work follows on the work of Boyd (1993), Park and Park (1997), van de Leensel et al. (1999) and Boland et al. (2011). Computational experiments show that our new techniques and insights can be used to significantly improve the performance of cutting plane algorithms for this problem.

Idioma originalInglés
Páginas (desde-hasta)65-80
Número de páginas16
PublicaciónDiscrete Applied Mathematics
Volumen194
DOI
EstadoPublicada - 30 oct. 2015

Huella

Profundice en los temas de investigación de 'The precedence constrained knapsack problem: Separating maximally violated inequalities'. En conjunto forman una huella única.

Citar esto