We consider the 0-1 Knapsack Problem with Setups. We propose an exact approach which handles the structure of the ILP formulation of the problem. It relies on partitioning the variables set into two levels and exploiting this partitioning. The proposed approach favorably compares to the algorithms in literature and to solver CPLEX 12.5 applied to the ILP formulation. It turns out to be very effective and capable of solving to optimality, within limited CPU time, all instances with up to 100,000 variables.
An exact approach for the 0–1 knapsack problem with setups / DELLA CROCE DI DOJOLA, Federico; Salassa, FABIO GUIDO MARIO; Scatamacchia, Rosario. - In: COMPUTERS & OPERATIONS RESEARCH. - ISSN 0305-0548. - 80:(2017), pp. 61-67. [10.1016/j.cor.2016.11.015]
An exact approach for the 0–1 knapsack problem with setups
DELLA CROCE DI DOJOLA, Federico;SALASSA, FABIO GUIDO MARIO;SCATAMACCHIA, ROSARIO
2017
Abstract
We consider the 0-1 Knapsack Problem with Setups. We propose an exact approach which handles the structure of the ILP formulation of the problem. It relies on partitioning the variables set into two levels and exploiting this partitioning. The proposed approach favorably compares to the algorithms in literature and to solver CPLEX 12.5 applied to the ILP formulation. It turns out to be very effective and capable of solving to optimality, within limited CPU time, all instances with up to 100,000 variables.File | Dimensione | Formato | |
---|---|---|---|
KPsetup.pdf
Open Access dal 16/11/2019
Descrizione: Article
Tipologia:
2. Post-print / Author's Accepted Manuscript
Licenza:
Creative commons
Dimensione
359.88 kB
Formato
Adobe PDF
|
359.88 kB | Adobe PDF | Visualizza/Apri |
1-s2.0-S0305054816302787-main.pdf
accesso riservato
Tipologia:
2a Post-print versione editoriale / Version of Record
Licenza:
Non Pubblico - Accesso privato/ristretto
Dimensione
353.32 kB
Formato
Adobe PDF
|
353.32 kB | Adobe PDF | Visualizza/Apri Richiedi una copia |
Pubblicazioni consigliate
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
https://hdl.handle.net/11583/2657654
Attenzione
Attenzione! I dati visualizzati non sono stati sottoposti a validazione da parte dell'ateneo