JONCOUR, Cédric; PÊCHER, Arnaud; VALICOV, Petru

doi:10.1007/s10852-011-9159-z

Métadonnées

Licence d’utilisation du document

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]

VALICOV, Petru
Laboratoire Bordelais de Recherche en Informatique [LaBRI]

Langue

Article de revue

Ce document a été publié dans

Journal of Mathematical Modelling and Algorithms. 2012-03-01, vol. 11, n° 1, p. 3-22

Springer Verlag

Résumé en anglais

Given a set of rectangular items of different sizes and a rectangular container, the aim of the bi-dimensional Orthogonal Packing Problem (OPP-2 for short) is to decide whether there exists a non-overlapping packing of the items in this container. The rotation of items is not allowed. In this paper we present a new exact algorithm for solving OPP-2, based upon the characterization of solutions using interval graphs proposed by Fekete and Schepers. The algorithm uses MPQ-trees, which were introduced by Korte and Möhring to recognize interval graphs.< Réduire

Mots clés en anglais

Orthogonal Packing Problem

MPQ-trees

Métadonnées

Partager cette publication !

Licence d’utilisation du document

MPQ-trees for the orthogonal packing problem

Langue

Ce document a été publié dans

Résumé en anglais

Mots clés en anglais

URI

DOI

Origine

Unités de recherche