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 条
12345