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

El cuarto (y último) cambio al algoritmo de PEB para obtener el algoritmo de PEM se refiere a la prueba de sondeo 3. Antes, con un problema de PE pura, la prueba consistia en que la solución a la soltura de PL del subproblema fuera entera, puesto que esto aseguraba una solución factible y por lo tanto óptima para el subproblema. Ahora, on un problema de PE mixta, la prueba requiere que nada más las variables restringidas a enteras tengan valores enteras en la solución óptima de la soltura de PL del subproblema, ya que esto es suficiente para asegurar que la solución es factible y por lo tanto óptima para el subproblema.

La incorporación de estos cuatro cambios  al resumen que se presentó en la sección anterior del algoritmo de programación entera binaria lleva al siguiente resumen del nuevo algoritmo de programación entera mixta.

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.

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

El segundo cambio se refiere a los valores asignados a la variable de ramificación para crear los nuevos subproblemas. Antes, se fijaba este valor en 0 y 1 respectivamente para los dos nuevos subproblemas. Ahora, la variable general con restricción entera puede tener un número grande de valores enteros posibles, y sería ineficiente crear y analizar muchos subproblemas dando los valores enteros individuales a la variable. Entonces, se crean sólo dos nuevos subproblemas - como antes- especificando dos intervalos de valores para la variable.

Para aclarar cómo se hace esto, sea xj la variable de ramificación actual y sea x*j su valor (no entero) en la solución óptima de la soltura de PL del subproblema actual. Con paréntesis cuadrados sea

[x*j] = entero más grande menor o igual que x*j

los intervalos de valores para los dos nuevos subproblemas son

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

Se describirá un algoritmo básico de ramificación y acotamiento para resolver este problema que, un poco más elaborado, ha proporcionado el enfoque estándar a PEM. La estructura de este algoritmo fue desarrollada por R.J. Dakin basándose en un algoritmo anterior que se debera a A.H. Land y A.G. Doig.

ESte algoritmo es bastante parecido en estructura al algoritmo de PEB que se presentó en la sección anterior. De nuevo la solución de una soltura  de PL proporciona la base tanto para la ramificación como para el acotamiento. De hecho sólo se necesitan cuatro cambios al algoritmo  de PEB para manejar la generalización de variables enteras binarias a generales y de PE pura a PE mixta.

Un cambio involucra la elección de la variable de ramificación. Antes se elegía de manera automática la siguiente variable en el ordenador natural (x1,x2,.......xn). Ahora, las únicas variables que se toman en cuenta son las variables con restricción de enteras que tienen un valor no entero en la solución óptima de la soltura de PL para el subproblema actual. La regla para elegir estas variables será la primera de la lista en el orden natural. (Los paquetes de producción casi siempre utilizan una regla más complicada.)

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

Ahora se estudiará el problema general de programación entera mixta, PEM, en donde algunas variables (por ejemplo I de ellas) están restringidas a valores enteros (pero no necesariamente  sólo 0 o 1), y el resto son variables continuas comunes. Por conveniencia en la notación, se ordenarán estas variables de manera que las primeras I de ellas sean variables con restricción a enteros. La forma general del problema que se va a estudiar es:

Otras opciones con la técnica de ramificación y acotamiento (VII)

y realizar esta prueba después de la prueba 3 (para que una solución factible que se encuentra con Z > Z* se conserve como una nueva solución de apoyo). La razón para que esta prueba 1 más débil sea suficiente es que no importa qué tan cerca de la cota del subproblema se encuentre Z para la solución óptima (desconocida) del subproblema, la solución de apoyo todavía estará "bastante cerca" de esta solución (si se cumple la nueva desigualdad) como para que no sea necesario seguir analizando el subproblema. Cuando no hay subproblemas restantes, la solución de apoyo actual será la solución cercana a al óptima que se desea. Sin embargo, es mucho más sencillos sondear con esta nueva prueba (en cualquier forma), por lo que el algoritmo trabajará más rápido. Si se trata de problemas grandes, está aceleración puede significar la diferencia entre terminar con una solución que seguramente es cercana a la óptima y nunca

Otras opciones con la técnica de ramificación y acotamiento (VI)

Para terminar, debe hacerse notar que más que encontrar una solución óptima, la técnica de ramificación y acotamiento se puede usar también para encontrar una solución cercana a la óptima, en general, con mucho menos esfuerzo computacional. En algunas aplicaciones, una solución es "bastante buena" si su Z está lo "suficientemente cerca' del valor de Z en la solución óptima (llámese Z**). "Suficientemente cerca" se puede definir como

Z ≥ Z** - K o como Z ≥ (1 - α)Z**

para una constante (positiva) específica K o α. Por ejemplo, si α=0.05, entonces se requiere que la solución se encuentre a un 5% de la óptima. Para encontrar una solución "suficientemente cerca" a la óptima sólo se necesita un cambio en el procedimiento usual de ramificación y acotamiento. ESte cambio consiste en reemplazar la prueba de sondeo 1 para un subproblema,

Cota ≤ Z*?
ya sea por Cota - K ≤ Z*?
o bien por (1 - α) cota ≤ Z*?

Otras opciones con la técnica de ramificación y acotamiento (V)

Hasta ahora se ha descrito cómo usar la técnica de ramificación y acotamiento para encontrar una solución óptima. Sin embargo, en el caso de empates a veces es deseable identificar todas estas soluciones óptimas para que la elección final entre ellas pueda hacerse sobre factores intangibles que no se incorporaron al modelo matemático. Para encontrarlas todas es necesario hacer unos cuantos cambios al procedimiento. Primero, se cambia la desigualdad débil en la prueba de sondeo 1 (Es la cota del subproblema ≤ Z*?) or una desigualdad estricta (Es la cota del subproblema < Z*?) para que el sondeo no ocurra si el subproblema puede tener una solución factible igual a la de apoyo. Segundo, si la prueba de sondeo 3 pasa y la solución óptima para el subproblema tiene Z = Z*, entonces se almacena esta solución como otra solución de apoyo (empatada o no), se verifica si la solución óptima obtenida para la soltura es única. Si no lo es, se identifican las otras soluciones óptimas de la soltura y se verifica que sean óptimas también para el subproblema, en cuyo caso se convierten en incumbentes. Por último, cundo la prueba de optimalidad encuentra que no hay subconjuntos restantes (sin sondear), todas las soluciones de apoyo actuales serán soluciones óptimas.

Otras opciones con la técnica de ramificación y acotamiento (IV)

Igual que para el algoritmo de PEB, los dos primeros criterios se aplican resolviendo una soltura para obtener una cota sobre el subproblema y después verificar si esta cota es ≤ Z* (prueba I) o si la soltura no tiene soluciones factibles (prueba 2). Si la soltura difiere del subproblema sólo en que se eliminaron (o se relajaron) algunas restricciones, entonces se aplica el tercer criterio verificando si la solución óptima de la soltura es factible para el subproblema, en cuyo caso debe ser óptima para el subproblema. En otras solturas (como la de Lagrange), se requiere un análisis adicional par determinar si la solución óptima para la soltura es óptima para el subproblema.

Si el problema original involucra minimización en lugar de maximización, se tienen dos opciones. Una es convertirlo a maximización en la forma usual (véase la sección 4.6). La otra es convertir directamente el algoritmo de ramificación y acotamiento a la forma de minización, en donde el ajuste más importante es cambiar la dirección de la desigualdad para la prueba de sondeo 1, de

Es la cota del subproblema ≤ Z*?
a
Es la cota del subproblema ≥ ZZ*?

Otras opciones con la técnica de ramificación y acotamiento - Resumen de criterios de sondeo

Un subproblema se sondea si el análisis de su soltura revela que:

Criterio 1: las soluciones factibles del problema  cumplen que Z ≤ Z*, o
Criterio 2: el subproblema no tiene soluciones factibles, o
Criterio 3:se encontró una solución óptima del subproblema.

Otras opciones con la técnica de ramificación y acotamiento (III)

En términos generales, las dos características que se buscan al elegir una soltura son que se pueda resolver relativamente rápido y que proporcione una cota cerrada. Ninguna de las dos por sí sola adecuada. La soltura de PL se usa más porque proporciona un excelente trueque entre estos dos factores.

Una opción que se emplea a veces es la solución rápida de una soltura y después, si no se logra el sondeo, se cierra la soltura de alguna forma para obtener una mejor cota.

El  sondeo casi siempre se hace como se describió en el algoritmo de PEB. Los tres criterios para sondear se pueden establecer en términos más generales como sigue:

Otras opciones con la técnica de ramificación y acotamiento (II)

La ramificación casi siempre se hace resolviendo una soltura. Sin embargo, existen muchas formas de solturas. Por ejemplo, considérese la soltura de Lagrange, en donde se elimina el conjunto completo de restricciones funcionales (en forma matricial), Ax ≤ b (excepto quizá algunas restricciones "convenientes"), y después la función objetivo,

Maximizar Z = cx,

se reemplaza por

Maximizar ZR = cx - λ(Ax - b)

en donde el vector fijo λ ≤ 0. Si x* es una solución óptima para el problema original, su Z ≤ ZR, por o que al obtener un valor óptimo de ZR con la soltura de Lagrange se llega a una cota válida. Si λ se elige bien, esta cota tiende a ser razonablemente cerrada (al menos comparable a la cota de la soltura de PL). Sin restricciones funcionales, esta soltura se puede obtener muy rápido. Las desventajas son que las pruebas de sondeo 2 y 3 (cambiadas) no son tan poderosas como las de la soltura de PL. No obstante, en ocasiones se usan las dos solturas juntas con bastantes ventajas.

Otras opciones con la técnica de ramificación y acotamiento (I)

Esta sección ha ilustrado la técnica de ramificación y acontamiento con la descripción de un algoritmo básico para resolver problemas  de programación entera binaria. Sin embargo, el marco general de trabajo de la técnica de ramificación y acotamiento proporciona una gran flexibilidad en cuanto al diseño de un algoritmo específico para cualquier tipo de problema dado. Se dispone de muchas opciones y la construcción de un algoritmo eficiente requiere adaptar el diseño específico para que se ajuste a la estructura particular del tipo de problema.

Cada algoritmo de ramificación y acotamiento contiene los mismos pasos básicos de ramificación, acotamiento y sondeo. La flexibilidad consiste en cómo se realizan estos pasos.

La ramificación siempre implica seleccionar un subproblema restante y dividirlo en subproblemas  más pequeños. En este caso, la flexibilidad se encuentra en las en las reglas para seleccionar y dividir. El algoritmo que se presentó elige el subproblema de creación más reciente, porque esto es muy eficiente para reoptimizar cada soltura de PL a partir  de la anterior. Elegir el subproblema con la mejor cota es la otra regla popular, ya que tiende a llegar más rápido  a mejores soluciones de apoyo y más sondeos. También se puede usar una combinación de estas dos reglas. La división casi siempre (pero no siempre) se hace seleccionando una variable de ramificación y asignándole, ya sea valores individuales (como el algoritmo), o intervalos de valores (como en el algoritmo de la siguiente sección). Algoritmos más elaborados por lo general  utilizan una regla para elegir estratégicamente una variable de ramificación que tienda a sondeos rápidos.

Iteración 4 (II)

Como se encontró una nueva solución de apoyo, se vuelve a aplicar la prueba 1 con el nuevo valor más grande de Z al único subproblema que queda, el del nodo (1,0)

Subproblema 3: cota = 13 ≤ Z* = 14

Entonces, este subproblema queda sondeado.

Se tiene ahora el árbol de solución en la figura 13.7. Nótese que no hay subproblemas restantes (sin sondear). En consecuencia, la prueba de optimalidad indica que la solución de apoyo actual.,

(x1, x2, x3, x4) = (1,1,0,0)

es óptima, y el problema termina aquí.

Iteración 4 (I)

Los subproblemas que corresponden a los nodos (1,0) y (1,1,0) en la figura 13.6 permanece bajo consideración, pero el último es de creación más reciente, por lo que se selecciona para ramificación. Como la variable de ramificación x4 es la última variable, si se fija su valor en 0 o en 1, de hecho se crea una solución y no un subproblema que requiere más investigación. Estas soluciones son

Iteración 3 (II)

Nótese que las restricciones 2x4 ≤-4 y x4 ≥ 0 en la soltura de PL del subproblema 6 evitan las soluciones factibles. Por lo tanto, este subproblema se sondea por la prueba 2. No obstante, el subproblema 5 no pasa esta prueba, ni la 1(16 > 9) ni la prueba 3 (x4 = 1/2 no es un entero), así que permanece bajo consideración.

En la figura 13.6 se muestra el árbol de solución.

Iteración 3 (I)

Hasta aquí, el algoritmo ha creado cuatro subproblemas. El subproblema 1 quedó sondeado y el subproblema 2 se sustituyó por (se dividio  en) los subproblemas 3 y 4, pero estos dos últimos quedan bajo consideración. Como fueron creados al mismo  tiempo pero el subproblema 4 (x1 =1, x2 =1 ) tiene una cota más grande (16 > 3), la siguiente ramificaciónse hace desde el nodo (x1,x2) = (1,1)  en el árbol de solución,  lo que crea los siguientes subproblemas nuevos.

Iteración 2 (II)

Obsérvese que estas cotas son más grandes que Z* = 9, así que la prueba de sondeo 1 fracasa en ambos casos. La prueba 2 también fracasa, ya que ambas solturas de PL tienen soluciones factibles (como lo indica la existencia de una solución óptima). La prueba 3 también fracasa, porque ambas soluciones óptimas incluyen variables con valores no enteros.

La figura 13.5 muestra el árbol de solución resultante en este punto. La falta de una S a la derecha de cualquiera de los nuevos nodos indica que ambos quedan sin sondear.

Iteración 2 (I)

El único subproblema que queda corresponde al nodo x1 = 1 en la figura 13.4, entonces se ramificará este nodo para crear dos nuevos subproblemas:

Final del ejemplo

El patrón para las iteraciones que faltan será muy similar al de la primera iteración que se acaba de describir, excepto por la forma en que ocurre el sondeo. Así, se resumirán los pasos de la ramificación y acotamiento y se hará hincapié en el paso de sondeo.

Sondeo IV

El paso de ramificación para este algoritmo amerita un comentario respecto a la razón por la que se elige de esta manera el subproblema que se va a ramificar. Una opción que no se usó sería elegir el subproblema restante con la mejor cota, ya que este subproblema sería el más prometedor en cuanto a contener la solución óptima para el problema completo. La razón para usar la opción de seleccionar el subproblema de creación más reciente es que las solturas de PL, se resuelven en el paso de acotamiento. En lugar de iniciar el método símplex cada vez desde el principio, cada soltura de PL en los problemas de gran escala se puede resolver casi siempre por reoptimización. Esta reoptimización implica revisar la tabla símplex final de la soltura de PL anterior, según sea necesario debido a las pocas diferencias en el modelo (igual que para análisis de sensibilidad), y después aplicar unas cuantas iteraciones quizá del método símplex dual. Esta reoptimización tiende a ser mucho más rápida que comenzar desde el principio, siempre que el modelo anterior y el actual sean parecidos. Los modelos tenderán a parecerse si se usa la regla de ramificación descrita, pero no cuando van de un lado a otro en el árbol de solución, como cuando se elige el subproblema con la mejor cota.

Resumen de la técnica de ramificación y acotamiento de PEB: Prueba de optimalidad

El proceso termina cuando no existen subproblemas restantes; la solución incumbente o de  apoyo actual es la solución óptima. De otra manera, se realiza otra iteración.

Resumen de la técnica de ramificación y acotamiento de PEB: Paso para cada iteración

1. Ramificación: entre los subproblemas restantes (no sondeados) se elige el de creación más reciente. (Los empates se rompen con el que tenga la cota más grande.)  Se ramifica este nodo en ese subproblema, para crear dos nuevos subproblemas fijando la siguiente variable (la variable de ramificación) ya sea en 0 o en 1.
2. Acotamiento: para cada nuevo subproblema se obtiene su cota aplicando el método simplex  a su soltura de PL y redondeando hacia abajo el valor de Z en la solución óptima que resulta.
3. Sondeo: para cada nuevo subproblema se aplican las tres pruebas de sondeo que se resumieron antes y se descartan aquellos subproblemas que quedan sondeados por cualquiera de las tres pruebas.

Resumen de la técnica de ramificación y acotamiento de PEB: Paso inicial

Paso inicial: se establece Z* = -∞. Se aplican al problema completo, el paso de acotamiento, el paso de sondeo y la prueba de optimalidad que se describen. Si no se sondea, este problema se clasifica como el único "subproblema" restante para realizar la primera iteración completa.

Resumen de las pruebas de sondeo (II)

La figura 13.4 resume los resultados después de aplicar estas tres pruebas a los subproblemas 1 y 2, mostrando el árbol de solución actual. Nada más el subproblema 1 se sondeó por la prueba de sondeo 3, como lo indica la S(3) junto al nodo x1 = 0. La solución de apoyo también se identifica debajo de este nodo.

Las iteraciones siguientes ilustrarán la aplicación exitosa de las tres pruebas, pero antes de continuar con el ejemplo se resumirá el algoritmo que se está aplicando a este problema de PEB. (El algoritmo supone que todos los coeficientes de la función objetivo son enteros y que el orden de las variables para la ramificación es x1, x2,......xn).

Resumen de las pruebas de sondeo (I)

Un subproblema se sondea (elimina) si

Prueba 1: su cota ≤ Z*,
o
Prueba 2: Su soltura de PL no tiene soluciones factibles,

o

Prueba 3: la solución óptima para su soltura de PL es entera. (Si esta solución es mejor que la de apoyo, se convierte en la nueva de apoyo y se aplica de nuevo la prueba 1 a todos los subproblemas no sondeados, con la nueva Z* mejor.)

Sondeo (III)

La tercera forma de sondeo es bastante directa. Si el método símplex encuentra que la soltura de PL de un subproblema no tiene soluciones factibles, entonces el subproblema en sí no debe tener soluciones factibles, de forma que puede eliminarse (sondearse).

En los tres casos, se busca una solución óptima reteniendo sólo aquellos subproblemas que posiblemente tengan una mejor solución factible que la de apoyo actual.

Sondeo (II)

Los resultados anteriores sugieren una segunda prueba de sondeo importante. Como Z* = 9, no existe razón alguna para toma en cuenta ningún subproblema cuya cota ≤ 9, ya que tales subproblemas no pueden tener soluciones factibles mejores que la incumbente.
Establecido en forma general, un subproblema se sondea siempre que su

Cota ≤ Z*

Esto ocurre en la iteracción actual del ejemplo porque el subproblema 2 tiene una cota de 16 que es mayor que 9. No obstante, puede ocurrir más adelante, para los descendientes de este subproblema (nuevos problemas más pequeños creados al ramificar más este subproblema y quizá después al ramificarlo más en "generaciones" subsecuentes) Lo que es más, conforme se encuentren nuevas soluciones de apoyo con valores más grandes de Z*, será más fácil sondear de esta manera.

Sondeo (I)

Un subproblema se puede vencer (sondear) y por lo tanto ya no tomarse en cuenta, en las tres formas que se describen a continuación.

Una de estas formas se ilustra con los resultados del subproblema 1 dados en el nodo x1 = 0, en la figura 13.3. Nótose que la solución óptima (única) de esta soltura de PL, (x1, x2, x3, x4) = (0,1, 0, 1), es una solución entera. Entonces, esta solución debe ser también la solución óptima para el subproblema 1 en sí. Esta solución debe almacenarse como la primera solución incumbente o de apoyo (la primera solución factible que se ha encontrado hasta ahora) para el problema completo, junto con su valor de Z. Este valor se denota por

Z* = valor de Z para la solución de apoyo actual,

de manera que en este punto Z* = 9. Una vez almacenada esta solución, no hay razón para seguir tomando en cuenta el subproblema 1 y ramificar el nodo x1 = 0. Hacerlo sólo conduciría a otras soluciones factibles inferiores a la de apoyo que no son de interés. Ahora, como ya se resolvió, el subproblema 1 se sondea (elimina).

Acotamiento (III)

Ahora se obtendrá, de la misma manera, las cotas para los subproblemas. Sus solturas de PL se obtienen de los modelos de la subsección anterior sustituyendo 0 ≤ xj ≤ 1 para j = 2,3,4, en lugar de las restricciones, xj es binaria para j = 2,3,4. Al aplicar el método símplex se obtienen su soluciones óptimas (además del valor fijo de x1).

Soltura de PL del subproblema 1: (x1, x2, x3, x4) = (0, 1, 0, 1), con Z = 9
Soltura de PL del subproblema 2: (x1, x2, x3, x4) = (1, 4/5, 0, 4/5), con Z = 16(1/5)

Las cotas que se obtienen son entonces

Cota para el subproblema 1: Z ≤ 9
Conta para el subproblema 2: Z ≤ 16.

La figura 13.3 resume estos resultados, en donde los números que se encuentran justo abajo de los nodos son las cotas, y debajo de cada cota se da la solución óptima obtenida para la soltura de PL.

Acotamiento (II)

Por tanto, Z ≤ 16(1/2) para todas las soluciones factibles del problema original de PEB (ya que estas soluciones son un subconjunto de las soluciones factibles de la soltura de PL). De hecho, como se resume en seguida, esta cota de 16(1/2) se puede redondear a 16, ya que todos los coeficientes de la función objetivo son enteros y por ende deben dar un valor entero de Z.

Conta para todo el problema: Z ≤ 16.