Ramificar y enlazar
El algoritmo Branch and bound es una enumeración "inteligente" del árbol de posibles soluciones.
Como sugiere su nombre, el algoritmo tiene dos tiempos:
- separación: separar un conjunto de soluciones en subconjuntos;
- evaluación: evalúa las soluciones de un subconjunto aumentando el valor de la mejor solución de este subconjunto.
El algoritmo de bifurcación y cota (separación y evaluación) propone recorrer la estructura de á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 menor que 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
La ramificación y el límite comienzan 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
La rama y el límite se turnan para evaluar cada separación. La raíz del árbol es una solución admisible que nos servirá de referencia. Obtenemos así una solución que da un valor z aumentando la solución óptima.
A menudo, la evaluación se realiza sobre el problema inicial después de la relajación. Una relajación permite pasar de restricciones complejas a restricciones lineales o cuya dual es simple. Por ejemplo, la relajación de la integridad permite trabajar con variables reales en lugar de variables completas.
Una vez realizada la valoración son posibles 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 lleva a cabo 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 yz = 60,75. Es una solución inadmisible, por lo tanto, se separa en comparación con xPARA :
- XPARA=1. la problema lineal relajado da xVS= 1/4 yz = 60,25. Ésta es una solución inaceptable. Ya no es posible separar porque no hay más 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, así 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).
ES 
FR 
EN