Title: Efficient heuristic for very large 0/1 multiple knapsack problems

Authors: Yacine Laalaoui; Hedi Mhalla

Addresses: Department of Information Technology, Taif University, Taif, KSA ' Department of Mathematics and Statistics, The American University of the Middle East, Egaila, Kuwait

Abstract: In this paper, we describe a heuristic that solves very large problem instances (one million items) of the 0/1 multiple knapsack problem. The proposed method is based on IRT heuristic and it is a pure local search technique that attempts to improve within a subset of items instead of the complete set of n items. Each time an interval of items is randomly selected to choose the set of items that can increase the total profit. The experimental work reveals an excellent scalability to solve very large problem instances against IRT and Martelo&Toth heuristic method (MTHM).

Keywords: 0-1 multiple knapsack problems; very large problem instances; swap heuristics; local search.

DOI: 10.1504/IJCSYSE.2015.077065

International Journal of Computational Systems Engineering, 2015 Vol.2 No.2, pp.112 - 120

Received: 18 Sep 2015
Accepted: 22 Nov 2015

Published online: 20 Jun 2016 *

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