Please use this identifier to cite or link to this item:
|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.|
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.|
|Appears in Collections:||Unicamp - Artigos e Outros Documentos|
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.