MPQ-trees for the orthogonal packing problem
JONCOUR, Cédric
Reformulations based algorithms for Combinatorial Optimization [Realopt]
Institut de Mathématiques de Bordeaux [IMB]
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]
Reformulations based algorithms for Combinatorial Optimization [Realopt]
Laboratoire Bordelais de Recherche en Informatique [LaBRI]
JONCOUR, Cédric
Reformulations based algorithms for Combinatorial Optimization [Realopt]
Institut de Mathématiques de Bordeaux [IMB]
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]
< Leer menos
Reformulations based algorithms for Combinatorial Optimization [Realopt]
Laboratoire Bordelais de Recherche en Informatique [LaBRI]
Idioma
en
Article de revue
Este ítem está publicado en
Journal of Mathematical Modelling and Algorithms. 2012-03-01, vol. 11, n° 1, p. 3-22
Springer Verlag
Resumen en inglés
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 ...Leer más >
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.< Leer menos
Palabras clave en inglés
Orthogonal Packing Problem
MPQ-trees
Orígen
Importado de HalCentros de investigación