Article Preview
Top1. Introduction
The Multidimensional 0-1 Knapsack Problem (MKP) is a well-known optimization problem, which is identified to be an NP-hard problem. The mathematical formulation of MKP can be stated as follows:
(1) (2) (3) where
n is a set of items with worthy profits
cj ≥ 0 and
m represents the dimensions of a knapsack, with capacities
bi ≥ 0. Each item
j consumes an amount
aij ≥ 0 from each dimension
i and the binary decision variables
xj indicate which items are selected. The aim of this problem is to choose a subset of items with maximum total profit. For each constraint
i = {1, 2, ...,
m},
aij units are consumed from capacity
bi, if item
j is selected, where the selected items need not exceed the available capacities (Kellerer et al., 2004; Akçay et al., 2007).
The practical and theoretical importance of MKP has led to a large body of literature. Some exact, heuristic and metaheuristic methods have been suggested to solve MKPs. Fréville (2004) proposes a good review of the related problems, applications, and solution techniques.
A key step in designing an efficient exact solution method for such problem is to establish a tight upper bound on the optimal value. Quadri et al. (2007) present an effective upper bound method based on a linearization and surrogate relaxation. Boussier et al. (2010) propose a multi-level search strategy for MKP. This strategy is primarily based on the reduced costs of the non-basic variables of the LP-relaxation solution. Pi et al. (2008) use the linear relaxation solutions to generate high quality samples used for solving the local pickup and delivery problem, and the discrete facility location problem.
Several heuristic methods have been proposed to solve MKP. Akçay et al. (2007) propose a greedy heuristic which orders items by their values multiplied by the maximum number of copies of an item that could be accommodated with the resources. Puchinger et al. (2010) propose a heuristic algorithm which exploits the core problem approach proposed by Balas and Zemel (1980) for the one-dimensional knapsack problem. Their best solutions, requiring less CPU time, are dominated by those presented in Vimont et al. (2008). Hanfi and Glover (2007) offer a better exploitation of nested inequalities and surrogate constraints on MKP than Osorio et al. (2002), but they do not offer computational results. Della Croce and Grosso (2012) propose a new heuristic procedure for a parallel computing environment embedding core problem approaches and a branching scheme based on reduced costs of the corresponding LP relaxation solution value.
Fleszar and Hindi (2009) introduce several heuristics for MKP that are based on solving the LP relaxation of the problem. Hill et al. (2012) introduce problem-size reduction heuristics using the dual variables to formulate a Lagrangian relaxation of the original problem. Angelelli et al. (2010) apply the kernel search framework to solve MKP. Wilbaut et al. (2009) develop an iterative scheme which is based on a dynamic fixation of the variables.