.png){kind=icon}
.png){kind=icon}
Return
Material utilization optimization through area-minimized rectangle packing: a reliable and exact piecewise linearization method
.png){kind=icon}
PRE
AI
DOI：10.1007/s10479-025-06995-w.png)
.png){kind=icon}
Original request for help.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
En 中文
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 $$\epsilon $$ , 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.
Keywords:
Material utilization
Bin-packing problem
Piecewise linearization
Mixed-integer programming
Environmental sustainability
Journal
IF:
4.5
Papers:
8.0K
Citations:
2.1W