Theoretical analysis of integer programming models for the two-dimensional two-staged knapsack problem

Abstract

In this study, we theoretically compare integer programming models for the two-dimensional two-staged knapsack problem. Including the well-known level packing model, we introduce two pattern-based models called the strip packing model and the staged pattern model derived from integer programming models for the two-dimensional two-staged cutting stock problem. We show that the level packing model provides weaker linear programming (LP) relaxation bounds than pattern-based models. Furthermore, we also present upper bounds on the LP-relaxation bound of the level packing model, which can be obtained from the LP-relaxation bounds of the pattern-based models.