Ramificar y enlazar - Branch and bound

Branch and bound ( BB , B&B o BnB ) es un paradigma de diseño de algoritmos para problemas de optimización discreta y combinatoria , así como optimización matemática . Un algoritmo de ramificación y acotación consiste en una enumeración sistemática de soluciones candidatas mediante la búsqueda en el espacio de estados : se piensa que el conjunto de soluciones candidatas forma un árbol enraizado con el conjunto completo en la raíz. El algoritmo explora las ramas de este árbol, que representan subconjuntos del conjunto de soluciones. Antes de enumerar las soluciones candidatas de una rama, la rama se compara con los límites estimados superior e inferior de la solución óptima y se descarta si no puede producir una solución mejor que la mejor encontrada hasta ahora por el algoritmo.

El algoritmo depende de una estimación eficiente de los límites superior e inferior de las regiones / ramas del espacio de búsqueda. Si no hay límites disponibles, el algoritmo degenera en una búsqueda exhaustiva.

El método fue propuesto por primera vez por Ailsa Land y Alison Doig mientras realizaban una investigación en la London School of Economics patrocinada por British Petroleum en 1960 para programación discreta , y se ha convertido en la herramienta más utilizada para resolver problemas de optimización NP-hard . El nombre "rama y límite" apareció por primera vez en el trabajo de Little et al. sobre el problema del viajante .

Descripción general

El objetivo de un algoritmo de ramificación y límite es encontrar un valor x que maximice o minimice el valor de una función de valor real f ( x ) , llamada función objetivo, entre algún conjunto S de soluciones admisibles o candidatas . El conjunto S se denomina espacio de búsqueda o región factible . El resto de esta sección asume que se desea la minimización de f ( x ) ; esta suposición viene sin pérdida de generalidad , ya que uno puede encontrar el valor máximo de f ( x ) encontrando el mínimo de g ( x ) = - f ( x ) . Un algoritmo B&B funciona según dos principios:

  • Divide de forma recursiva el espacio de búsqueda en espacios más pequeños, luego minimiza f ( x ) en estos espacios más pequeños; la división se llama ramificación .
  • La ramificación por sí sola equivaldría a una enumeración de fuerza bruta de soluciones candidatas y probarlas todas. Para mejorar el rendimiento de la búsqueda de fuerza bruta, un algoritmo B&B realiza un seguimiento de los límites del mínimo que está tratando de encontrar y usa estos límites para " podar " el espacio de búsqueda, eliminando las soluciones candidatas que puede probar que no contendrán. una solución óptima.

Convertir estos principios en un algoritmo concreto para un problema de optimización específico requiere algún tipo de estructura de datos que represente conjuntos de soluciones candidatas. Tal representación se denomina instancia del problema. Denotar el conjunto de soluciones candidatas de una instancia que por S I . La representación de la instancia tiene que venir con tres operaciones:

  • rama ( I ) produce dos o más instancias que representan cada uno un subconjunto de S I . (Por lo general, los subconjuntos están separados para evitar que el algoritmo visite la misma solución candidata dos veces, pero esto no es necesario. Sin embargo, una solución óptima entre S I debe estar contenida en al menos uno de los subconjuntos).
  • unido ( I ) calcula un límite inferior en el valor de cualquier solución candidato en el espacio representado por I , es decir, unido ( I ) ≤ f ( x ) para todo x en S I .
  • solution ( I ) determina si I representa una única solución candidata. (Opcionalmente, si no es así, la operación puede optar por devolver alguna solución factible de entre S I ). Si la solución ( I ) devuelve una solución, entonces f (solución ( I )) proporciona un límite superior para el valor objetivo óptimo sobre el Todo el espacio de soluciones viables.

Con estas operaciones, un algoritmo B&B realiza una búsqueda recursiva de arriba hacia abajo a través del árbol de instancias formado por la operación de bifurcación. Al visitar una instancia I , comprueba si el límite ( I ) es mayor que un límite superior encontrado hasta ahora; si es así, puedo ser descartado de forma segura de la búsqueda y la recursión se detiene. Este paso de poda generalmente se implementa manteniendo una variable global que registra el límite superior mínimo visto entre todas las instancias examinadas hasta ahora.

Versión genérica

El siguiente es el esqueleto de un algoritmo genérico de bifurcación y cota para minimizar una función objetiva arbitraria f . Para obtener un algoritmo real a partir de esto, se requiere un límite de función delimitador , que calcula los límites inferiores de f en los nodos del árbol de búsqueda, así como una regla de ramificación específica del problema. Como tal, el algoritmo genérico presentado aquí es una función de orden superior .

  1. Usando una heurística , encuentre una solución x h al problema de optimización. Almacene su valor, B = f ( x h ) . (Si no hay una heurística disponible, establezca B en infinito). B denotará la mejor solución encontrada hasta ahora y se utilizará como límite superior en las soluciones candidatas.
  2. Inicialice una cola para contener una solución parcial sin ninguna de las variables del problema asignadas.
  3. Repita hasta que la cola esté vacía:
    1. Saque un nodo N de la cola.
    2. Si N representa una única solución candidato x y f ( x ) < B , entonces x es la mejor solución hasta el momento. Regístrelo y establezca Bf ( x ) .
    3. De lo contrario, bifurque en N para producir nuevos nodos N i . Para cada uno de estos:
      1. Si límite ( N i )> B , no haga nada; dado que el límite inferior de este nodo es mayor que el límite superior del problema, nunca conducirá a la solución óptima y puede descartarse.
      2. De lo contrario, guarde N i en la cola.

Se pueden utilizar varias estructuras de datos de cola diferentes . Esta implementación basada en la cola FIFO produce una búsqueda en amplitud . Una pila (cola LIFO) producirá un algoritmo de profundidad . Se puede obtener un algoritmo de enlace y bifurcación del mejor primero utilizando una cola de prioridad que ordena los nodos en su límite inferior. Ejemplos de algoritmos de búsqueda del mejor primero con esta premisa son el algoritmo de Dijkstra y su búsqueda A * descendiente . La variante de profundidad primero se recomienda cuando no hay una buena heurística disponible para producir una solución inicial, porque rápidamente produce soluciones completas y, por lo tanto, límites superiores.

Pseudocódigo

Una implementación de pseudocódigo similar a C ++ de lo anterior es:

// C++-like implementation of branch and bound, 
// assuming the objective function f is to be minimized
CombinatorialSolution branch_and_bound_solve(
    CombinatorialProblem problem, 
    ObjectiveFunction objective_function /*f*/,
    BoundingFunction lower_bound_function /*bound*/) 
{
    // Step 1 above
    double problem_upper_bound = std::numeric_limits<double>::infinity; // = B
    CombinatorialSolution heuristic_solution = heuristic_solve(problem); // x_h
    problem_upper_bound = objective_function(heuristic_solution); // B = f(x_h)
    CombinatorialSolution current_optimum = heuristic_solution;
    // Step 2 above
    queue<CandidateSolutionTree> candidate_queue;
    // problem-specific queue initialization
    candidate_queue = populate_candidates(problem);
    while (!candidate_queue.empty()) { // Step 3 above
        // Step 3.1
        CandidateSolutionTree node = candidate_queue.pop();
        // "node" represents N above
        if (node.represents_single_candidate()) { // Step 3.2
            if (objective_function(node.candidate()) < problem_upper_bound) {
                current_optimum = node.candidate();
                problem_upper_bound = objective_function(current_optimum);
            }
            // else, node is a single candidate which is not optimum
        }
        else { // Step 3.3: node represents a branch of candidate solutions
            // "child_branch" represents N_i above
            for (auto&& child_branch : node.candidate_nodes) {
                if (lower_bound_function(child_branch) <= problem_upper_bound) {
                    candidate_queue.enqueue(child_branch); // Step 3.3.2
                }
                // otherwise, bound(N_i) > B so we prune the branch; step 3.3.1
            }
        }
    }
    return current_optimum;
}

En el pseudocódigo anterior, las funciones heuristic_solvey populate_candidatesllamadas como subrutinas deben proporcionarse según corresponda al problema. Las funciones f ( objective_function) y bound ( lower_bound_function) se tratan como objetos de función tal como están escritas y podrían corresponder a expresiones lambda , punteros de función o functores en el lenguaje de programación C ++, entre otros tipos de objetos invocables .

Mejoras

Cuando es un vector de , los algoritmos de bifurcación y límite se pueden combinar con análisis de intervalo y técnicas de contratista para proporcionar cerramientos garantizados del mínimo global.

Aplicaciones

Este enfoque se utiliza para una serie de problemas NP difíciles :

La ramificación y el límite también pueden ser la base de varias heurísticas . Por ejemplo, es posible que desee dejar de ramificar cuando el espacio entre los límites superior e inferior se vuelve más pequeño que un cierto umbral. Se utiliza cuando la solución es "suficientemente buena para fines prácticos" y puede reducir en gran medida los cálculos necesarios. Este tipo de solución es particularmente aplicable cuando la función de costo utilizada es ruidosa o es el resultado de estimaciones estadísticas y, por lo tanto, no se conoce con precisión, sino que solo se sabe que se encuentra dentro de un rango de valores con una probabilidad específica .

Relación con otros algoritmos

Nau y col. presentan una generalización de bifurcación y cota que también subsume los algoritmos de búsqueda A * , B * y alfa-beta .

Ver también

Referencias

enlaces externos

  • LiPS : programa GUI gratuito y fácil de usar destinado a resolver problemas de programación lineal, de enteros y de objetivos.
  • Cbc - (Coin-or branch and cut) es un solucionador de programación de enteros mixtos de código abierto escrito en C ++.