Consecutive Ones Matrices for Multi‐dimensional Orthogonal Packing Problems

The multi‐dimensional orthogonal packing problem (OPP) is a well studied decisional problem. Given a set of items with rectangular shapes, the problem is to decide whether there is a non‐overlapping packing of these items in a rectangular bin. The rotation of items is not allowed. A powerful caracterization of packing configurations by means of interval graphs was recently introduced. In this paper, we propose a new algorithm using consecutive ones matrices as data structure. This new algorithm is then used to solve the two‐dimensional orthogonal knapsack problem. Computational results are reported, which show its effectiveness.