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 metadatas

Cited literature [26 references]  Display  Hide  Download

https://hal.inria.fr/hal-00652574
Contributor : Cédric Joncour <>
Submitted on : Thursday, December 15, 2011 - 7:08:00 PM
Last modification on : Thursday, January 11, 2018 - 6:22:12 AM
Long-term archiving on : Friday, November 16, 2012 - 3:41:16 PM

File

paperAlgoKPjmma.pdf
Files produced by the author(s)

Licence


Distributed under a Creative Commons Attribution - ShareAlike 4.0 International License

Identifiers

Citation

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

Share

Metrics

Record views

454

Files downloads

192