A branch-and-bound algorithm for hard multiple knapsack problems

被引:29
作者
Fukunaga, Alex S. [1 ]
机构
[1] Tokyo Inst Technol, Global Edge Inst, Meguro Ku, Tokyo 152, Japan
关键词
SUBSET SUM; PACKING;
D O I
10.1007/s10479-009-0660-y
中图分类号
C93 [管理学]; O22 [运筹学];
学科分类号
070105 ; 12 ; 1201 ; 1202 ; 120202 ;
摘要
The multiple knapsack problem (MKP) is a classical combinatorial optimization problem. A recent algorithm for some classes of the MKP is bin-completion, a bin-oriented, branch-and-bound algorithm. In this paper, we propose path-symmetry and path-dominance criteria for pruning nodes in the MKP branch-and-bound search space. In addition, we integrate the "bound-and-bound" upper bound validation technique used in previous MKP solvers. We show experimentally that our new MKP solver, which successfully integrates dominance based pruning, symmetry breaking, and bound-and-bound, significantly outperforms previous solvers on some classes of hard problem instances.
引用
收藏
页码:97 / 119
页数:23
相关论文
共 22 条
[1]  
[Anonymous], P 10 NAT C ART INT
[2]  
[Anonymous], 1990, Knapsack Problems: Algorithms and ComputerImplementations
[3]   A PTAS for the Multiple Subset Sum Problem with different knapsack capacities [J].
Caprara, A ;
Kellerer, H ;
Pferschy, U .
INFORMATION PROCESSING LETTERS, 2000, 73 (3-4) :111-118
[4]   A 3/4-approximation algorithm for multiple subset sum [J].
Caprara, A ;
Kellerer, H ;
Pferschy, U .
JOURNAL OF HEURISTICS, 2003, 9 (02) :99-111
[5]  
Chekuri C, 2000, PROCEEDINGS OF THE ELEVENTH ANNUAL ACM-SIAM SYMPOSIUM ON DISCRETE ALGORITHMS, P213
[6]   LOADING PROBLEM [J].
EILON, S ;
CHRISTOF.N .
MANAGEMENT SCIENCE SERIES A-THEORY, 1971, 17 (05) :259-268
[7]  
Fahle T., 2001, Principles and Practice of Constraint Programming - CP 2002. 7th International Conference, CP 2001. Proceedings (Lecture Notes in Computer Science Vol.2239), P93
[8]   A NEW DOMINANCE PROCEDURE FOR COMBINATORIAL OPTIMIZATION PROBLEMS [J].
FISCHETTI, M ;
TOTH, P .
OPERATIONS RESEARCH LETTERS, 1988, 7 (04) :181-187
[9]  
FISCHETTI M, 2008, PRUNING MOVES
[10]  
FOCACCI, 2001, PROC CP01, P77