Guillotine Cuts

A combinatorial Benders decomposition approach for the constrained two-dimensional guillotine cutting problem with defects

Abstract

In this paper, we study the constrained two-dimensional guillotine cutting problem with defects, which involves cutting a set of items from a large sheet containing defects while satisfying guillotine constraints. The goal is to maximise the value of the cut items. We propose an exact combinatorial Benders decomposition approach to solve this problem, decomposing it into a master problem and a subproblem. The master problem involves deciding which items to cut and determining the y-coordinates of the cut items. The subproblem is a feasibility problem that identifies a two-dimensional packing, ensuring no overlap and satisfying the guillotine constraints. Valid inequalities and enhanced Benders cuts are applied to strengthen the linear programming relaxation of the master problem. Numerical results on benchmark instances show that our algorithm proves 5,384 optimal solutions out of 5,400 instances. We also compare it with state-of-the-art algorithms in the literature to demonstrate the good performance of the proposed method.

Keywords

Cutting
Guillotine Cuts
Defect
Combinatorial Benders
Exact Algorithm

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

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

2025
2.
Yao, S., Wang, S., Zhang, T., Wei, L.*, & Liu, Q. (2025). A combinatorial Benders decomposition approach for the constrained two-dimensional guillotine cutting problem with defects. International Journal of Production Research, 63(23), 8593–8610.
Abstract
In this paper, we study the constrained two-dimensional guillotine cutting problem with defects, which involves cutting a set of items from a large sheet containing defects while satisfying guillotine constraints. The goal is to maximise the value of the cut items. We propose an exact combinatorial Benders decomposition approach to solve this problem, decomposing it into a master problem and a subproblem. The master problem involves deciding which items to cut and determining the y-coordinates of the cut items. The subproblem is a feasibility problem that identifies a two-dimensional packing, ensuring no overlap and satisfying the guillotine constraints. Valid inequalities and enhanced Benders cuts are applied to strengthen the linear programming relaxation of the master problem. Numerical results on benchmark instances show that our algorithm proves 5,384 optimal solutions out of 5,400 instances. We also compare it with state-of-the-art algorithms in the literature to demonstrate the good performance of the proposed method.
Keywords
Cutting
Guillotine Cuts
Defect
Combinatorial Benders
Exact Algorithm
2025
1.
Wang, S., Baldacci, R., Liu, Q., & Wei, L.* (2025). EATKG: An Open-Source Efficient Exact Algorithm for the Two-Dimensional Knapsack Problem with Guillotine Constraints. European Journal of Operational Research, 327, 735–753. GitHub
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