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

Aunque toda esta simplificación no es usual, con frecuencia los problemas de programación entera que surgen en la práctica tiene alguna estructura especial que se puede aprovechar para simplificarlos. A veces se pueden resolver con éxito versiones muy largas de estos problemas. Cada vez son más importantes los algortimos de propósitos especiales que están elaborados específicamente para explotar ciertos tipos de estructuras especiales en programación entera.

Entonces, los dos factores determinantes de la dificultad computacional de un problema de PE son 1) el número de variables enteras y 2) la estructura del problema. Esta situación es opuesta a la de programación lineal, en donde el número de restricciones funcionales es mucho más importante que el número de variables. En programación entera, el número de restricciones tiene alguna importancia (en especial, si se van a resolver las solturas de PL), pero es estrictamente secundario para los otros dos factores. De hecho, existen casos en los que aumentar el número de restricciones disminuye el tiempo de cálculo ya que se reduce el número de soluciones factibles. En los problemas de PEM es el número de variables enteras y no el número total de variables el que es importante, pues las variables continuas casi no tienen efecto sobre el esfuerzo computacional.

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

Aunque, sin duda, casi siempre es accidental que la solución óptima de la soltura de PL sea entera de hecho, existen varios tipos especificos de problemas de PE para los que este resultado se puede garantizar. Ya se vieron dos de estos casos especiales en los capitulos 7 y 10, estos son el problema de flujo de costo mínimo (con parámetros enteros) y sus casos especiales (el problema de transporte, el problema de trasbordo, el problema de asignación, el problema de la ruta más corta, y el problema del flujo máximo). La razón por la que se puede dar esta garantía es la estructura especial que poseen estos tipos particulares de problemas, que asegura que toda solución factible es entera, como se estableció en la propiedad de soluciones enteras dada en las secciones 7.1 y 10.6. Por ello, estos tipos especiales de problemas de programación entera se pueden manejar como problemas de programación lineal (que es el motivo por el que tres de ellso aparecen en el capitulo 7) ya que se pueden resolver completamente aplicando las versiones simplificadas del método símplex.

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

Existe una situación especial en la que no es más difícil resolver el problema de programación entera que resolver una vez su soltura de PL aplicando el método símplex; esta situación es aquélla en la que la solución a la soltura de PL satisface la restricción de valores enteros.

Cuando ocurre esto, la solución también debe ser óptima para el problema de programación entera, ya que se trata de la mejor solución entre todas las soluciones de la soltura de PL, que incluye todas las soluciones factibles del problema de programación entera. Entonces, es normal que un algoritmo de programación entera comience con la aplicación del método símplex  a su soltura de PL, para verificar si tiene lugar este casual acontecimiento.

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

La segunda falacia es que al eliminar algunas soluciones factibles (las o enteras) de un problema de programación lineal, será más fácil de resolverlo. Todo lo contrario: sólo cuando todas estas soluciones factibles están ahí, se puede garantizar (véase la sección 5.1) que existe una solución factible en el vértice (solución básica factible) que es óptima para el problema completo. Esta garantía es la clave de la extraordinaria eficiencia del método símplex. Como resultado, en general es mucho más sencillo resolver los problemas de programación líneal que los de programación entera.

ES lógico, entonces, que la mayor parte de los buenos algoritmos de programación entera incorporen el método simplex (o el método símplex dual) lo más que puedan, y relacionen partes del problema de PE bajo consideración con el problema correspondiente de programación líneal  (es decir, el mismo problema con la restricción de valores enteros eliminada). Para cualquier problema dado de programacion entera, el problema correspondiente de programación líneal se conoce como su soltura de PL. El algortimo que se presenta en las dos secciones siguientes ilustra cómo se puede usar una sucesión de solturas de PL para porciones de un problema de programación entera, con objeto de resolver de manera eficiente un problema completo de PE.

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

Representación binaria de variables enteras en general (IV)

Si se trata de un problema de programación entera en el que todas las variables son enteras generales (acotadas) sería posible usar esta misma técnica para reducirlo a un problema de PEB. Sin embargo, esto casi nunca es aconsejable debido a la explosión en el número de variables. En general, aplicar un buen algoritmo de PE al modelo original será más eficiente que aplicar un buen algoritmo de PEB a un modelo mucho más grande.

En términos generales, con todas las posibilidades de formulación con variables binarias auxiliares que se presentaron en esta sección, es necesario hacer notar una precaución que debe tenerse. Algunas veces, este enfoque requiere que se agregue un número relativamente grande de variables,lo que puede hacer que el modelo se vuelva no factible computacionalmente. De hecho, como se explica en las siguiente secciones, se pueden tener problemas con menos de cien variables binarias.

Representación binaria de variables enteras en general (III)

DEspués de sustituir estas expresiones por las variables respectivas en todas las restricciones funcionales y en la función objetivo, las dos restricciones funcionales que se establecieron se convierten en: