Please use this identifier to cite or link to this item: http://repositorio.unicamp.br/jspui/handle/REPOSIP/91279
Type: Artigo de periódico
Title: A New Lagrangian Based Branch And Bound Algorithm For The 0-1 Knapsack Problem
Author: Salles da Cunha A.
Bahiense L.
Lucena A.
Carvalho de Souza C.
Abstract: This paper describes a new Branch and Bound algorithm for the 0-1 Knapsack Problem (KP). The algorithm is based on the use of a Lagrangean Relax-and-Cut procedure that allows exponentially many Fractional Gomory Cuts and Extended Cover Inequalities to be candidates to Lagrangean dualization. In doing so, the upper bounds thus obtained are stronger than the standard Linear Programming relaxation bound for KP. The algorithm is aimed at solving instances with coefficients as large as 1015, a class of KP instance for which existing solution algorithms might not be directly applicable. © 2010 Elsevier B.V.
Editor: 
Rights: fechado
Identifier DOI: 10.1016/j.endm.2010.05.079
Address: http://www.scopus.com/inward/record.url?eid=2-s2.0-77954944939&partnerID=40&md5=55714f93bde835cf426aa24bf1ca8c12
Date Issue: 2010
Appears in Collections:Unicamp - Artigos e Outros Documentos

Files in This Item:
File Description SizeFormat 
2-s2.0-77954944939.pdf214.75 kBAdobe PDFView/Open


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.