LP relaxation and dynamic programming enhancing VNS for the multiple knapsack problem with setup

被引：4

作者：

Masmoudi, Malek ^{[1
]}

Adouani, Yassine ^{[2
]}

Jarboui, Bassem ^{[3
]}

机构：

[1] Univ Sharjah, Coll Engn, Sharjah, U Arab Emirates

[2] Univ Sfax, Fac Econ & Management Sci Sfax, Lab Modeling & Optimizat Decis Ind & Logist Syst, Sfax, Tunisia

[3] Higher Coll Technol, Abu Dhabi, U Arab Emirates

来源：

INTERNATIONAL TRANSACTIONS IN OPERATIONAL RESEARCH | 2024年 / 31卷 / 03期

关键词：

metaheuristics; LP relaxation; dynamic programming; variable neighborhood search; multiple knapsack problem with setup; VARIABLE NEIGHBORHOOD SEARCH; ALGORITHM;

D O I：

10.1111/itor.13213

中图分类号：

C93 [管理学];

学科分类号：

12 ; 1201 ; 1202 ; 120202 ;

摘要：

We consider the multiple knapsack problem (KP) with setup (MKPS), which is an extension of the KP with setup (KPS). We propose a new solving approach denoted by LP&DP-VNS that combines linear programming (LP) relaxation and dynamic programming (DP) to enhance variable neighborhood search (VNS). The LP&DP-VNS is tailored to the characteristics of the MKPS and reduced to LP&DP to solve the KPS. The approach is tested on 200 KPS and 360 MKPS benchmark instances. Computational experiments show the effectiveness of the LP&DP-VNS, compared to integer programming (using CPLEX) and the best state-of-the-art algorithms. It reaches 299/342 optimal solutions and 316/318 best-known solutions and provides 127 new best solutions. An additional computational study shows that the LP&DP-VNS scales up extremely well, solving optimally and near-optimally very large instances with up 200 families and 300,000 items in a reasonable amount of time.

引用

页码：1890 / 1916

页数：27

共 46 条

[1] A matheuristic for the 0-1 generalized quadratic multiple knapsack problem [J].

Adouani, Yassine ;

Jarboui, Bassem ;

Masmoudi, Malek .

OPTIMIZATION LETTERS, 2022, 16 (01) :37-58

[2] Efficient matheuristic for the generalised multiple knapsack problem with setup [J].

Adouani, Yassine ;

Jarboui, Bassem ;

Masmoudi, Malek .

EUROPEAN JOURNAL OF INDUSTRIAL ENGINEERING, 2020, 14 (05) :715-741

[3] A hybrid population-based algorithm for the bi-objective quadratic multiple knapsack problem [J].

Aider, Meziane ;

Gacem, Oussama ;

Hifi, Mhand .

EXPERT SYSTEMS WITH APPLICATIONS, 2022, 191

[4] Greedy algorithm for the general multidimensional knapsack problem [J].

Akcay, Yalcin ;

Li, Haijun ;

Xu, Susan H. .

ANNALS OF OPERATIONS RESEARCH, 2007, 150 (01) :17-29

[5] Sensitivity analysis of the setup knapsack problem to perturbation of arbitrary profits or weights [J].

Al-Maliky, Ferhan ;

Hifi, Mhand ;

Mhalla, Hedi .

INTERNATIONAL TRANSACTIONS IN OPERATIONAL RESEARCH, 2018, 25 (02) :637-666

[6] A Lagrangean based solution algorithm for the multiple knapsack problem with setups [J].

Amiri, Ali ;

Barkhi, Reza .

COMPUTERS & INDUSTRIAL ENGINEERING, 2021, 153

[7] A Lagrangean based solution algorithm for the knapsack problem with setups [J].

Amiri, Ali .

EXPERT SYSTEMS WITH APPLICATIONS, 2020, 143

[8] A multi-start iterated local search algorithm for the generalized quadratic multiple knapsack problem [J].

Avci, Mustafa ;

Topaloglu, Seyda .

COMPUTERS & OPERATIONS RESEARCH, 2017, 83 :54-65

[9] DYNAMIC PROGRAMMING [J].

BELLMAN, R .

SCIENCE, 1966, 153 (3731) :34-&

[10]

Boukhari Samah, 2022, Intelligent Computing: Proceedings of the 2021 Computing Conference. Lecture Notes in Networks and Systems, P154, DOI 10.1007/978-3-030-80119-9_7

← 1 2 3 4 5 →