Improved Algorithm for Orthogonal Rectangular Packing Problem
In this paper, the authors develop a modified version of the Best First Branch and Bound algorithm (BFBB) proposed for solving exactly the Orthogonal Rectangular Packing problem (ORP). The ORP consists to pack a given set of small rectangles in an enclosing final rectangle. In their proposed version, they introduce a new upper-bound in order to reduce the problem space search. They also propose new strategies that eliminate several duplicate packing patterns. Extensive computational testing on several randomly generated problem instances shows the effectiveness of the proposed algorithm.