Models and bounds for two-dimensional level packing problems

Lodi, Andrea ; Martello, Silvano ; Vigo, Daniele (2004) Models and bounds for two-dimensional level packing problems. Journal of Combinatorial Optimization, 8 (3). pp. 363-379. ISSN 1382-6905
Full text disponibile come:
[thumbnail of Models.pdf]
Anteprima
Documento PDF
Licenza: Creative Commons Attribution Non-commercial 3.0 (CC BY-NC 3.0)

Download (186kB) | Anteprima

Abstract

We consider two-dimensional bin packing and strip packing problems where the items have to be packed by levels. We introduce new mathematical models involving a polynomial number of variables and constraints, and show that their LP relaxations dominate the standard area relaxations. We then propose new (combinatorial) bounds that can be computed in O(nlog n) time. We show that they dominate the other bounds, and establish their absolute worst-case behavior. The quality of models and bounds is evaluated through extensive computational experiments

Abstract
Tipologia del documento
Articolo
Autori
AutoreAffiliazioneORCID
Lodi, Andrea
Martello, Silvano
Vigo, Daniele
Parole chiave
combinatorial mathematics, mathematical programming, polynomials, constraint theory, approximation theory, packing, costs, problem solving, algorithms, mathematical models, computational complexity
Settori scientifico-disciplinari
ISSN
1382-6905
DOI
Data di deposito
07 Apr 2006
Ultima modifica
31 Ott 2012 11:50
URI

Altri metadati

Statistica sui download

Statistica sui download

Gestione del documento: Visualizza il documento

^