Premium
A Best‐first Branch‐and‐bound Algorithm for Orthogonal Rectangular Packing Problems
Author(s) -
Hifi M.,
Ouafi R.
Publication year - 1998
Publication title -
international transactions in operational research
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.032
H-Index - 52
eISSN - 1475-3995
pISSN - 0969-6016
DOI - 10.1111/j.1475-3995.1998.tb00119.x
Subject(s) - rectangle , heuristic , packing problems , branch and bound , algorithm , set (abstract data type) , computer science , set packing , mathematical optimization , upper and lower bounds , mathematics , mathematical analysis , geometry , programming language
In this paper we discuss the problem of packing a set of small rectangles (pieces) in an enclosing final rectangle. We present first a best‐first branch‐and‐bound exact algorithm and second a heuristic approach in order to solve exactly and approximately this problem. The performances of the proposed approaches are evaluated on several randomly generated problem instances. Computational results show that the proposed exact algorithm is able to solve small and medium problem instances within reasonable execution time. The derived heuristic performs very well in the sense that it produces high‐quality solutions within small computational time.