A column generation method for the multiple-choice multi-dimensional knapsack problem

被引：40

作者：

Cherfi, N. ^{[2
]}

Hifi, M. ^{[1
]}

机构：

[1] Univ Picardie Jules Verne, MIS, F-80000 Amiens, France

[2] Univ Paris 01, Equipe CERMSEM, CES, F-75634 Paris 13, France

来源：

COMPUTATIONAL OPTIMIZATION AND APPLICATIONS | 2010年 / 46卷 / 01期

关键词：

Branch-and-bound; Column generation; Heuristics; Knapsack; Optimization; ALGORITHM;

D O I：

10.1007/s10589-008-9184-7

中图分类号：

C93 [管理学]; O22 [运筹学];

学科分类号：

070105 ; 12 ; 1201 ; 1202 ; 120202 ;

摘要：

In this paper, we propose to solve large-scale multiple-choice multi-dimensional knapsack problems. We investigate the use of the column generation and effective solution procedures. The method is in the spirit of well-known local search metaheuristics, in which the search process is composed of two complementary stages: (i) a rounding solution stage and (ii) a restricted exact solution procedure. The method is analyzed computationally on a set of problem instances of the literature and compared to the results reached by both Cplex solver and a recent reactive local search. For these instances, most of which cannot be solved to proven optimality in a reasonable runtime, the proposed method improves 21 out of 27.

引用

页码：51 / 73

页数：23

共 50 条

[41] An improved version of a core based algorithm for the multi-objective multi-dimensional knapsack problem: A computational study and comparison with meta-heuristics
Mavrotas, George
Florios, Kostas
Figueira, Jose Rui
APPLIED MATHEMATICS AND COMPUTATION, 2015, 270 : 25 - 43
[42] Stabilized column generation for the temporal knapsack problem using dual-optimal inequalities
Gschwind, Timo
Irnich, Stefan
OR SPECTRUM, 2017, 39 (02) : 541 - 556
[43] Identifying redundancy in multi-dimensional knapsack constraints based on surrogate constraints
Choi, Jiwoong
Choi, In-Chan
INTERNATIONAL JOURNAL OF COMPUTER MATHEMATICS, 2014, 91 (12) : 2470 - 2482
[44] A column generation based heuristic for the capacitated vehicle routing problem with three-dimensional loading constraints
Mahvash, Batoul
Awasthi, Anjali
Chauhan, Satyaveer
INTERNATIONAL JOURNAL OF PRODUCTION RESEARCH, 2017, 55 (06) : 1730 - 1747
[45] Construct, Merge, Solve and Adapt Versus Large Neighborhood Search for Solving the Multi-dimensional Knapsack Problem: Which One Works Better When?
Lizarraga, Evelia
Blesa, Maria J.
Blum, Christian
EVOLUTIONARY COMPUTATION IN COMBINATORIAL OPTIMIZATION (EVOCOP 2017), 2017, 10197 : 60 - 74
[46] A Column Generation Method for Quay Crane Scheduling Problem
Zheng, Kewei
Lu, Zhiqiang
Sun, Xiaoming
PROCEEDINGS OF 2010 INTERNATIONAL CONFERENCE ON LOGISTICS SYSTEMS AND INTELLIGENT MANAGEMENT, VOLS 1-3, 2010, : 81 - 85
[47] A K-means Supported Reinforcement Learning Framework to Multi-dimensional Knapsack
Bushaj, Sabah
Buyuktahtakin, I. Esra
JOURNAL OF GLOBAL OPTIMIZATION, 2024, 89 (03) : 655 - 685
[48] Multi-Swarm Optimization for Extracting Multiple-Choice Tests From Question Banks
Nguyen, Tram
Nguyen, Loan T. T.
Bui, Toan
Loc, Ho Dac
Pedrycz, Witold
Snasel, Vaclav
Vo, Bay
IEEE ACCESS, 2021, 9 : 32131 - 32148
[49] A prototype column generation strategy for the multiple container loading problem
Zhu, Wenbin
Huang, Weili
Lim, Andrew
EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 2012, 223 (01) : 27 - 39
[50] An informative column generation and decomposition method for a production planning and facility location problem
Liang, Zhe
He, Yan
Wu, Tao
Zhang, Canrong
INTERNATIONAL JOURNAL OF PRODUCTION ECONOMICS, 2015, 170 : 88 - 96

← 1 2 3 4 5 →