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

• Propose a dynamic core problem heuristic strengthened by valid inequalities for MKP.
• Describe the Global Lifted Cover Inequalities (GLCI) in the general lifting framework.
• Design a Two-level Core problem Heuristic to tackle large problems.

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.