Consecutive ones matrices for multi-dimensional orthogonal packing problems

The multi-dimensional orthogonal packing problem (OPP) is a well studied optimization problem [Beasley, J. E., An exact two-dimensional non-guillotine cutting tree search procedure, Operations Research 33 (1985), pp. 49–64; Fekete, S. P. and J. Schepers, A combinatorial characterization of higher-dimensional orthogonal packing, Mathematics of Operations Research 29 (2004), pp. 353–368]. 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. Rotation of items is not allowed.Fekete and Schepers introduced a tuple of interval graphs as data structures to store a feasible packing, and gave a very efficient algorithm. In this paper, we propose a new algorithm using consecutive one matrices as data structures, due to Fulkerson and Gross's characterization of interval graphs. Computational results are reported, which show its effectiveness.