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.
Type de document :
Article dans une revue
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〉
Liste complète des métadonnées

Littérature citée [26 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-00652574
Contributeur : Cédric Joncour <>
Soumis le : jeudi 15 décembre 2011 - 19:08:00
Dernière modification le : jeudi 11 janvier 2018 - 06:22:12
Document(s) archivé(s) le : vendredi 16 novembre 2012 - 15:41:16

Fichier

paperAlgoKPjmma.pdf
Fichiers produits par l'(les) auteur(s)

Licence


Distributed under a Creative Commons Paternité - Partage selon les Conditions Initiales 4.0 International License

Identifiants

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〉

Partager

Métriques

Consultations de la notice

417

Téléchargements de fichiers

138