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