DocumentCode
3061846
Title
A Solution to the Strongly Correlated 0-1 Knapsack Problem by a Binary Branch and Bound Algorithm
Author
Zavala-Díaz, José Crispín ; Ruiz-Vanoye, Jorge A. ; Díaz-Parra, Ocotlán ; Aguilar, José A Hernández
Author_Institution
FCAeI-UAEM Cuernavaca, Cuernavaca, Mexico
fYear
2012
fDate
23-26 June 2012
Firstpage
237
Lastpage
241
Abstract
In this paper is presented the Binary Branch-and-Bound Algorithm (BBBA) and its application to determine the solution of the 0-1 Knapsack Problem. The algorithm solves different instances (uncorrelated, weakly and strongly correlated) in time (Kn). The proposed algorithm was experimentally compared with the Pisinger Model, based on the obtained results it is demonstrated the ability of the proposed algorithm to solve problems that the Pisinger algorithm cannot solve.
Keywords
computational complexity; knapsack problems; tree searching; BBBA; Pisinger algorithm; Pisinger model; binary branch and bound algorithm; correlated 0-1 knapsack problem; Approximation algorithms; Complexity theory; Equations; Heuristic algorithms; Mathematical model; Search problems; Upper bound; Branch-and-Bound; Knapsack problem 0-1; Search tree;
fLanguage
English
Publisher
ieee
Conference_Titel
Computational Sciences and Optimization (CSO), 2012 Fifth International Joint Conference on
Conference_Location
Harbin
Print_ISBN
978-1-4673-1365-0
Type
conf
DOI
10.1109/CSO.2012.60
Filename
6274718
Link To Document