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
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;
Conference_Titel :
Computational Sciences and Optimization (CSO), 2012 Fifth International Joint Conference on
Conference_Location :
Harbin
Print_ISBN :
978-1-4673-1365-0
DOI :
10.1109/CSO.2012.60
