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

Resumen

"El problema de la mochila (KP por sus siglas en inglés), es un problema de optimización combinatoria muy referenciado en la literatura de investigación de operaciones, tanto por sus aplicaciones como por su estructura, que lo hace ideal para la evaluación del desempeño de métodos de búsqueda inteligente en problemas de optimización combinatorio. En este artículo se explora la utilización de optimizadores de propósito general, que usan métodos de solución estándar basados en algoritmos genéticos, solvers que utilizan métodos exactos, fundamentalmente métodos basados en branch&bound y se diseña dos algoritmos propios, el primero basado en la metaheurística GRASP clásica, y el segundo en una modificación a la propuesta original de la metodología GRASP, que demuestra ser muy eficiente en la solución del KP, y que es construido en base a un estudio de las cotas de este problema, con ello se propone el nuevo esquema GRASP para desarrollar algoritmos eficientes para resolver problemas de optimización combinatoria."