We consider the 0/1 Collapsing Knapsack Problem (CKP) and a generalization involving more than a capacity constraint (M-CKP). We propose a novel ILP formulation and a problem reduction procedure together with an exact approach. The proposed approach compares favorably to the methods available in the literature and manages to solve to optimality very large size instances particularly for CKP and 2-CKP.
A new exact approach for the 0–1 Collapsing Knapsack Problem / DELLA CROCE DI DOJOLA, Federico; Salassa, FABIO GUIDO MARIO; Scatamacchia, Rosario. - In: EUROPEAN JOURNAL OF OPERATIONAL RESEARCH. - ISSN 0377-2217. - 260:(2017), pp. 56-69. [10.1016/j.ejor.2016.12.009]
A new exact approach for the 0–1 Collapsing Knapsack Problem
DELLA CROCE DI DOJOLA, Federico;SALASSA, FABIO GUIDO MARIO;SCATAMACCHIA, ROSARIO
2017
Abstract
We consider the 0/1 Collapsing Knapsack Problem (CKP) and a generalization involving more than a capacity constraint (M-CKP). We propose a novel ILP formulation and a problem reduction procedure together with an exact approach. The proposed approach compares favorably to the methods available in the literature and manages to solve to optimality very large size instances particularly for CKP and 2-CKP.Pubblicazioni consigliate
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
https://hdl.handle.net/11583/2659040
Attenzione
Attenzione! I dati visualizzati non sono stati sottoposti a validazione da parte dell'ateneo