El problema de la mochila, complejidad, cotas y métodos de búsqueda eficientes

Abstract

"The knapsack problem (KP) is a combinatorial optimization problem very referenced in the literature of Operations Research, both for its applications as its structure, making it ideal for performance evaluation of intelligent search methods useful for solving combinatorial optimization problems. In this article the use of general purpose solvers, using standard methods of solution based on genetic algorithms, and exact methods, mainly branch and bound based and two proprietary algorithms designed is explored, the first based on the GRASP classical metaheuristic, and the second in an amendment to the original proposal of the GRASP methodology, which proves to be very efficient in solving the KP, and is built on a study of the dimensions of this problem, thus the new scheme GRASP is proposed to develop efficient algorithms for solving combinatorial optimization problems. "