💻 computer science

Solving the Two-dimensional single stock size Cuting Stock Problem with SAT and MaxSAT

This paper presents a SAT-based framework for the Two-Dimensional Single Stock Size Cutting Stock Problem that utilizes demand expansion, orientation elimination, and various solving strategies to significantly outperform commercial solvers like OR-Tools, CPLEX, and Gurobi in certifying optimality and reducing gaps on benchmark instances.

Original authors: Tuyen Van Kieu, Chi Linh Hoang, Khanh Van To

Published 2026-04-03

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Tuyen Van Kieu, Chi Linh Hoang, Khanh Van To

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you run a massive furniture factory. Every day, you receive a huge order: 50 tables, 30 chairs, and 20 bookshelves. You have a warehouse full of identical, giant sheets of plywood. Your goal? Cut all those items out of the fewest number of sheets possible to save money and reduce waste.

This is the Two-Dimensional Single Stock Size Cutting Stock Problem (2D-CSSP). It sounds simple, but it's a nightmare for computers. Why? Because if you have 50 tables, the computer has to figure out not just where to put them, but which of the 50 identical tables goes where. The number of possibilities explodes like a popcorn machine set to "nuclear."

This paper introduces a new way to solve this puzzle using a type of logic engine called SAT (Boolean Satisfiability). Here is the breakdown of their solution, explained with everyday analogies.

1. The Old Way vs. The New Way

The Old Way (Commercial Solvers): Imagine trying to solve this puzzle by asking a super-smart but very literal robot, "Can I fit 50 tables on 10 sheets?" The robot tries, fails, and says "No." Then you ask, "How about 11 sheets?" It tries again. This is slow, and often the robot gets stuck in a loop, unable to prove it found the absolute best answer, only a "good enough" one.
The New Way (The SAT Approach): The authors built a custom logic engine that treats the problem like a massive game of Logic Sudoku. Instead of just guessing numbers, the engine builds a set of strict rules (clauses) that describe the physical world: "If Table A is here, Table B cannot be there."

2. The Secret Sauce: "Conditional" Rules

The biggest breakthrough in this paper is how they handle the "copy" problem.

The Problem: If you have 50 identical chairs, the computer usually treats them as 50 unique individuals, creating a massive mess of rules.
The Solution: The authors realized that you only need to worry about two chairs bumping into each other if they are on the same sheet of plywood.
- Analogy: Imagine you are organizing a party. You don't need to worry if the guest in Room 1 bumps into the guest in Room 100. You only care if they are in the same room.
- The new engine only activates the "don't bump" rules when two items are assigned to the same sheet. This keeps the logic clean and manageable.

3. The "Smart" Shortcuts (Symmetry Breaking)

When you have 50 identical chairs, it doesn't matter if Chair #1 is on the left and Chair #2 is on the right, or vice versa. They look the same.

The Problem: The computer wastes hours checking both scenarios, thinking they are different.
The Solution: The authors added "Symmetry Breaking" rules.
- Analogy: It's like telling a librarian, "If you have two identical books, always put the one with the lower number on the left shelf." This forces the computer to ignore duplicate scenarios and focus only on unique arrangements.
The "Rotation" Trick: They also added a rule that says, "If a chair is too tall to fit sideways, but fits standing up, force it to stand up." This eliminates impossible options before the computer even starts thinking about them.

4. Three Strategies to Find the Best Answer

The team tested three different ways to use their logic engine to find the minimum number of sheets:

The Binary Search (Non-Incremental): Like guessing a number between 1 and 100. "Is it 50? No. Is it 25? Yes. Is it 12?" It's fast but throws away all its work every time it guesses a new number.
The Memory Keeper (Incremental SAT): This is the winner for most cases. Imagine a detective solving a mystery. If they prove a suspect is innocent on Monday, they remember that fact on Tuesday.
- When the computer tries to fit items on 10 sheets and fails, it learns why it failed (e.g., "These three wide items can never fit together"). When it tries 11 sheets, it remembers that lesson immediately. It doesn't start from scratch; it builds on its previous failures.
The One-Shot Wager (MaxSAT): This tries to solve for the perfect number in a single giant leap. It's powerful but sometimes gets overwhelmed by the sheer size of the math, like trying to eat a whole pizza in one bite.

5. The Results: Who Won?

The authors tested their system against the world's best commercial software (like Google OR-Tools, CPLEX, and Gurobi) using 30 difficult real-world puzzles.

The Verdict: Their new SAT-based system was a dominant champion.
- Proof of Perfection: While the commercial software could often find a "good" solution, they frequently couldn't prove it was the absolute best. The new SAT system proved the optimal solution for 2 to 3 times more puzzles than the commercial giants.
- Efficiency: It found better solutions with less waste (lower "optimality gap").
- The Twist: Interestingly, the "Memory Keeper" (Incremental) approach was the best when items couldn't be rotated. But when items could be rotated (making the math much bigger), the "Binary Search" approach actually performed better because the memory became too cluttered with too many rules.

The Takeaway

This paper shows that by treating a manufacturing problem as a pure logic puzzle and using "memory" to learn from past mistakes, we can solve complex cutting problems much faster and more accurately than traditional methods. It's like upgrading from a calculator that just adds numbers to a super-intelligent assistant that understands the story of the puzzle.

In short: They built a smarter, more logical way to cut plywood that saves money, reduces waste, and proves it's the best possible way every single time.

1. Problem Definition

The paper addresses the Two-Dimensional Single Stock Size Cutting Stock Problem (2D-CSSP).

Objective: Cut a set of rectangular items from identical raw stock sheets to satisfy specific demands while minimizing the total number of sheets used.
Input: A list of item types $T = \{(w_t, h_t, d_t)\}$ , where $w_t$ and $h_t$ are dimensions and $d_t$ is the demand (number of copies required). The sheet size is $W \times H$ .
Complexity: The problem is NP-hard. It generalizes the Two-Dimensional Bin Packing Problem (2D-BPP). The specific challenge in 2D-CSSP is the multiplicative effect of demands: if an item type has a high demand, it creates many identical copies, leading to a massive search space and significant symmetry (interchangeability of identical copies).
Constraints: Items must be placed without overlap, within sheet boundaries, and may optionally be rotated by 90 degrees.

2. Methodology

The authors propose a SAT-based framework that encodes the problem into Boolean Satisfiability (SAT) and Weighted Partial MaxSAT.

A. SAT Encoding Strategy

Unlike traditional Mixed Integer Programming (MIP) which scales poorly with high demands, the SAT approach uses:

Demand Expansion: Instead of treating item types as abstract variables, the demands are expanded. If item type $t$ has demand $d_t$ , it is treated as $d_t$ distinct copies ( $c_{t,1}, \dots, c_{t,d_t}$ ).
Variables:
- Sheet Assignment ( $s_{c,j}$ ): Boolean variable indicating if copy $c$ is assigned to sheet $j$ .
- Coordinates (Order Encoding): Uses order encoding for $x_c$ and $y_c$ to keep the number of variables linear relative to sheet dimensions.
- Rotation ( $R_c$ ): Boolean flag for 90-degree rotation.
- Relative Position: Variables for "left of" and "below" relationships.
Conditional Non-Overlap Constraints: This is the core innovation. Non-overlap constraints are conditional on sheet assignment.
- Standard encodings enforce non-overlap for all pairs.
- This encoding enforces non-overlap only if two copies are assigned to the same sheet ( $\neg s_{c,j} \lor \neg s_{c',j} \lor \text{non-overlap}$ ). This drastically reduces the number of active constraints for copies on different sheets.
Symmetry Breaking: To handle the combinatorial blow-up from identical copies, four rules are applied:
- Large Item Constraints: Fix relative positions if items cannot fit side-by-side.
- Same-Size Ordering: Enforce a strict ordering among copies of the same type to break permutation symmetry.
- Infeasible-Orientation Elimination: If an item fits in a sheet in only one orientation (due to dimensions), the rotation variable is fixed immediately.
- Sheet Ordering: Sheets are used in index order (1, 2, 3...) to eliminate $k!$ relabeling symmetries.

B. Solving Approaches

The paper compares three strategies to find the minimum number of sheets ( $k$ ):

Non-Incremental SAT with Binary Search: Rebuilds the SAT formula from scratch for each candidate $k$ using binary search.
Incremental SAT with Binary Search: Builds the formula for the upper bound ($UB$) once. It uses solver assumptions to "disable" sheets beyond the current test $k$ . Crucially, conflict clauses learned during failed attempts (UNSAT) are retained and reused for subsequent iterations, pruning the search space effectively.
Weighted Partial MaxSAT: Encodes the problem as a single optimization task where minimizing the number of used sheets is a soft objective.

3. Key Contributions

First SAT Encoding for 2D-CSSP: The authors present the first declarative logic-based formulation for this specific problem, addressing the unique challenge of demand-induced symmetries and conditional constraints.
Infeasible-Orientation Rule: A generalized rule that fixes rotation variables when only one orientation fits the sheet, extending previous work on strip packing.
Empirical Analysis of Solving Strategies: The study reveals that the optimal SAT strategy depends on the problem structure:
- Without Rotation: Incremental SAT is superior because conflict clauses learned from geometric impossibilities (e.g., "three wide items cannot fit on one sheet") remain valid across different sheet counts.
- With Rotation: Non-Incremental SAT performs better. Rotation increases the formula size significantly (clauses grow ~3x), causing the clause database in incremental solving to become too large with "noise," diluting the benefit of clause reuse.
Comprehensive Benchmarking: A large-scale comparison against industrial solvers (OR-Tools, CPLEX, Gurobi) on the Cui–Zhao benchmark suite.

4. Experimental Results

The experiments were conducted on 30 instances from the Cui–Zhao suite (7–21 item types, demands up to 45) with a 1,800-second time limit.

Optimality Certification:
- SAT Approach: Certified optimality for 16 instances (no rotation) and 18 instances (with rotation).
- Commercial Solvers: The best commercial solver (OR-Tools CP) certified only 7 instances (no rotation) and 6 instances (with rotation).
- Result: The SAT approach certified 2 to 3 times more instances as provably optimal than any commercial solver.
Optimality Gaps:
- The SAT approach achieved significantly lower gaps (e.g., 3.24% with rotation vs. 4.63% for OR-Tools).
- MIP solvers (CPLEX, Gurobi) struggled with gaps >13% and certified very few instances.
Performance Nuances:
- OR-Tools CP was often fast at finding feasible solutions matching the Best Known Solution (BKS) but failed to prove optimality.
- SAT solvers provided strong optimality certificates via the CDCL (Conflict-Driven Clause Learning) engine.
- Incremental SAT was the fastest for compact formulas (no rotation), while Non-Incremental SAT was more robust when rotation expanded the search space.

5. Significance

This paper demonstrates that SAT-based methods are highly competitive, and often superior, to state-of-the-art commercial MIP and CP solvers for the 2D Cutting Stock Problem, particularly when item demands are high.

Theoretical Impact: It bridges the gap between geometric packing and Boolean satisfiability, showing how CDCL engines can effectively exploit demand structures (identical copies) through clause reuse and conditional constraints.
Practical Impact: For manufacturing industries (steel, glass, textiles), the ability to prove optimality on more instances than current commercial tools is a major advancement. It allows manufacturers to guarantee minimal waste rather than relying on heuristics.
Future Directions: The authors suggest exploring tighter lower bounds, hybrid column-generation approaches where SAT solves the pricing sub-problem, and extending the framework to heterogeneous stock sizes.

In summary, the paper establishes a new state-of-the-art for 2D-CSSP, proving that tailored SAT encodings can outperform general-purpose industrial solvers in both solution quality and optimality certification.