TY - JOUR
T1 - The precedence constrained knapsack problem
T2 - Separating maximally violated inequalities
AU - Espinoza, Daniel
AU - Goycoolea, Marcos
AU - Moreno, Eduardo
N1 - Funding Information:
This work was partially funded by FONDECYT grants 1110024 and 1110674 , ANILLO grant ACT-88 , Basal project CMM (Universidad de Chile) and ICM grant P10-024-F . We would especially like to thank the anonymous referees who handled this paper for their meticulous attention to detail, and for their generous and very useful suggestions.
Publisher Copyright:
© 2015 Elsevier B.V.
PY - 2015/10/30
Y1 - 2015/10/30
N2 - 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.
AB - 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.
KW - Induced clique inequality
KW - Induced cover inequality
KW - Lifting
KW - Precedence-constrained knapsack problem
KW - Separation problem
KW - Shrinking
UR - http://www.scopus.com/inward/record.url?scp=84940718765&partnerID=8YFLogxK
U2 - 10.1016/j.dam.2015.05.020
DO - 10.1016/j.dam.2015.05.020
M3 - Article
AN - SCOPUS:84940718765
SN - 0166-218X
VL - 194
SP - 65
EP - 80
JO - Discrete Applied Mathematics
JF - Discrete Applied Mathematics
ER -