| Article ID: | iaor20123456 |
| Volume: | 11 |
| Issue: | 1 |
| Start Page Number: | 3 |
| End Page Number: | 22 |
| Publication Date: | Mar 2012 |
| Journal: | Journal of Mathematical Modelling and Algorithms |
| Authors: | Pcher Arnaud, Joncour Cdric, Valicov Petru |
| Keywords: | bin packing, trees |
Given a set of rectangular items of different sizes and a rectangular container, the aim of the bi‐dimensional Orthogonal Packing Problem (OPP‐2 for short) is to decide whether there exists a non‐overlapping packing of the items in this container. The rotation of items is not allowed. In this paper we present a new exact algorithm for solving OPP‐2, based upon the characterization of solutions using interval graphs proposed by Fekete and Schepers. The algorithm uses MPQ‐trees, which were introduced by Korte and Möhring to recognize interval graphs.