Ramificar y enlazar
El algoritmo Branch andbound es una enumeración “inteligente” del árbol de posibles soluciones.
Como su nombre indica, el algoritmo tiene dos etapas:
- separación: separar un conjunto de soluciones en subconjuntos;
- evaluación: evaluar las soluciones de un subconjunto aumentando el valor de la mejor solución de este subconjunto.
El algoritmo Branch andbound propone recorrer el árbol de posibles soluciones evaluando cada subconjunto de soluciones. Mantiene en memoria el valor de la mejor solución f(s) encontrada hasta el momento. Cuando la evaluación de un subconjunto da un valor inferior a f(s), el algoritmo considera inútil explorarlo directamente después.
El algoritmo de rama y límite se usa a menudo en lugar del programación dinámica. La evaluación es a menudo la función objetivo con restricciones relajadas (por número decreciente) según la profundidad.
La separación
Rama y límite comienza con la separación. El conjunto de soluciones se separa fijando el valor de una o más variables del problema. Supongamos un problema con tres variables, el árbol completo de separación en orden ascendente de las variables es el siguiente:
Existen dos técnicas de exploración, vinculadas a las trayectorias de un árbol. La amplitud primero consiste en favorecer la ampliación de posibilidades aumentando la profundidad, no hay retroceso. La profundidad primero favorece la ampliación de posibilidades visitando las hojas más profundas. La ventaja es proporcionar rápidamente soluciones "buenas" y eliminar ramas subóptimas.
Evaluación
Rama y límite evalúa cada división a su vez. La raíz del árbol es una solución admisible que servirá de referencia. Obtenemos así una solución que da un valor z aumentando la solución óptima.
La evaluación se realiza a menudo sobre el problema inicial después de la relajación. Una relajación permite pasar de restricciones complejas a restricciones lineales o cuyo dual es simple. Por ejemplo, una relajación de integridad permite trabajar con variables reales en lugar de variables enteras.
Una vez realizada la evaluación, se pueden dar dos casos:
- Si la evaluación (SI) ≥z, luego SI no contiene ninguna solución óptima, no es útil explorar en detalle el subconjunto SI.
- Si la evaluación (SI) <z, alors on teste l’admissibilité de la solution d’évaluation. Si elle est admissible, on actualise z, sinon on continue l’exploration jusqu’à l’obtention d’une des conditions précédentes.
Ejemplo: problema de mochila
Un avión de carga tiene una capacidad de carga de 18 unidades de volumen. Debe transportar contenedores de mercancías de tal manera que maximice el valor total de su carga. Los contenedores disponibles están en cantidad ilimitada para cada tipo:
- Contenedor tipo A, valor 6, volumen 2;
- Contenedor tipo B, valor 8, volumen 3;
- Contenedor tipo C, valor 13, volumen 4;
- Contenedor tipo D, valor 17, volumen 5;
- Contenedor tipo E, valor 20, volumen 7.
Al principio, resolveremos el problema usando un algoritmo glotón. Luego determinaremos la solución óptima mediante un procedimiento Branch&Bound.
los modelo matematico del problema es el siguiente sistema: max z=6*xPARA+ 8 * xB+ 13 * xVS+ 17 * xD+ 20 * xmi menos de 2 * xPARA+ 3 * xB+ 4 * xVS+ 5 * xD+ 7 * xmi≤18 con xI el número entero de contenedores de tipo i.
La solución inicial se logra mediante el algoritmo codicioso de la mejor relación valor/volumen. Obtenemos el vector solución (1,0,0,3,0) con z=57. XD siendo el mayor, realizaremos la separación en este criterio. Obtendremos 4 ramas para respectivamente xD= 3, 2, 1 y 0:
- XD=3. Resolvemos el programa lineal relajado lo que da xVS=3/4 y z=60,75. Esta es una solución inadmisible por lo que separamos con respecto a xPARA :
- XPARA=1. la problema lineal relajado da xVS=1/4 y z=60,25. Esta es una solución inadmisible. Ya no es posible separar porque ya no hay xI> 0. La solución completa más cercana se reduce a nuestra solución inicial aproximada.
- XPARA= 0. El problema lineal relajado da xB= 1. La solución es admisible y da z = 59. Actualizamos z.
- XD= 2. Resolvemos el programa lineal relajado que da xVS=2 yz=60. Es una solución admisible por lo que actualizamos z.
- XD= 1. Resolvemos el programa lineal relajado que da xVS= 13/4 yz = 59,25. Este límite es menor que z, por lo que no visitamos esta rama.
- XD= 0. Resolvemos el programa lineal relajado que da xVS= 9/2 yz = 58,5. Este límite es menor que z, por lo que no visitamos esta rama.
Se explora toda la zona. El óptimo z*=60 se obtuvo con el vector solución (0,0,2,2,0).
