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 (LOGIQ – ISGI, University of Sfax, Sfax, Tunisia), Boukthir Haddar (LOGIQ – ISGI, University of Sfax, Sfax, Tunisia), Khalil Chebil (LOGIQ – ISGI, University of Sfax, Sfax, Tunisia) and Saïd Hanafi (LAMIH, University of Valenciennes, Valenciennes, France)
Copyright: © 2012 |Pages: 21
DOI: 10.4018/jamc.2012100103
OnDemand PDF Download:
$30.00
List Price: $37.50

Abstract

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 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.

Complete Article List

Search this Journal:
Reset
Open Access Articles: Forthcoming
Volume 9: 4 Issues (2018): 1 Released, 3 Forthcoming
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