Ramificación y poda
El término (del inglés, Branch and Bound) se aplica mayoritariamente para resolver cuestiones o problemas de optimización.
La técnica de ramificación y poda se suele interpretar como un árbol de soluciones, donde cada rama conduce a una posible solución posterior a la actual.
La característica de esta técnica con respecto a otras anteriores (y a la que debe su nombre) es que el algoritmo se encarga de detectar en qué ramificación las soluciones dadas ya no están siendo óptimas, para «podar» esa rama del árbol y no continuar malgastando recursos y procesos en casos que se alejan de la solución óptima.
cuya unión cubre S. Nótese que el mínimo de f(x) sobre S es min{
La idea clave del algoritmo de ramificación y poda es: si la menor rama para algún árbol nodo(conjunto de candidatos) A es mayor que la rama padre para otro nodo B, entonces A debe ser descartada con seguridad de la búsqueda.
Este paso es llamado poda, y usualmente es implementado manteniendo una variable global m que graba el mínimo nodo padre visto entre todas las subregiones examinadas hasta entonces.
Idealmente, el procedimiento se detiene cuando todos los nodos del árbol de búsqueda están podados o resueltos.
En ese punto, todas las subregiones no podadas, tendrán un nodo padre e hijo iguales a una función global mínima.
Alternativamente, sin superar un tiempo restringido, el algoritmo debe terminar cuando un criterio de error, tal que (max-min)/(max+min), cae bajo un valor específico.
Una mala elección puede llevarnos a una repetida ramificación, sin poda, hasta que las subregiones se conviertan en muy pequeñas.
Este método naturalmente lleva a una forma de implementación paralela y distribuida, como podemos ver por ejemplo en el Problema del Viajante de Comercio.
Nuestro objetivo principal será eliminar aquellos nodos que no lleven a soluciones buenas.
Supongamos un problema de maximización donde se han recorrido varios nodos i=1,…,n.
estimando para cada uno la cota superior CS(xi) e inferior CI(
) = 5, esto nos llevará a la conclusión de que se puede podar el nodo
Si se obtiene una posible solución válida para el problema con un beneficio
Debido a esto todos los nodos de un nivel deben ser expandidos antes de alcanzar un nuevo nivel, cosa que es lógica ya que para poder elegir la rama del árbol que va a ser explorada, se deben conocer todas las ramas posibles.
Todos estos nodos que se van generando y que no han sido explorados se almacenan en lo que se denomina Lista de Nodos Vivos (a partir de ahora LNV), nodos pendientes de expandir por el algoritmo.
Según como estén almacenados los nodos en la lista, el recorrido del árbol será de uno u otro tipo, dando lugar a las tres estrategias que se detallan a continuación.
En la estrategia LIFO (Last In First Out), la LNV será una pila, produciendo un recorrido en profundidad del árbol.
Por lo tanto ya no estamos hablando de un avance “a ciegas”.
-Estrategia LC-LIFO: Elige de la LNV el nodo que tenga mayor beneficio y en caso de empate se escoge el último que se introdujo.
Un variante del método de ramificación y poda más eficiente se puede obtener “relajando” el problema, es decir, eliminando algunas de las restricciones para hacerlo más permisivo.
Este método resuelve programas lineales sin restricciones enteras usando algoritmos regulares simplificados.
Cuando se obtiene una solución óptima que tiene un valor no entero para una variable que ha de ser entera, el algoritmo de planos de corte se usa para encontrar una restricción lineal más adelante que sea satisfecha por todos los puntos factibles enteros, pero violados por la solución fraccional actual.
En este punto comienza la parte del algoritmo de ramificación y poda.
Los nuevos programas lineales se resuelven usando un método simplificado y después el proceso repetido hasta que una solución satisfaga todas las restricciones enteras.
Durante el proceso de ramificación y poda, los planos de corte se pueden separar más adelante y pueden ser o cortes globales válidos para todas las soluciones enteras factibles, o cortes locales que son satisfechos por todas las soluciones llenando todas las ramas de la restricción del subárbol de ramificación y poda actual.
Esto es usado cuando la solución es suficientemente buena para el problema propuesto, y puede reducir gratamente la complejidad computacional.
