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 in questo prodotto:
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

non disponibili

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.

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

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