We consider a generalization of the 0–1 Knapsack problem, that is the Penalized Knapsack Problem. We devise an improved dynamic programming algorithm and a new integer linear formulation of the problem. Further, we propose an exact approach that exploits the peculiarities of the new ILP formulation. The approach turns out to be very effective in solving hard instances and compares favorably to both the state of art solver CPLEX 12.5 and the algorithms available in literature.

Exact Algorithms for the 0-1 Penalized Knapsack Problem / DELLA CROCE DI DOJOLA, Federico; Scatamacchia, Rosario. - (2015), pp. 269-269. (Intervento presentato al convegno AIRO 2015 tenutosi a Pisa nel 7-10 Settembre 2015).

Exact Algorithms for the 0-1 Penalized Knapsack Problem

DELLA CROCE DI DOJOLA, Federico;SCATAMACCHIA, ROSARIO
2015

Abstract

We consider a generalization of the 0–1 Knapsack problem, that is the Penalized Knapsack Problem. We devise an improved dynamic programming algorithm and a new integer linear formulation of the problem. Further, we propose an exact approach that exploits the peculiarities of the new ILP formulation. The approach turns out to be very effective in solving hard instances and compares favorably to both the state of art solver CPLEX 12.5 and the algorithms available in literature.
File in questo prodotto:
Non ci sono file associati a questo prodotto.
Pubblicazioni consigliate

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11583/2639568
 Attenzione

Attenzione! I dati visualizzati non sono stati sottoposti a validazione da parte dell'ateneo