Improving problem reduction for 0-1 Multidimensional Knapsack Problems with valid inequalities

Publication Type:
Journal Article
Computers and Operations Research, 2016, 71 pp. 82 - 89
Issue Date:
Full metadata record
© 2016 Elsevier Ltd. All rights reserved. This paper investigates the problem reduction heuristic for the Multidimensional Knapsack Problem (MKP). The MKP formulation is first strengthened by the Global Lifted Cover Inequalities (GLCI) using the cutting plane approach. The dynamic core problem heuristic is then applied to find good solutions. The GLCI is described in the general lifting framework and several variants are introduced. A Two-level Core problem Heuristic is also proposed to tackle large instances. Computational experiments were carried out on classic benchmark problems to demonstrate the effectiveness of this new method.
Please use this identifier to cite or link to this item: