Método de ramificación y acotación

From Systems analysis wiki
Jump to navigation Jump to search

El método de ramificación y acotación (en inglés, Branch and Bound, abreviado B&B o BnB) es un paradigma general para la construcción de algoritmos exactos para resolver problemas de optimización discreta y combinatoria, en particular problemas NP-difíciles[1]. El método consiste en una estrategia de búsqueda sistemática en la que el conjunto de soluciones factibles se divide sucesivamente en subconjuntos (ramificación), y para cada uno de ellos se calculan estimaciones (acotaciones) del valor de la función objetivo. Estas estimaciones permiten descartar (podar) aquellos subconjuntos que se sabe que no contienen soluciones óptimas, lo que reduce significativamente el espacio de búsqueda[2].

El método fue propuesto por primera vez por A. H. Land y A. G. Doig en 1960 para resolver problemas de programación entera[3]. Desde entonces, se ha convertido en uno de los enfoques más fundamentales en la investigación de operaciones y las ciencias de la computación. La característica clave del método es su flexibilidad: no es un algoritmo específico, sino un esquema estratégico de alto nivel (un marco de trabajo o framework), que se adapta a la estructura del problema a resolver.

Componentes clave del método

El método se basa en tres operaciones fundamentales que se aplican a los subconjuntos del espacio de soluciones, organizados en forma de un árbol de búsqueda.

  • Ramificación (en inglés, Branching) — es el proceso de dividir recursivamente el conjunto actual de soluciones factibles Si en varios subconjuntos más pequeños, generalmente disjuntos, Si1,Si2,…,Sik. Cada uno de estos subconjuntos corresponde a un nuevo subproblema y se representa como un nodo hijo en el árbol de búsqueda. Por ejemplo, en problemas de programación entera, la ramificación se realiza a menudo sobre una variable que tiene un valor fraccionario en la solución de la relajación LP.
  • Acotación (en inglés, Bounding) — para cada nodo del árbol de búsqueda (es decir, para cada subproblema), se calcula una estimación del valor de la función objetivo. Para un problema de minimización, esta es una cota inferior (lower bound), que es una estimación garantizada por debajo para cualquier solución en ese subconjunto. Generalmente, esta cota se obtiene resolviendo una relajación del subproblema original, una versión simplificada en la que algunas restricciones complejas (como las de integridad) se ignoran temporalmente. La relajación más común es la relajación de programación lineal (relajación LP).
  • Poda (en inglés, Pruning) — es el proceso de eliminar de la consideración los nodos (y sus subárboles correspondientes) que se sabe que no pueden contener una solución óptima. Un nodo se poda en uno de los siguientes casos:
  1. Poda por cota: La cota inferior para un nodo dado no es mejor (es decir, es mayor o igual para un problema de minimización) que el valor de la mejor solución factible encontrada hasta el momento, conocida como incumbente (incumbent).
  2. Poda por factibilidad: La solución de la relajación del nodo es factible para el problema original (por ejemplo, todas las variables son enteras). Esta solución se compara con el incumbente actual y, si es mejor, el incumbente se actualiza. No se requiere más ramificación desde este nodo.
  3. Poda por infactibilidad: El subproblema correspondiente al nodo no tiene soluciones factibles.

Algoritmo general

El algoritmo general del método de ramificación y acotación para un problema de minimización se puede describir con los siguientes pasos:

  1. Inicialización: Encontrar una solución factible inicial (por ejemplo, mediante una heurística) y establecer su valor como la cota superior inicial (incumbente) U. Crear una cola de nodos activos Q que contenga el nodo raíz (el problema original).
  2. Bucle principal: Mientras la cola Q no esté vacía:
    • Seleccionar un nodo de Q según una estrategia de búsqueda (por ejemplo, búsqueda en profundidad o búsqueda por la mejor cota).
    • Resolver la relajación para este nodo para obtener una cota inferior L.
    • Podar el nodo si L≥U.
    • Si la solución de la relajación es factible para el problema original, actualizar el incumbente: U←L.
    • Si el nodo no se poda y la solución no es factible, realizar la ramificación, dividiéndolo en nodos hijos, y añadirlos a la cola Q.
  3. Terminación: Cuando la cola Q se vacía, el algoritmo termina. La solución encontrada, correspondiente al incumbente U, es globalmente óptima.

Propiedades y teoremas clave

  • Corrección y convergencia: El algoritmo garantiza encontrar la solución óptima global en un número finito de pasos, si el conjunto de soluciones factibles es finito y el procedimiento de ramificación es convergente (es decir, durante la división recursiva, los subconjuntos se "contraen" hacia puntos)[4].
  • Estrategia de búsqueda: La eficiencia del algoritmo depende en gran medida de la estrategia para seleccionar el siguiente nodo a ramificar (por ejemplo, búsqueda en profundidad, búsqueda en anchura, búsqueda por la mejor cota) y de la elección de la variable para la ramificación. Los solvers modernos suelen utilizar estrategias híbridas[5].

Ejemplos

  • Problema de programación entera: Una aplicación clásica del método. Como relajación se utiliza la programación lineal. La ramificación se realiza sobre una variable fraccionaria xj, creando dos subproblemas con las restricciones adicionales xj≤⌊xj*⌋ y xj≥⌈xj*⌉.
  • Problema del viajante de comercio: El espacio de soluciones son todos los posibles ciclos hamiltonianos en un grafo. La ramificación puede realizarse sobre las aristas (incluir/excluir una arista de la ruta). Como cotas inferiores se pueden utilizar soluciones de problemas más sencillos, como el problema de asignación o la construcción de un árbol de expansión mínima[6].

Conceptos relacionados y aplicaciones

  • Método de ramificación y corte (Branch-and-Cut): Un método híbrido que combina B&B con el método de los planos de corte. En cada nodo del árbol de búsqueda, además de resolver la relajación, se generan desigualdades adicionales (cortes) que refuerzan la cota inferior, lo que conduce a una poda más eficiente de las ramas.
  • Búsqueda con retroceso (Backtracking): El método de ramificación y acotación puede considerarse una generalización de este algoritmo para problemas de optimización.
  • Poda alfa-beta: Una analogía conceptual utilizada en árboles de juego para podar ramas que se sabe que conducen a una derrota.

Véase también

  • Programación entera
  • Optimización combinatoria
  • Problema del viajante de comercio
  • Problema NP-difícil
  • Método símplex

Referencias

  1. ↑ Wikipedia contributors. (2025). Branch and bound. In Wikipedia, The Free Encyclopedia. Retrieved 2025-10-26, from https://en.wikipedia.org/wiki/Branch_and_bound
  2. ↑ Wikipedia contributors. (2023). Método de ramificación y acotación. En Wikipedia en ruso. Consultado el 2025-10-26, de https://ru.wikipedia.org/wiki/Метод_ветвей_и_границ
  3. ↑ Land, A. H.; Doig, A. G. (1960). An automatic method of solving discrete programming problems. Econometrica, 28(3), 497–520. DOI: 10.2307/1910129. URL: https://www.jstor.org/stable/1910129
  4. ↑ Conitzer, V. (2008). Solving (mixed) integer programs using branch and bound. Duke University, Department of Computer Science. URL: https://courses.cs.duke.edu/spring08/cps296.2/branch_and_bound.pdf
  5. ↑ Maudet, G.; Danoy, G. (2024). Search Strategy Generation for Branch and Bound Using Genetic Programming. arXiv preprint arXiv:2412.09444. DOI: 10.48550/arXiv.2412.09444. URL: https://arxiv.org/abs/2412.09444
  6. ↑ Little, J. D. C.; Murty, K. G.; Sweeney, D. W.; Karel, C. (1963). An Algorithm for the Traveling Salesman Problem. Operations Research, 11(6), 972–989. DOI: 10.1287/opre.11.6.972. URL: https://dspace.mit.edu/bitstream/handle/1721.1/46907/branchboundmetho00litt.pdf
Retrieved from "https://systems-analysis.ru/int/index.php?title=Método_de_ramificación_y_acotación&oldid=368"