Journal
COMPUTATIONAL OPTIMIZATION AND APPLICATIONS
Volume 46, Issue 1, Pages 51-73Publisher
SPRINGER
DOI: 10.1007/s10589-008-9184-7
Keywords
Branch-and-bound; Column generation; Heuristics; Knapsack; Optimization
Ask authors/readers for more resources
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.
Authors
I am an author on this paper
Click your name to claim this paper and add it to your profile.
Reviews
Recommended
No Data Available