Name
Abstract | ||
|---|---|---|
The multidimensional knapsack problem (MKP) is a well-known, strongly NP-hard problem and one of the most challenging problems in the class of the knapsack problems. In the last few years, it has been a favorite playground for metaheuristics, but very few contributions have appeared on exact methods. In this paper we introduce an exact approach based on the optimal solution of subproblems limited to a subset of variables. Each subproblem is faced through a recursive variable-fixing process that continues until the number of variables decreases below a given threshold (restricted core problem). The solution space of the restricted core problem is split into subspaces, each containing solutions of a given cardinality. Each subspace is then explored with a branch-and-bound algorithm. Pruning conditions are introduced to improve the efficiency of the branch-and-bound routine. In all the tested instances, the proposed method was shown to be, on average, more efficient than the recent branch-and-bound method proposed by Vimont et al. [Vimont, Y., S. Boussier, M. Vasquez. 2008. Reduced costs propagation in an efficient implicit enumeration for the 0-1 multidimensional knapsack problem. J. Combin. Optim.15(2) 165--178] and CPLEX 10. We were able to improve the best-known solutions for some of the largest and most difficult instances of the OR-LIBRARY data set [Chu, P. C., J. E. Beasley. 1998. A genetic algorithm for the multidimensional knapsack problem. J. Heuristics4(1) 63--86]. |
Year | DOI | Venue |
|---|---|---|
2012 | 10.1287/ijoc.1110.0460 | INFORMS Journal on Computing |
Keywords | Field | DocType |
restricted core problem,knapsack problem,branch-and-bound algorithm,j. e. beasley,multidimensional knapsack problem,branch-and-bound routine,j. combin,exact algorithm,challenging problem,np-hard problem,j. heuristics4 | Discrete mathematics,Mathematical optimization,Exact algorithm,Change-making problem,Generalized assignment problem,Cardinality,Continuous knapsack problem,Cutting stock problem,Knapsack problem,Mathematics,Metaheuristic | Journal |
Volume | Issue | ISSN |
24 | 3 | 1091-9856 |
Citations | PageRank | References |
21 | 0.70 | 15 |
Authors | ||
2 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Renata Mansini | 1 | 574 | 43.10 |
| M. Grazia Speranza | 2 | 663 | 45.44 |