Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2503.21009 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866915218410438656 |
|---|---|
| author | Lastra-Díaz, Juan J. Ortuño, M. Teresa |
| author_facet | Lastra-Díaz, Juan J. Ortuño, M. Teresa |
| contents | The irregular strip-packing problem consists of the computation of a non-overlapping placement of a set of polygons onto a rectangular strip of fixed width and the minimal length possible. Recent performance gains of the Mixed-Integer Linear Programming (MILP) solvers have encouraged the proposal of exact optimization models for nesting. The Dotted-Board (DB) MILP model solves the discrete version of the nesting problem by constraining the positions of the polygons to be on a grid of fixed points. However, its number of non-overlapping constraints grows exponentially with the number of dots and types of polygons, which encouraged the proposal of a reformulation called the DB Clique Covering (DB-CC) that sets the current state-of-the-art by significantly reducing the constraints required. However, DB-CC requires a significant preprocessing time to compute edge and vertex clique coverings. Moreover, current knowledge of the stable set polytope suggests that achieving a tighter formulation is unlikely. Thus, our hypothesis is that an ad-hoc exact algorithm requiring no preprocessing might be a better option to solve the DB model than the costly Branch-and-Cut approach. This work proposes an exact branch-and-bound-and-prune algorithm to solve the DB model from the conflict inverse graph based on ad-hoc data structures, bounding, and forward-checking for pruning the search space. We introduce two 0-1 ILP DB reformulations with discrete rotations and a new lower-bound algorithm as by-products. Our experiments show that DB-PB significantly reduces the resolution time compared to our replication of the DB-CC model. Seventeen open instances are solved up to optimality. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2503_21009 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | A parallel branch-and-bound-and-prune algorithm for irregular strip packing with discrete rotations Lastra-Díaz, Juan J. Ortuño, M. Teresa Optimization and Control The irregular strip-packing problem consists of the computation of a non-overlapping placement of a set of polygons onto a rectangular strip of fixed width and the minimal length possible. Recent performance gains of the Mixed-Integer Linear Programming (MILP) solvers have encouraged the proposal of exact optimization models for nesting. The Dotted-Board (DB) MILP model solves the discrete version of the nesting problem by constraining the positions of the polygons to be on a grid of fixed points. However, its number of non-overlapping constraints grows exponentially with the number of dots and types of polygons, which encouraged the proposal of a reformulation called the DB Clique Covering (DB-CC) that sets the current state-of-the-art by significantly reducing the constraints required. However, DB-CC requires a significant preprocessing time to compute edge and vertex clique coverings. Moreover, current knowledge of the stable set polytope suggests that achieving a tighter formulation is unlikely. Thus, our hypothesis is that an ad-hoc exact algorithm requiring no preprocessing might be a better option to solve the DB model than the costly Branch-and-Cut approach. This work proposes an exact branch-and-bound-and-prune algorithm to solve the DB model from the conflict inverse graph based on ad-hoc data structures, bounding, and forward-checking for pruning the search space. We introduce two 0-1 ILP DB reformulations with discrete rotations and a new lower-bound algorithm as by-products. Our experiments show that DB-PB significantly reduces the resolution time compared to our replication of the DB-CC model. Seventeen open instances are solved up to optimality. |
| title | A parallel branch-and-bound-and-prune algorithm for irregular strip packing with discrete rotations |
| topic | Optimization and Control |
| url | https://arxiv.org/abs/2503.21009 |