This paper introduces a new optimization problem, namely the Polynomial Robust Knapsack Problem. It generalises the Robust Knapsack formulation to encompass possible relations between subsets of items having every possible cardinality. This allows to better describe the utility function for the decision maker, at the price of increasing the complexity of the problem. Thus, in order to solve realistic instances in a reasonable amount of time, two heuristics are proposed. The first one applies machine learning techniques in order to quickly select the majority of the items, while the second makes use of genetic algorithms to solve the problem. A set of simulation examples is finally presented to show the effectiveness of the proposed approaches.

The polynomial robust knapsack problem / Baldo, Alessandro; Boffa, Matteo; Cascioli, Lorenzo; Fadda, Edoardo; Lanza, Chiara; Ravera, Arianna. - In: EUROPEAN JOURNAL OF OPERATIONAL RESEARCH. - ISSN 0377-2217. - STAMPA. - (2022). [10.1016/j.ejor.2022.06.029]

The polynomial robust knapsack problem

Boffa, Matteo;Fadda, Edoardo;
2022

Abstract

This paper introduces a new optimization problem, namely the Polynomial Robust Knapsack Problem. It generalises the Robust Knapsack formulation to encompass possible relations between subsets of items having every possible cardinality. This allows to better describe the utility function for the decision maker, at the price of increasing the complexity of the problem. Thus, in order to solve realistic instances in a reasonable amount of time, two heuristics are proposed. The first one applies machine learning techniques in order to quickly select the majority of the items, while the second makes use of genetic algorithms to solve the problem. A set of simulation examples is finally presented to show the effectiveness of the proposed approaches.
File in questo prodotto:
File Dimensione Formato  
Article_EJOR.pdf

non disponibili

Descrizione: Elsevier version
Tipologia: 2a Post-print versione editoriale / Version of Record
Licenza: Non Pubblico - Accesso privato/ristretto
Dimensione 1.31 MB
Formato Adobe PDF
1.31 MB Adobe PDF   Visualizza/Apri   Richiedi una copia
Accepted_EJOR.pdf

embargo fino al 22/06/2024

Descrizione: Accepted Manuscript
Tipologia: 2. Post-print / Author's Accepted Manuscript
Licenza: Creative commons
Dimensione 446.09 kB
Formato Adobe PDF
446.09 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/2969420