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

Puede parecer que los problemas de programación entera son relativamente fáciles de resolver. Después de todo, los problemas de programación lineal se pueden resolver de una manera bastante eficiente, y la única diferencia es que la programación entera tiene muchas menos soluciones que considerar. De hecho, está garantizado que los problemas de PE pura con una región factible acotada tienen sólo un número finito de soluciones factibles.

Por desgracia, existen dos falacias en este tipo de razonamiento. Una es que el tener un número finito de soluciones factibles asegure que el problema se puede resolver. Los números finitos pueden ser astronómicamente grandes. Por ejemplo, considérese el caso de problemas sencillos de programación entera binaria. Si se tienen n variables, existen 2^n soluciones que se deben tomar en cuenta (en donde algunas de estas soluciones se pueden descartar por violar las restricciones funcionales). Entonces, cada vez que n se aumenta en uno, el número de soluciones se duplica. Este patrón se llama el crecimiento exponencial de la dificultad del problema. Con n =10, se tienen más de mil soluciones (1024); con n = 20, son más de un millón; con n  = 30 resultan más de mil millones, y así sucesivamente; por eso, aun las computadoras más eficientes son incapaces de realizar una enumeración exhaustiva (que verifique la factibilidad de cada solución y, si es posible, calcular el valor de la función objetivo) para problemas de PEB con unas cuantas docenas de variables, sin mencionar los problemas de PE general con el mismo número de variables enteras.  Se cuenta con algunos algoritmos elaborados, como los que se desarrollan en las secciones siguientes, que pueden llevar a cabo un mejor trabajo. En la sección 13.6 se explica cómo algunos algoritmos desarrollados recientemente han resuelto con éxito ciertos problemas muy grandes de PEB (de hasta 2756 variables). Sin embargo, debido al crecimiento exponencial, incluso los mejores algoritmos no garantizan la solución de todos los problemas relativamente pequeños (con menos de cien variables binarias o enteras.)