Article Preview
Top1. Introduction
In this paper we are dealing with the 0-1 Multidimensional Knapsack Problem (MKP) which can be formulated as follows:
where
is the number of items and
is the number of knapsack constraints with capacities
Each item
yields
units of profit and consumes a given amount of resource
for each knapsack
The MKP coefficients are all non-negative integer values
and there are usually few constraints compared to the number of variables.
The MKP is a special case of 0-1 integer programs; it is known to be NP-hard problem. This problem has been widely studied in the literature, and efficient exact and approximate algorithms have been developed for obtaining optimal or near-optimal solutions (the reader is referred to Fréville, 2004; Fréville & Hanafi, 2005, for a comprehensive annotated bibliography). Some very efficient algorithms (Kellerer et al., 2004; Martello & Toth, 1990) exist when m = 1, but as m increases, exact methods usually fail to provide an optimal solution for even moderate size instances.
Hybrid tabu search techniques have been developed for the MKP (Glover & Kochenberger, 1996; Hanafi & Fréville, 1998), and most of the best-known solutions for the set of MKP instances available in the OR-Library (Beasley, 1990) were obtained by Vasquez & Hao (2001) and Vasquez & Vimont (2005). Other recent methods have obtained encouraging results by making a compromise between solution quality and computational effort. For example, Puchinger et al. (2006) proposed an extension of the classic core concept for the MKP (Pisinger, 1995) and also described an extension of the variable neighborhood search metaheuristic (Hansen & Mladenovic, 2001) used with a branch-and-cut algorithm. In addition, Hanafi and Glover (2007) offered an exploitation of nested inequalities and surrogate constraints on the MKP better than that proposed by Osorio et al. (2002), but did not offer computational results.
Akcay et al. (2007) proposed a greedy heuristic based on the effective capacity notion defined as the maximum number of copies of an item that can be accepted if the entire knapsack were to be used for that item alone. Also in Boyer et al. (2009) two heuristics are presented. The first one uses surrogate relaxation where the relaxed problem is solved via a modified dynamic-programming algorithm. The heuristic provides a feasible solution. The second one combines a limited-branch-and-cut procedure with the previous approach, and tries to improve the bound obtained by exploring some nodes that have been rejected by the modified dynamic programming algorithm. Finally, Fleszar and Hindi (2009) proposed several fast and effective heuristics that are based on solving the linear programming relaxation of the problem.