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

Mahdi Khemakhem, Boukthir Haddar, Khalil Chebil and Saïd Hanafi
Additional contact information
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
Saïd Hanafi: LAMIH, University of Valenciennes, Valenciennes, France

International Journal of Applied Metaheuristic Computing (IJAMC), 2012, vol. 3, issue 4, 43-63

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.

Date: 2012
References: Add references at CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
http://services.igi-global.com/resolvedoi/resolve. ... 4018/jamc.2012100103 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:igg:jamc00:v:3:y:2012:i:4:p:43-63

Access Statistics for this article

International Journal of Applied Metaheuristic Computing (IJAMC) is currently edited by Peng-Yeng Yin

More articles in International Journal of Applied Metaheuristic Computing (IJAMC) from IGI Global
Bibliographic data for series maintained by Journal Editor ().