Acotamiento (I)

Ahora es necesario obtener, para cada subproblema, una cota que muestre qué tan buena puede ser su mejor solución factible. La forma más común para hacer esto es resolver rápidamente una soltura sencilla del subproblema. Casi siempre, una soltura de un problema se obtiene elininando ("soltando") un conjunto de restricciones que hacen que el problema sea difícil de resolver. En los problemas de PE las restricciones de más dificultad son las que requieren que las variables sean enteras. Entonces, la soltura que más se usa es la soltura de PL que elimina este conjunto de restricciones.

Trabajando con el ejemplo, considérese primero el problema completo dado en la sección 13.1. Su soltura de PL se obtiene al eliminar el último renglón del modelo (xj es entera, para j = 1,2,3,4) pero conservando las restricciones de xj ≤ 1 y xj ≥ 0. Al aplicar el método símplex para resolver esta soltura de PL se obtiene su solución óptima.

(x1, x2, x3, x4 ) = (5/6, 1, 0, 1), con Z = 16(1/2)

Ramificación (III)

En otros problemas de programación entera, en donde los valores enteros pueden tener más de dos variables posibles, la ramificación se puede hacer estableciendo la variable de ramificación igual a sus respectivos valores individuales, con lo que se crean más de dos subproblemas. Otro buen enfoque es especificar el intervalo de valores (por ejemplo, xj ≤ 2 o xj ≥ 3) para la variable de ramificación para cada nuevo subproblema. Este es el enfoque que se usa en el algoritmo que se presenta en la sección 13.5

Ramificación (II)

La figura 13.2 muestra esto con una división (ramificación) en subproblemas, mediante un árbol (definido en la sección 10.2) con ramas (arcos) desde todos los nodos (correspondientes al problema completo que contiene todas las soluciones factibles) a los dos nodos correspondientes a los dos subproblemas. Este árbol que hará *crecer sus ramas* en cada interación se conoce como el árbol de soluciones (o árbol de enumeración) para el algortimo. La variable que se usa para hacer la ramificación en una iteración al asignarle valores (como con x1) se llama variable de ramificación.

Más adelante se verá que uno de estos subproblemas se puede vencer (sondear) de inmediato, mientas que el otro requiere una nueva división en subproblemas más pequeños estableciendo  x2 = 0 o x2 = 1, etc.

Ramificación (I)

Cuando se manejan variables binarias, la forma más sencilla de partir el conjunto de soluciones factibles es fijar el valor de una variable (por ejemplo, x1) en x1 = 0 para un subconjunto y en x1 = 1 para el otro. Al hacer esto en el ejemplo prototipo, el problema completo queda dividido en dos subproblemas más pequeños, como sigue:

Subproblema 1: (x1 = 0)

Maximizar Z = 5x2 + 6x3 + 4x4

Técnica de ramificación y acotamiento y sus aplicaciones a la programación entera binaria

Como cualquier problema acotado de programación entera pura, tiene sólo un número finito de soluciones factibles, resulta natural considerar el uso de algun tipo de procedimiento de enumeración para encontrar una solución óptima. Desafortunadamente, como ya se dijo, este número finito puede ser, y casi siempre lo es, muy grande, por lo que es imperativo que cualquier procedimiento de enumeración de estructura con habilidad para que sólo sea necesario examinar una pequeña fracción de estas soluciones factibles. Por ejemplo, la programación dinámica (véase el capítulo) proporciona un procedimiento de este tipo para muchos problemas que tienen un número finito de soluciones factibles (aunque no es especialmente eficiente para la mayor parte delos problemas de PE) Otro enfoque de este tipo lo proporciona la técnica de ramificación y acotamiento. Esta técnica y algunas variaciones se han aplicado con cierto éxito a diversos problemas de investigación de operaciones, pero es más conocida por sus aplicaciones a los problemas de programación entera.

La idea básica en la que se apoya esta técnica se divide y vencerás. Como es demasiado complicado resolver directamente el problema original "grande", se divide en subproblemas cada vez más pequeños hasta que estos se puedan vencer. La división (ramificación) se hace mediante una partición del conjunto completo de soluciones factibles en subconjuntos más pequeños. La consulta (sondeo) se hace en parte acotando la mejor solución en el subconjunto y después descartando los subconjuntos cuya cota indique que no es posible que contenga una solución óptima.

Ahora se describirá cada uno de estos pasos básicos -ramificación, acotamiento y sondeo - y se ilustrarán aplicando un algoritmo de ramificación y acotamiento al ejemplo prototipo (el problema de California Manufacturing Co.) que se presentó en la sección 13.1.

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

Uno de los algortimos más populares de programación entera es la técnica de ramificación y aontecimientoy las ideas relacionadas con la enumeración implícita de las soluciones factibles enteras, cuyos enfoques se analizarán aquí. La siguiente sección presenta la técnica de ramificación y acotamiento en un contexto general. La sección 13.5 describe otro algoritmo del mismo tipo para problemas de programación entera mixta.

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.