JONCOUR, Cédric; PÊCHER, Arnaud

doi:10.1007/s10852-011-9167-z

Métadonnées

Licence d’utilisation du document

http://creativecommons.org/licenses/by-sa/

JONCOUR, Cédric
Reformulations based algorithms for Combinatorial Optimization [Realopt]
Institut de Mathématiques de Bordeaux [IMB]

PÊCHER, Arnaud
Reformulations based algorithms for Combinatorial Optimization [Realopt]
Laboratoire Bordelais de Recherche en Informatique [LaBRI]

Langue

Article de revue

Ce document a été publié dans

Journal of Mathematical Modelling and Algorithms. 2012, vol. 11, n° 1, p. 23-44

Springer Verlag

Résumé en anglais

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.< Réduire

Métadonnées

Partager cette publication !

Licence d’utilisation du document

Consecutive ones matrices for multi-dimensional orthogonal packing problems

Langue

Ce document a été publié dans

Résumé en anglais

URI

DOI

Origine

Unités de recherche