Exact Algorithms for Two-Dimensional Knapsack Problems: A Unified Framework with New Benchmark Results

This paper investigates two-dimensional knapsack problems modeled as the Generalized Two-Dimensional Knapsack Problem (G2KP), a variant not previously studied in the literature. The importance of the G2KP lies in its crucial role in designing Branch-Price-and-Cut (BPC) algorithms for the classical Two-Dimensional Bin-Packing Problem. We propose a novel and effective exact solution framework that incorporates both nonnumerically exact and numerically exact algorithms tailored to G2KP. The framework also achieves state-of-the-art performance on the well-known Two-Dimensional Knapsack Problem (with and without item conflicts) and the Two-Dimensional Orthogonal Packing Problem, solving several previously unsolved instances and establishing new benchmark results. These findings highlight the framework’s potential to inspire algorithmic developments for pricing problems in related BPC methods and higher-dimensional packing problems. To support future research, we make the algorithm code, instance data, and detailed results publicly available.

History: Accepted by Andrea Lodi, Area Editor for Design & Analysis of Algorithms–Discrete.

Funding: This study was supported by the Natural Science Foundation of China [Grants 72271062, 72671084, and 52575565], Science and Technology Projects in Guangzhou [Grant 2024A04J01019], and the Province Natural Science Fund of Guangdong [Grants 2025A1515011297 and 2024A1515010246].

Supplemental Material: The software that supports the findings of this study is available within the paper and its Supplemental Information (https://pubsonline.informs.org/doi/suppl/10.1287/ijoc.2025.1423) as well as from the IJOC GitHub software repository (https://github.com/INFORMSJoC/2025.1423). The complete IJOC Software and Data Repository is available at https://informsjoc.github.io/.