Solving the Two-dimensional Single Stock Size Cutting Stock Problem with SAT and MaxSAT
The Two-Dimensional Single Stock Size Cutting Stock Problem (2D-CSSP) is a significant challenge in manufacturing, encompassing the task of efficiently cutting rectangular items from stock sheets to fulfill specific demands while minimizing waste. This problem expands on the traditional bin packing approach, necessitating multiple copies of each item type, which leads to complex combinatorial challenges. Recent advancements in SAT (Boolean Satisfiability Problem) and MaxSAT (Maximum Satisfiability Problem) provide promising frameworks for addressing these challenges effectively.
Understanding the 2D-CSSP
The 2D-CSSP requires not only the arrangement of items within a given sheet but also the assignment of each item copy to a specific sheet. This adds layers of complexity, especially when considering non-overlap constraints, which ensure that items do not interfere with one another when placed on the same sheet.
Innovative SAT Framework
The proposed SAT-based framework enhances the problem-solving process by expanding item types according to demand. Each copy of the item is represented by a sheet-assignment variable, and constraints for non-overlapping items are activated solely for those assigned to the same sheet. This strategic approach allows for a more organized and efficient way of tackling the combinatorial explosion inherent in 2D-CSSP.
Infeasible-Orientation Elimination Rule
An important advancement in this research is the introduction of the infeasible-orientation elimination rule. This rule simplifies the problem by fixing rotation variables when only one orientation can fit the sheet, thus reducing unnecessary complexity in the solution space. This contributes significantly to the efficiency of the SAT formulations employed.
Comparative Approaches for Minimizing Sheets
The research compares three different approaches for minimizing the number of sheets required:
- Non-incremental SAT with Binary Search: This method explores the solution space iteratively, allowing for a straightforward determination of the optimal solution.
- Incremental SAT with Clause Reuse: By reusing clauses across different iterations, this approach enhances efficiency and reduces computation time.
- Weighted Partial MaxSAT: This method focuses on maximizing the satisfaction of the constraints while minimizing waste, providing a flexible approach to the problem.
Results and Performance
The results of the study, particularly on the Cui-Zhao benchmark suite, demonstrate a significant improvement in performance. The best configurations of SAT not only certified two to three times more instances as provably optimal but also achieved lower optimality gaps when compared to established solvers such as OR-Tools, CPLEX, and Gurobi.
Conclusion
The findings indicate that the effectiveness of SAT approaches varies based on the presence of rotation. Specifically, incremental SAT outperforms in scenarios without rotation, while non-incremental SAT proves to be more effective as the complexity of rotation increases. This research provides valuable insights and methodologies for future studies aimed at solving complex cutting stock problems using advanced SAT and MaxSAT techniques.