A Filter-and-Fan Metaheuristic for the 0-1 Multidimensional Knapsack Problem

A Filter-and-Fan Metaheuristic for the 0-1 Multidimensional Knapsack Problem

Mahdi Khemakhem, Boukthir Haddar, Khalil Chebil, Saïd Hanafi
Copyright: © 2012 |Pages: 21
DOI: 10.4018/jamc.2012100103
(Individual Articles)
No Current Special Offers


This paper proposes a new hybrid tree search algorithm to the Multidimensional Knapsack Problem (MKP) that effectively combines tabu search with a dynamic and adaptive neighborhood search procedure. The authors’ heuristic, based on a filter-and-fan (F&F) procedure, uses a Linear Programming-based Heuristic to generate a starting solution to the F&F process. A tabu search procedure is used to try to enhance the best solution value provided by the F&F method that generates compound moves by a strategically truncated form of tree search. They report the first application of the F&F method to the MKP. Experimental results obtained on a wide set of benchmark problems clearly demonstrate the competitiveness of the proposed method compared to the state-of-the-art heuristic methods.
Article Preview

1. Introduction

In this paper we are dealing with the 0-1 Multidimensional Knapsack Problem (MKP) which can be formulated as follows:

where jamc.2012100103.m02 is the number of items and jamc.2012100103.m03 is the number of knapsack constraints with capacitiesjamc.2012100103.m04 Each item jamc.2012100103.m05yields jamc.2012100103.m06 units of profit and consumes a given amount of resource jamc.2012100103.m07 for each knapsackjamc.2012100103.m08 The MKP coefficients are all non-negative integer values jamc.2012100103.m09 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.

Complete Article List

Search this Journal:
Volume 15: 1 Issue (2024)
Volume 14: 1 Issue (2023)
Volume 13: 4 Issues (2022): 2 Released, 2 Forthcoming
Volume 12: 4 Issues (2021)
Volume 11: 4 Issues (2020)
Volume 10: 4 Issues (2019)
Volume 9: 4 Issues (2018)
Volume 8: 4 Issues (2017)
Volume 7: 4 Issues (2016)
Volume 6: 4 Issues (2015)
Volume 5: 4 Issues (2014)
Volume 4: 4 Issues (2013)
Volume 3: 4 Issues (2012)
Volume 2: 4 Issues (2011)
Volume 1: 4 Issues (2010)
View Complete Journal Contents Listing