Global optimization for the three-dimensional open-dimension rectangular packing problem

Publication Type:
Journal Article
Engineering Optimization, 2018, 50 (10), pp. 1789 - 1809
Issue Date:
Full metadata record
© 2017, © 2017 Informa UK Limited, trading as Taylor & Francis Group. 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.
Please use this identifier to cite or link to this item: