Track papers across labs, topics, and trends.
Search papers, labs, and topics across Lattice.
This paper tackles the Two-Dimensional Single Stock Size Cutting Stock Problem (2D-CSSP) by formulating it as a SAT problem, expanding item types by demand and activating non-overlap constraints only for items on the same sheet. They introduce an infeasible-orientation elimination rule to fix rotation variables. They compare non-incremental SAT with binary search, incremental SAT with clause reuse, and weighted partial MaxSAT for minimizing the number of sheets, demonstrating superior performance compared to OR-Tools, CPLEX, and Gurobi on the Cui-Zhao benchmark.
SAT solvers can now outperform traditional optimization tools like CPLEX and Gurobi on the notoriously hard 2D-CSSP, especially when combined with problem-specific symmetry breaking.
Cutting rectangular items from stock sheets to satisfy demands while minimizing waste is a central manufacturing task. The Two-Dimensional Single Stock Size Cutting Stock Problem (2D-CSSP) generalizes bin packing by requiring multiple copies of each item type, which causes a strong combinatorial blow-up. We present a SAT-based framework where item types are expanded by demand, each copy has a sheet-assignment variable and non-overlap constraints are activated only for copies assigned to the same sheet. We also introduce an infeasible-orientation elimination rule that fixes rotation variables when only one orientation can fit the sheet. For minimizing the number of sheets, we compare three approaches: non-incremental SAT with binary search, incremental SAT with clause reuse across iterations and weighted partial MaxSAT. On the Cui--Zhao benchmark suite, our best SAT configurations certify two to three times more instances as provably optimal and achieve lower optimality gaps than OR-Tools, CPLEX and Gurobi. The relative ranking among SAT approaches depends on rotation: incremental SAT is strongest without rotation, while non-incremental SAT is more effective when rotation increases formula size.