Algunas perspectivas sobre la solución de problemas de programación entera (VIII)

A causa de estos riesgos una mejor forma de tratar con problemas de programación entera grandes es usar uno de los algortimos heurísticos disponibles. Estos algoritmos son muy eficientes para problemas grandes, pero no garantizan que se llegue a una solución óptima. Sin embargo, tienden a ser considerablemente más efectivos para encontrar excelentes soluciones factibles que el enfoque de redondeo que se acaba de analizar.

Por ahora se dispone de un gran número de algoritmos para pequeños problemas de programación entera que deben resolverse hasta llegar al óptimo. Por desgracia, ninguno posee eficiencia computacional que se pueda siquiera comparar con el método  símplex (excepto los tipos especiales de problemas). El desarrollo de algoritmos de programación entera sigue siendo un tema de investigación. Por fortuna, durante la última parte de la decáda de 1980 se hicieron algunos adelantos y se esperan más progresos para la siguiente década. Estos adelantos recientes se analizarán en la sección 13.6.