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.
The authors would like to thank the Institute for Industrial Systems Innovation of Seoul National University for the administrative support. This work was supported by the National Research Foundation of Korea (NRF) grant funded by the Korean government (No. 2021R1A2C2005531).
