Theoretical analysis of integer programming models for the two-dimensional two-staged knapsack problem - Kang, Suho; Kim, Junyoung; Joung, Seulgi; Lee, Kyungsik (Optimization Letters, 2025)
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.
Keywords: Integer programming models; Knapsack problems; Level packing model; Linear programming relaxation; Packing models; Staged pattern model; Strip packing; Strip packing model; Two-dimensional; Two-dimensional two-staged knapsack problem; Integer programming models; Level packing model; LP-relaxation; Staged pattern model; Strip packing model; Two-dimensional two-staged knapsack problem