A Combinatorial Benders Decomposition Framework for Two-Dimensional Irregular Bin Packing Problems with Convex Polygons
Abstract
Two-dimensional irregular bin packing combines combinatorial bin-assignment decisions with difficult geometric feasibility constraints, making exact optimization challenging. This paper develops an exact combinatorial Benders decomposition framework for the two-dimensional irregular bin packing problem with convex polygons, coupling a pattern-based master problem with an exact single-bin geometric feasibility oracle. The dynamically strengthened Benders master is solved by a tailored exact branch-and-price procedure that incorporates objective-layered search and adaptive exact pricing. Geometric information obtained from the oracle is further fed back to the master and pricing processes through dynamically generated Benders feasibility cuts, which progressively restrict the subsequent pricing problems. Computational experiments are conducted on 540 benchmark instances from 18 classes. The proposed method obtains the optimal solution for 318 instances across 12 classes within a 3600-second time limit. On these classes, the proposed method solves more instances than a direct mixed-integer programming formulation and a baseline combinatorial Benders decomposition approach.
Related
- A Combinatorial Formula and a Hilbert Scheme Realization of a Rank-One Virasoro Irregular Conformal Block
- PAR2COX: Survival-Informed Tensor Decomposition for Phenotyping and Risk Prediction from Irregular Longitudinal Data
- A Highly Scalable Quantized Tensor-Train FDTD Framework for the Simulation of Three-Dimensional Electromagnetic Scattering Problems
- Weekly sales forecasting using time series decomposition with irregular seasonality: A case study of Sony TV sales in the United States
- Combinatorial slicing problems of polytopes: How (not) to reconstruct a polytope from its slices
BibTeX
@misc{wang2026combinatorial,
title = {{A Combinatorial Benders Decomposition Framework for Two-Dimensional Irregular Bin Packing Problems with Convex Polygons}},
author = {Jianming Wang and Zhouwang Yang},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.23461},
eprint = {2609.23461},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.23461},
}
RIS
TY - UNPB
TI - A Combinatorial Benders Decomposition Framework for Two-Dimensional Irregular Bin Packing Problems with Convex Polygons
AU - Jianming Wang
AU - Zhouwang Yang
PY - 2026
DA - 2026/09/20
PB - arXiv
DO - 10.48550/arxiv.2609.23461
UR - https://arxiv.org/abs/2609.23461
AB - Two-dimensional irregular bin packing combines combinatorial bin-assignment decisions with difficult geometric feasibility constraints, making exact optimization challenging. This paper develops an exact combinatorial Benders decomposition framework for the two-dimensional irregular bin packing problem with convex polygons, coupling a pattern-based master problem with an exact single-bin geometric feasibility oracle. The dynamically strengthened Benders master is solved by a tailored exact branch-and-price procedure that incorporates objective-layered search and adaptive exact pricing. Geometric information obtained from the oracle is further fed back to the master and pricing processes through dynamically generated Benders feasibility cuts, which progressively restrict the subsequent pricing problems. Computational experiments are conducted on 540 benchmark instances from 18 classes. The proposed method obtains the optimal solution for 318 instances across 12 classes within a 3600-second time limit. On these classes, the proposed method solves more instances than a direct mixed-integer programming formulation and a baseline combinatorial Benders decomposition approach.
ER -