Publication Date:
2012
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-andbound
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. Heuristics 4(1) 63–86].
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-andbound
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. Heuristics 4(1) 63–86].
CRIS type:
1.1 Articolo in rivista
Keywords:
Multidimensional Knapsack Problem; exact algorithm; reduced costs; recursive variable fixing; cardinality constraint
List of contributors:
Mansini, Renata; Speranza, Maria Grazia
Published in: