Title: Hybrid algorithms for the Multiple-choice Multi-dimensional Knapsack Problem

Authors: Nawal Cherfi, Mhand Hifi

Addresses: CERMSEM, CNRS UMR 8095, MSE, Universite Paris 1, 106-112, bd de l'Hopital, 75013 Paris, France. ' Universite de Picardie Jules Verne, MIS, Axe–Discrete Optimization and Re-optimization, 5 rue du Moulin Neuf, 80000 Amiens, France

Abstract: In this paper, we propose three versions of an algorithm for approximately solving large-scale Multiple-choice Multi-dimensional Knapsack Problems (MMKP). First, an adaptation of the local branching is proposed. Second, a hybrid solution procedure is presented that is based on two complementary solution procedures: a local branching which cooperates with a column generation solution procedure. Third and last, an augmented algorithm of the last hybrid algorithm is developed. It can also be viewed as a special truncated branch and bound in which the first hybrid algorithm is applied to a subset of elite nodes generated according to some variables/constraint branchings. The proposed methods are analysed computationally on a set of instances of the literature and compared to the results provided by other algorithms of the literature. Encouraging results have been obtained.

Keywords: branch-and-bound; column generation; heuristics; knapsack problem; local branching; optimisation; multiple choice; hybrid algorithms.

DOI: 10.1504/IJOR.2009.024531

International Journal of Operational Research, 2009 Vol.5 No.1, pp.89 - 109

Published online: 08 Apr 2009 *

Full-text access for editors Full-text access for subscribers Purchase this article Comment on this article