EATKG: An Open-Source Efficient Exact Algorithm for the Two-Dimensional Knapsack Problem with Guillotine Constraints

Sunkanghong Wang, Roberto Baldacci, Qiang Liu and Lijun Wei

European Journal of Operational Research, 2025, vol. 327, issue 3, 735-753

Abstract: This paper addresses the Two-Dimensional Knapsack Problem with Guillotine Constraints, which is a famous NP-hard problem and is commonly encountered in industries where rectangular raw materials are cut into smaller pieces using guillotine cuts. We propose an efficient exact algorithm (EATKG) to solve this problem, which incorporates advanced techniques and novel elements, including an adapted preprocessing procedure, two enhanced upper bounds, an improved bidirectional tree search approach, and an iterative combination enumeration process. These components effectively balance the computation of upper and lower bounds and handle the issue of memory overflow. We extensively evaluate EATKG on eight classic benchmark sets, comprising 1,277 instances. Our algorithm solves 87% of the instances with an average computing time of 7 seconds, and 93% with an average computing time of 49 seconds. Moreover, EATKG efficiently solves nearly all small- and medium-sized instances, providing better solutions for 46 instances and tighter upper bounds for 109 instances. These results demonstrate the superior performance of our algorithm compared to leading algorithms. To support future research, we have made the source code for the proposed algorithm, along with the corresponding instance data, aggregated results, and detailed solutions, publicly available. This will facilitate further investigations and comparisons of solution methods.

Keywords: Cutting and packing; Two-dimensional knapsack; Guillotine cuts; Exact algorithm; Bidirectional tree search (search for similar items in EconPapers)
Date: 2025
References: Add references at CitEc
Citations:

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0377221725004175
Full text for ScienceDirect subscribers only

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:eee:ejores:v:327:y:2025:i:3:p:735-753

DOI: 10.1016/j.ejor.2025.05.033

Access Statistics for this article

European Journal of Operational Research is currently edited by Roman Slowinski, Jesus Artalejo, Jean-Charles. Billaut, Robert Dyson and Lorenzo Peccati

More articles in European Journal of Operational Research from Elsevier
Bibliographic data for series maintained by Catherine Liu ().