Global optimization for the three-dimensional open-dimension rectangular packing problem. Issue 10 (3rd October 2018)

• Record Type: Journal Article
• Authors: Huang, Yao-Huei; Hwang, F. J.
• Is Part Of: Engineering optimization. Volume 50:Issue 10(2018)
• Page Start: 1789
• Page End: 1809
• Publication Date: 2018-10-03
• Subjects: Rectangular packing problem -- global optimization -- exact method -- mixed-integer linear program; Engineering design -- Periodicals; Mathematical optimization -- Periodicals; 620.0042
• DOI: 10.1080/0305215X.2017.1411484
• Languages: English
• ISSNs: 0305-215X

Abstract

ABSTRACT: This article addresses the three-dimensional open-dimension rectangular packing problem (3D-ODRPP), which aims to pack a given set of unequal-size rectangular boxes within an enveloping rectangular space such that the volume of the occupied space is minimized. Even though the studied 3D-ODRPP is NP hard, the development of sophisticated global optimization methods has been stimulated. The mathematical programming formulation for the 3D-ODRPP has evolved into an effective and efficient mixed-integer linear programming (MILP) model. This study proposes an advanced exact scheme yielding a guaranteed global optimal solution given that all the instance data are non-negative rational numbers. The developed MILP retains not only fewer variables but also fewer constraints than the state-of-the-art models. The superior effectiveness and efficiency of the developed scheme are demonstrated with numerical experiments, where two sets of benchmark instances from references, real-world instances and instances with rational data are included.