Exact Methods for the Generalized Multiple Strip Packing Problem with Heterogeneous Costs
Fuente:
arXiv
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2026
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866911569608179712 |
|---|---|
| author | Lee, Hyunwoo Cheong, Taesu |
| author_facet | Lee, Hyunwoo Cheong, Taesu |
| contents | We study the Generalized Multiple Strip Packing Problem (GMSPP) with heterogeneous per-unit-area costs, in which rectangular items of fixed dimensions must be packed without overlap into multiple open-ended strips of different widths, each incurring a cost proportional to the area used. This cost-weighted area objective is introduced here for the first time and unifies several objectives studied separately in the literature, including total area, total height for identical strips, and makespan. We propose two exact integer programming formulations for this problem: a big-M formulation adapted from recent work, and a normal-position formulation extending an earlier single-strip approach to multiple heterogeneous strips. For the normal-position formulation, we develop an exact Benders decomposition algorithm, called BendM (Benders' Method for Multiple strips). Comprehensive computational experiments on 180 instances derived from standard strip-packing benchmarks compare both formulations and demonstrate the effectiveness of BendM across three cost structures. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2604_04740 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Exact Methods for the Generalized Multiple Strip Packing Problem with Heterogeneous Costs Lee, Hyunwoo Cheong, Taesu Optimization and Control We study the Generalized Multiple Strip Packing Problem (GMSPP) with heterogeneous per-unit-area costs, in which rectangular items of fixed dimensions must be packed without overlap into multiple open-ended strips of different widths, each incurring a cost proportional to the area used. This cost-weighted area objective is introduced here for the first time and unifies several objectives studied separately in the literature, including total area, total height for identical strips, and makespan. We propose two exact integer programming formulations for this problem: a big-M formulation adapted from recent work, and a normal-position formulation extending an earlier single-strip approach to multiple heterogeneous strips. For the normal-position formulation, we develop an exact Benders decomposition algorithm, called BendM (Benders' Method for Multiple strips). Comprehensive computational experiments on 180 instances derived from standard strip-packing benchmarks compare both formulations and demonstrate the effectiveness of BendM across three cost structures. |
| title | Exact Methods for the Generalized Multiple Strip Packing Problem with Heterogeneous Costs |
| topic | Optimization and Control |
| url | https://arxiv.org/abs/2604.04740 |