Material utilization optimization through area-minimized rectangle packing: a reliable and exact piecewise linearization method
Journal
Annals of Operations Research
ISSN
0254-5330
1572-9338
Date Issued
2025-12-23
Author(s)
Fang, Yu-Hsueh
Abstract
Minimizing material consumption is a critical objective in numerous industries, driven by both economic and environmental concerns; particularly, the prices of several materials have fluctuated and increased over the past decade. For many industrial applications, the area-minimized rectangle-packing problem (AMRPP) (or volume-minimized bin-packing problem) plays a pivotal role in achieving this by determining the smallest rectangular area required to contain a set of items, thereby directly reducing material waste. However, the inherent non-linear nature of the AMRPP objective function poses significant computational challenges to finding global optima. This study addresses this challenge by focusing on the logarithmic transformation of the AMRPP objective and introducing an exact piecewise linear function (PWLF) for logarithmic functions. This newly developed PWLF guarantees that the approximation error for the logarithmic terms is within a user-specified tolerance, performing consistently to provide a reliable and exact solution under tolerance for the function approximation itself. Numerical studies show that our proposed PWLF significantly reduces approximation errors compared to state-of-the-art algorithms—by up to 15% for the maximum error. The proposed linearized model also leads to a substantial reduction in total computation time for solving these packing problems—achieving up to a 21% improvement compared to the second-best approach in benchmark instances. This work underscores the practical value of exact PWL techniques in optimizing material utilization through more accurate and efficient solutions to AMRPP, contributing to both economic savings and environmental sustainability.
Subjects
Bin-packing problem
Environmental sustainability
Material utilization
Mixed-integer programming
Piecewise linearization
Publisher
Springer Science and Business Media LLC
Type
journal article