Algoritmo de ramificación y acotamiento para programación entera mixta (IV)

Cuando se combinan los dos cambios al algoritmo de PEB que se acaban de describir, puede ocurrir un interesante fenómeno de una variable de ramificación recurrente. Para ilustrar esto, sea j = 1 en el ejemplo anterior en donde x*j = 3(1/2) y considérese el nuevo subproblema con x1 ≤ 3. Supóngase que cuando se resuelve la soltura de PL para un descendiente de este subproblema se obtiene x*1 = 1(1/4). Entonces, x1 recurre como variable de ramificación y los dos nuevos subproblemas creados tienen la restricción adicional x1 ≤ 1 y x1 ≥ 2, respectivamente (además de la restricción adicional anterior, x1 ≤ 3). Más adelante, cuando se resuelva la soltura de PL de un descendiente del subproblema que contiene, digamos x1 ≤ 1, se supondrá que x*1 = 3/4. Entonces x1 recurre de nuevo como variable de ramificación, y los dos nuevos subproblemas creados tienen x1 = 0 (debido a la nueva restricción x1 ≤ 0 y la restricción de no negatividad sobre x1) y x1 = 1 (por la nueva restricción x1 ≥ 1 y la anterior x1 ≤ 1).

El tercer cambio se hace en el paso de acotamiento. Antes, con un problema de PE pura y coeficientes enteros en la función objetivo, el valor de Z para la solución óptima de la soltura de PL del subproblema, se redondeaba hacia abajo para obtener la cota, ya que cualquier solución factible para el problema debía tener una Z entera. Ahora, Con algunas variables sinla restricciónn de enteras, la cota es el valor de Z sin redondear.