Busca avançada
Ano de início
Entree
(Referência obtida automaticamente do Web of Science, por meio da informação sobre o financiamento pela FAPESP e o número do processo correspondente, incluída na publicação pelos autores.)

Determining the K-best solutions of knapsack problems

Texto completo
Autor(es):
Leao, Aline A. S. [1] ; Cherri, Luiz H. [1] ; Arenales, Marcos N. [1]
Número total de Autores: 3
Afiliação do(s) autor(es):
[1] Univ Sao Paulo, Inst Ciencias Matemat & Computacao, BR-13560970 Sao Carlos, SP - Brazil
Número total de Afiliações: 1
Tipo de documento: Artigo Científico
Fonte: Computers & Operations Research; v. 49, p. 71-82, SEP 2014.
Citações Web of Science: 3
Resumo

It is well-known that knapsack problems arise as subproblems of a number of large-scale integer optimization problems. In order to solve these large problems, it is necessary to solve the subproblems efficiently, and for many of them it can be useful to determine the K-best solutions. In this paper, a branch-and-bound method for the unbounded knapsack problem described in the literature is extended to determine the K-best solutions of unbounded and bounded knapsack problems. We show that the proposed extension determines exactly the K-best solutions and we solve important classical instances using high values of K. (C) 2014 Elsevier Ltd. All rights reserved. (AU)

Processo FAPESP: 08/09046-5 - Problemas da mochila compartimentada: casos unidimensional e bidimensional
Beneficiário:Aline Aparecida de Souza Leão
Linha de fomento: Bolsas no Brasil - Doutorado