arbiter
JournalsPricingAccount

EFFICIENT SAT AND MAXSAT TECHNIQUES FOR SOLVING THE TWO-DIMENSIONAL STRIP PACKING PROBLEM

Tuyen Van Kieu et al.

Pesquisa Operacional2025https://doi.org/10.1590/0101-7438.2025.045.00297231article
AJG 1
Weight
0.50

What the paper says

The NP-hard Two-Dimensional Strip Packing Problem (2SPP) demands efficient exact solutions. This paper presents SAT-based Order Encoding models incorporating item rotation and adapted symmetry-breaking (SB). It compares three height-minimization strategies: Non-Incremental SAT Bisection, Incremental SAT Bisection, and Direct MaxSAT Optimization. Benchmarks on established 2SPP instances show our Non-Incremental SAT and Direct MaxSAT strategies significantly outperform earlier incremental techniques. Direct MaxSAT excelled for non-rotational 2SPP, while Non-Incremental SAT was superior for rotational cases among our methods. Google CP-SAT, integrated into our Non-Incremental Bisection search framework, performed best overall. Nevertheless, our specialized SAT/MaxSAT methods were highly competitive, outperforming other CP and MIP solvers. SB was generally beneficial. Item rotation increased encoding complexity; while yielding improved optimal heights for some instances, it did not increase the total number of instances solved optimally by our SAT/MaxSAT methods. This work offers insights into SAT/MaxSAT strategy trade-offs and their performance against general solvers.

Open paper page →

Cite this paper

https://doi.org/https://doi.org/10.1590/0101-7438.2025.045.00297231

Or copy a formatted citation

@article{tuyen2025,
  title        = {{EFFICIENT SAT AND MAXSAT TECHNIQUES FOR SOLVING THE TWO-DIMENSIONAL STRIP PACKING PROBLEM}},
  author       = {Tuyen Van Kieu et al.},
  journal      = {Pesquisa Operacional},
  year         = {2025},
  doi          = {https://doi.org/https://doi.org/10.1590/0101-7438.2025.045.00297231},
}

Paste directly into BibTeX, Zotero, or your reference manager.

Flag this paper

EFFICIENT SAT AND MAXSAT TECHNIQUES FOR SOLVING THE TWO-DIMENSIONAL STRIP PACKING PROBLEM

Flags are reviewed by the Arbiter methodology team within 5 business days.

Evidence weight

0.50

Balanced mode · F 0.40 / M 0.15 / V 0.05 / R 0.40

F · citation impact0.50 × 0.4 = 0.20
M · momentum0.50 × 0.15 = 0.07
V · venue signal0.50 × 0.05 = 0.03
R · text relevance †0.50 × 0.4 = 0.20

† Text relevance is estimated at 0.50 on the detail page — for your query’s actual relevance score, open this paper from a search result.