A SAT-based Method for Solving the Two-dimensional Strip Packing Problem
- 1 January 2010
- journal article
- research article
- Published by SAGE Publications in Fundamenta Informaticae
- Vol. 102 (3-4) , 467-487
Abstract
We propose a satisfiability testing (SAT) based exact approach for solving the two-dimensional strip packing problem (2SPP). In this problem, we are given a set of rectangles and one large rectangle called a strip. The goal of the problem is to pack all rectangles without overlapping, into the strip by minimizing the overall height of the packing. Although the 2SPP has been studied in Operations Research, some instances are still hard to solve. Our method solves the 2SPP by translating it into a SAT problem through a SAT encoding called order encoding. The translated SAT problems tend to be large; thus, we apply several techniques to reduce the search space by symmetry breaking and positional relations of rectangles. To solve a 2SPP, that is, to compute the minimum height of a 2SPP, we need to repeatedly solve similar SAT problems. We thus reuse learned clauses and assumptions from the previously solved SAT problems. To evaluate our approach, we obtained results for 38 instances from the literature and made comparisons with a constraint satisfaction solver and an ad-hoc 2SPP solver.Keywords
This publication has 10 references indexed in Scilit:
- A least wasted first heuristic algorithm for the rectangular packing problemComputers & Operations Research, 2009
- Compiling finite linear CSP into SATConstraints, 2008
- A greedy randomized adaptive search procedure for the point-feature cartographic label placementComputers & Geosciences, 2008
- Reactive GRASP for the strip-packing problemComputers & Operations Research, 2008
- A branch and bound algorithm for the strip packing problemOR Spectrum, 2008
- Chapter 2 Satisfiability Solvers2008
- A competitive and cooperative approach to propositional satisfiabilityDiscrete Applied Mathematics, 2006
- Some experiments with a simple tabu search algorithm for the manufacturer's pallet loading problemComputers & Operations Research, 2006
- A New Placement Heuristic for the Orthogonal Stock-Cutting ProblemOperations Research, 2004
- Temporal Induction by Incremental SAT SolvingElectronic Notes in Theoretical Computer Science, 2003