Title | ||
---|---|---|
A Stochastic Local Search Heuristic for the Multidimensional Multiple-choice Knapsack Problem. |
Abstract | ||
---|---|---|
The Multidimensional Multiple-choice Knapsack Problem (M MKP) is an NP-hard combinatorial optimization task that appears in various applications. We present a fast stochastic local search heuristic for the MMKP that uses an iterative perturbative search paradigm with penalty weights for dimensions, and an additive weighting scheme is adopted to diversify the search. Our heuristic is tested on the standard benchmark problem instances. Experiments show that it is very competitive in terms of the best solutions found, compared the fast heuristics in the literature. Besides, our heuristic is easy to implement, has no parameter to tune in practice. |
Year | DOI | Venue |
---|---|---|
2015 | 10.1007/978-3-662-49014-3_46 | Communications in Computer and Information Science |
Keywords | Field | DocType |
Combinatorial optimization,Multidimensional multiple-choice knapsack problem,Stochastic local search | Heuristic,Mathematical optimization,Incremental heuristic search,Computer science,Combinatorial optimization,Continuous knapsack problem,Heuristics,Cutting stock problem,Knapsack problem,Local search (optimization) | Conference |
Volume | ISSN | Citations |
562 | 1865-0929 | 1 |
PageRank | References | Authors |
0.35 | 19 | 3 |
Name | Order | Citations | PageRank |
---|---|---|---|
Youxin Xia | 1 | 1 | 0.35 |
Chao Gao | 2 | 42 | 5.78 |
Jinlong Li | 3 | 239 | 8.14 |