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

  • Fernando Sandoya Escuela Superior Politécnica del Litoral

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."

Citas

K. BRETTHAUER Y B. SHETTY. (2002). "The nonlinear knapsack problem - algorithms and aplications ", European Journal of Operational Research, vol. 138, nº 3, pp. 459-472.

M. R. GAREY Y D. S. JOHNSON, Computers and lntractability: A Guide to the Theory of NP-Completeness , New York: W.H. Freeman, 1979.

C. H. Papadimitriou, «On the Complexity of lnteger Programming,» Journal of the Association for Computing Machinery, vol. 28, nº 4, pp. 765-768, 1981.

Optsicom.es,» [En línea]. Available: http://www.optsicom .es/binaryss/knaps ack.zip. [Último acceso: 20 4 2014].

T. FEO Y M. RESENDE, «A probabilistic heuristic for a computationally difficult set covering problem,» Operations Research Letters, vol. 8, pp. 67 - 71, 1989.

M. RESENDE Y R. WERNECK, «A hybrid heuristic for the p-median problem,» Journal of heuristics, vol. 10, nº l , pp. 59-88, 2004.

R. MARTÍ, Procedimientos Metaheuristicos en Optimización Combinatoria, Universitat de Valencia, 2008.

F. GORTÁZAR, A. DUARTE, M. LAGUNA Y R. MARTÍ, «Black box scatter search for general classes of binary optlmtzation problems,» Computers & Operations Research , vol. 37, nº 11, pp. 1977 - 1986, 2010.

PALISADE , «Evolver -Para optimización por medio de algoritmos genéticos- Palísade,» 16 05 2011. [En línea]. Available : http://www.palisade­ lta.com/evolver/. [Último acceso: 16 OS 2011].

PALISADE CORPORATION, Corporation,» [En línea]. Available: http://www.palísade-lta.com/. [Último acceso: Julio 2013].

J. DRÉO, A. PÉTROWSKI, P. SIARRI Y E. TAILLARD, Metaheuristics for Hard Optimization, Berlin: Springer, 2006, pp. 169 - 170.

V. CAMPOS, M. LAGUNA Y R. MARTÍ, «Context-independient scatter and tabu search for pennutation problems,» INFORMS Joumal on Computing, vol. 17, nº l , pp. 111 - 122, 2005.
Publicado
2014-10-01
Sección
Articulos