Método de rama y límite
El método de ramificación y acotación es un método algorítmico general para encontrar soluciones óptimas a varios problemas de optimización, especialmente la optimización discreta y combinatoria . El método es un desarrollo del método de enumeración exhaustiva , a diferencia de este último, con la eliminación de subconjuntos de soluciones factibles que obviamente no contienen soluciones óptimas.
El método de bifurcación y acotación fue propuesto por primera vez en 1960 por Alice Land y Alison Doig [1] para resolver problemas de programación entera .
La idea general del método se puede describir con el ejemplo de encontrar el mínimo de una función en el conjunto de valores permitidos de la variable . La función y la variable pueden ser de naturaleza arbitraria. El método de ramificación y vinculación requiere dos procedimientos: ramificación y búsqueda de estimaciones (límites).
El procedimiento de bifurcación consiste en dividir el conjunto de valores admisibles de una variable en subdominios (subconjuntos) de menor tamaño. El procedimiento se puede aplicar recursivamente a los subdominios. Los subdominios resultantes forman un árbol , llamado árbol de búsqueda o árbol ramificado y enlazado . Los nodos de este árbol son los subdominios construidos (subconjuntos del conjunto de valores de la variable ).
El procedimiento para encontrar estimaciones consiste en encontrar cotas superior e inferior para resolver el problema en el subdominio de valores admisibles de la variable .
El método de bifurcación y límite se basa en la siguiente idea: si el límite inferior de los valores de función en un subdominio del árbol de búsqueda es mayor que el límite superior en cualquier subdominio visto anteriormente , entonces puede excluirse de una consideración posterior ( regla de abandono ). Por lo general, el mínimo de los límites superiores obtenidos se escribe en una variable global ; cualquier nodo del árbol de búsqueda cuyo límite inferior sea mayor que , se puede excluir de una consideración posterior.
Si el límite inferior de un nodo de árbol coincide con el límite superior, entonces este valor es el mínimo de la función y se alcanza en el subdominio correspondiente.
El método se utiliza para resolver algunos problemas NP-completos , incluido el problema del viajante de comercio y el problema de la mochila .
Véase también
Notas
- ↑ AH Land y A.G. Doig . Un método automático para resolver problemas de programación discreta , pp. 497-520.