The polynomial robust knapsack problem

被引：10

作者：

Baldo, Alessandro ^{[1
]}

Boffa, Matteo ^{[2
]}

Cascioli, Lorenzo ^{[1
]}

Fadda, Edoardo ^{[1
,3
]}

Lanza, Chiara ^{[1
]}

Ravera, Arianna ^{[1
]}

机构：

[1] ISIRES, Turin, Italy

[2] Politecn Torino, Dept Elect & Telecommun, Turin, Italy

[3] Politecn Torino, Dept Math Sci Giuseppe Luigi Lagrange, Turin, Italy

来源：

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH | 2023年 / 305卷 / 03期

关键词：

Heuristics; Robust knapsack problem; Genetic algorithm; Machine learning; EXACT ALGORITHMS; OPTIMIZATION; MAX;

D O I：

10.1016/j.ejor.2022.06.029

中图分类号：

C93 [管理学];

学科分类号：

12 ; 1201 ; 1202 ; 120202 ;

摘要：

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.

引用

页码：1424 / 1434

页数：11

共 23 条

[1] Approximation of min-max and min-max regret versions of some combinatorial optimization problems [J].