We propose a unified exact approach for two different generalizations of the 0-1 Knapsack problem, that is the 0-1 Knapsack Problem with Setups and the 0-1 Collapsing Knapsack Problem. In the first problem, the items belong to disjoint families (or classes) and they can be picked only if the corresponding family is activated. The selection of a class involves setup costs and resource consumptions thus affecting both the objective function and the capacity constraint. In the 0-1 Collapsing Knapsack Problem the capacity of the knapsack is not a scalar but a non-increasing function of the number of items included, namely it is inversely related to the number of items placed inside the knapsack. The unified approach involves three main steps and relies on an effective exploration of a specific set of variables that leads to solve standard knapsack problems. It proves to be very effective both on the 0-1 Knapsack Problem with Setups and on the 0-1 Collapsing Knapsack Problem and is capable of solving to optimality large size instances with limited computational effort. The method significantly outperforms the state of art solver CPLEX 12.5 and compares favorably to the algorithms available in literature.
A Unified Exact Approach for Knapsack Problems with Side Constraints / DELLA CROCE DI DOJOLA, Federico; Salassa, FABIO GUIDO MARIO; Scatamacchia, Rosario. - (2015), pp. 93-93. (Intervento presentato al convegno EURO 2015 tenutosi a Glasgow (UK) nel 12-15 July 2015).
A Unified Exact Approach for Knapsack Problems with Side Constraints
DELLA CROCE DI DOJOLA, Federico;SALASSA, FABIO GUIDO MARIO;SCATAMACCHIA, ROSARIO
2015
Abstract
We propose a unified exact approach for two different generalizations of the 0-1 Knapsack problem, that is the 0-1 Knapsack Problem with Setups and the 0-1 Collapsing Knapsack Problem. In the first problem, the items belong to disjoint families (or classes) and they can be picked only if the corresponding family is activated. The selection of a class involves setup costs and resource consumptions thus affecting both the objective function and the capacity constraint. In the 0-1 Collapsing Knapsack Problem the capacity of the knapsack is not a scalar but a non-increasing function of the number of items included, namely it is inversely related to the number of items placed inside the knapsack. The unified approach involves three main steps and relies on an effective exploration of a specific set of variables that leads to solve standard knapsack problems. It proves to be very effective both on the 0-1 Knapsack Problem with Setups and on the 0-1 Collapsing Knapsack Problem and is capable of solving to optimality large size instances with limited computational effort. The method significantly outperforms the state of art solver CPLEX 12.5 and compares favorably to the algorithms available in literature.Pubblicazioni consigliate
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
https://hdl.handle.net/11583/2639638
Attenzione
Attenzione! I dati visualizzati non sono stati sottoposti a validazione da parte dell'ateneo