A new exact method for the two-dimensional orthogonal packing problem |
| |
Authors: | Franç ois Clautiaux,Jacques CarlierAziz Moukrim |
| |
Affiliation: | Laboratoire HeuDiaSyC, UMR CNRS 6599, Université de Technologie de Compiègne, BP 20529, 60205 Compiègne, France |
| |
Abstract: | The two-dimensional orthogonal packing problem (2OPP) consists in determining if a set of rectangles (items) can be packed into one rectangle of fixed size (bin). In this paper we propose two exact algorithms for solving this problem. The first algorithm is an improvement on a classical branch&bound method, whereas the second algorithm is based on a new relaxation of the problem. We also describe reduction procedures and lower bounds which can be used within enumerative methods. We report computational experiments for randomly generated benchmarks which demonstrate the efficiency of both methods: the second method is competitive compared to the best previous methods. It can be seen that our new relaxation allows an efficient detection of non-feasible instances. |
| |
Keywords: | Two-dimensional orthogonal packing problem Open-dimension packing problem Cutting and packing Exact method Branch& bound |
本文献已被 ScienceDirect 等数据库收录! |