Very Large-Scale Neighborhood Search for the K-Constraint Multiple Knapsack Problem

The K-Constraint Multiple Knapsack Problem (K-MKP) is a generalization of the multiple knapsack problem, which is one of the representative combinatorial optimization problems known to be NP-hard. In K-MKP, each item has K types of weights and each knapsack has K types of capacity. In this paper, we...

Full description

Saved in:
Bibliographic Details
Published in:Journal of heuristics 2005-12, Vol.11 (5-6), p.465-481
Main Authors: Ahuja, Ravindra K., Cunha, Claudio B.
Format: Article
Language:English
Subjects:
Algorithms
Capital budgeting
Capital expenditures
Heuristic
Knapsack problem
Linear programming
Neighborhoods
Optimization techniques
Studies
Systems engineering
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:The K-Constraint Multiple Knapsack Problem (K-MKP) is a generalization of the multiple knapsack problem, which is one of the representative combinatorial optimization problems known to be NP-hard. In K-MKP, each item has K types of weights and each knapsack has K types of capacity. In this paper, we propose several very large-scale neighborhood search (VLSN) algorithms to solve K-MKP. One of the VLSN algorithms incorporates a novel approach that consists of randomly perturbing the current solution in order to efficiently produce a set of simultaneous non-profitable moves. These moves would allow several items to be transferred from their current knapsacks and assigned to new knapsacks, which makes room for new items to be inserted through multi-exchange movements and allows for improved solutions. Computational results presented show that the method is effective, and provides better solutions compared to exact algorithms run for the same amount of time. [PUBLICATION ABSTRACT]
ISSN:1381-1231
1572-9397
DOI:10.1007/s10732-005-2634-9