The polynomial robust knapsack problem

Alessandro Baldo, Matteo Boffa, Lorenzo Cascioli, Edoardo Fadda, Chiara Lanza and Arianna Ravera

European Journal of Operational Research, 2023, vol. 305, issue 3, 1424-1434

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.

Keywords: Heuristics; Robust knapsack problem; Genetic algorithm; Machine learning (search for similar items in EconPapers)
Date: 2023
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0377221722005045
Full text for ScienceDirect subscribers only

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:eee:ejores:v:305:y:2023:i:3:p:1424-1434

DOI: 10.1016/j.ejor.2022.06.029

Access Statistics for this article

European Journal of Operational Research is currently edited by Roman Slowinski, Jesus Artalejo, Jean-Charles. Billaut, Robert Dyson and Lorenzo Peccati

More articles in European Journal of Operational Research from Elsevier
Bibliographic data for series maintained by Catherine Liu ().