Journal
EUROPEAN JOURNAL OF OPERATIONAL RESEARCH
Volume 305, Issue 3, Pages 1424-1434Publisher
ELSEVIER
DOI: 10.1016/j.ejor.2022.06.029
Keywords
Heuristics; Robust knapsack problem; Genetic algorithm; Machine learning
Ask authors/readers for more resources
This paper introduces a new optimization problem called the Polynomial Robust Knapsack Problem. It extends the Robust Knapsack formulation to consider relations between subsets of items, increasing the complexity of the problem. To solve realistic instances within a reasonable time, two heuristics are proposed - one using machine learning techniques and the other using genetic algorithms. Simulation examples demonstrate the effectiveness of these approaches.
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 tech-niques in order to quickly select the majority of the items, while the second makes use of genetic algo-rithms to solve the problem. A set of simulation examples is finally presented to show the effectiveness of the proposed approaches.(c) 2022 Elsevier B.V. All rights reserved.
Authors
I am an author on this paper
Click your name to claim this paper and add it to your profile.
Reviews
Recommended
No Data Available