Utilize este identificador para referenciar este registo:
https://hdl.handle.net/1822/26523
Título: | Multidimensional dual-feasible functions and fast lower bounds for the vector packing problem |
Autor(es): | Alves, Cláudio Carvalho, J. M. Valério de Clautiaux, François Rietz, Jurgen Endre |
Palavras-chave: | Dual-feasible functions Vector packing problem Fast lower bounds |
Data: | 2014 |
Editora: | Elsevier |
Revista: | European Journal of Operational Research |
Resumo(s): | In this paper, we address the 2-dimensional vector packing problem where an optimal layout for a set of items with two independent dimensions has to be found within the boundaries of a rectangle. Many practical applications in areas such as the telecommunications, transportation and production planning lead to this combinatorial problem. Here, we focus on the computation of fast lower bounds using original approaches based on the concept of dual-feasible functions. Until now, all the dual-feasible functions proposed in the literature were 1-dimensional functions. In this paper, we extend the principles of dual-feasible functions to the m-dimensional case by introducing the concept of vector packing dual-feasible function, and we propose and analyze di erent new families of functions. All the proposed approaches were tested extensively using benchmark instances described in the literature. Our computational results show that these functions can approximate very e ciently the best known lower bounds for this problem and improve signi cantly the convergence of branch-and-bound algorithms. |
Tipo: | Artigo |
URI: | https://hdl.handle.net/1822/26523 |
DOI: | 10.1016/j.ejor.2013.08.011 |
ISSN: | 0377-2217 |
Arbitragem científica: | yes |
Acesso: | Acesso restrito UMinho |
Aparece nas coleções: | CAlg - Artigos em revistas internacionais / Papers in international journals |
Ficheiros deste registo:
Ficheiro | Descrição | Tamanho | Formato | |
---|---|---|---|---|
VPDFFs.pdf Acesso restrito! | 552,64 kB | Adobe PDF | Ver/Abrir |