Skip to Main content Skip to Navigation
New interface
Journal articles

Consecutive ones matrices for multi-dimensional orthogonal packing problems

Cédric Joncour 1, 2 Arnaud Pêcher 1, 3 
1 Realopt - Reformulations based algorithms for Combinatorial Optimization
LaBRI - Laboratoire Bordelais de Recherche en Informatique, IMB - Institut de Mathématiques de Bordeaux, Inria Bordeaux - Sud-Ouest
Abstract : 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.
Complete list of metadata

Cited literature [26 references]  Display  Hide  Download
Contributor : Cédric Joncour Connect in order to contact the contributor
Submitted on : Thursday, December 15, 2011 - 7:08:00 PM
Last modification on : Saturday, June 25, 2022 - 7:44:25 PM
Long-term archiving on: : Friday, November 16, 2012 - 3:41:16 PM


Files produced by the author(s)


Distributed under a Creative Commons Attribution - ShareAlike 4.0 International License




Cédric Joncour, Arnaud Pêcher. Consecutive ones matrices for multi-dimensional orthogonal packing problems. Journal of Mathematical Modelling and Algorithms, 2012, Journal of Mathematical Modelling and Algorithm, 11 (1), pp.23-44. ⟨10.1007/s10852-011-9167-z⟩. ⟨hal-00652574⟩



Record views


Files downloads