Utilize este identificador para referenciar este registo:
https://hdl.handle.net/1822/36517
Título: | Solving the multiscenario Max-Min Knapsack problem exactly with column generation and branch-and-bound |
Autor(es): | Pinto, Telmo Alves, Cláudio Mansi, Raid Carvalho, J. M. Valério de |
Data: | 2015 |
Editora: | Hindawi Publishing Corporation |
Revista: | Mathematical Problems in Engineering |
Citação: | Pinto, T., Alves, C., Mansi, R., & Valério de Carvalho, J. (2015). Solving the Multiscenario Max-Min Knapsack Problem Exactly with Column Generation and Branch-and-Bound. Mathematical Problems in Engineering, 2015 |
Resumo(s): | Despite other variants of the standard knapsack problem, very few solution approaches have been devised for the multiscenario max-min knapsack problem. The problem consists in finding the subset of items whose total profit is maximized under the worst possible scenario. In this paper, we describe an exact solution method based on column generation and branch-and-bound for this problem. Our approach relies on a reformulation of the standard compact integer programming model based on the Dantzig- Wolfe decomposition principle.The resulting model is potentially stronger than the original one since the corresponding pricing subproblem does not have the integrality property. The details of the reformulation are presented and analysed together with those concerning the columngeneration and branch-and-bound procedures.To evaluate the performance of our algorithm,we conducted extensive computational experiments on large scale benchmark instances, and we compared our results with other state-of-the-art approaches under similar circumstances. We focused in particular on different relevant aspects that allow an objective evaluation of the efficacy of our approach. From different standpoints, the branch-and-price algorithm proved to outperform the other stateof- the-art methods described so far in the literature. |
Tipo: | Artigo |
URI: | https://hdl.handle.net/1822/36517 |
DOI: | 10.1155/2015/439609 |
ISSN: | 1024-123X 1563-5147 |
Versão da editora: | http://www.hindawi.com/journals/mpe/2015/439609/cta/ |
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 | |
---|---|---|---|---|
439609.pdf Acesso restrito! | 1,99 MB | Adobe PDF | Ver/Abrir |