ALGORITMO

BRANCH AND
BOUND
En este unidad se plantea una metodología para la solución del problema
del planeamiento de sistemas secundarios de distribución considerando un
modelo de programación lineal entero mixto (PLEM), el cual considera la
ubicación y dimensionamiento de transformadores de distribución, el
dimensionamiento y rutas de circuitos secundarios y sus costos variables.
Para la solución del problema se emplea el algoritmo Branch and Bound.
Los resultados obtenidos en un sistema de prueba empleado en la literatura
especializada muestran la validez y efectividad de la metodología propuesta.

Existen muchos problemas de optimización para los cuales no se conocen

métodos de solución directos, o bien, son ineficientes. Los problemas
pueden ser difíciles porque su función objetivo o las restricciones son no
convexas,, o porque algunas de las variables están restringidas a valores
discretos.
El algoritmo permite resolver problemas difíciles mediante la aplicación de
métodos de solución para problemas fáciles, además ha resultado ser una
de las mejores herramientas para la solución de problemas de optimización.
La idea general es dividir el problema en partes
manejables. Si las soluciones de los casos más pequeños
se obtienen de forma sencilla, entonces la solución del
problema original puede ser obtenida por medio de una
combinación de dichas soluciones. Si los casos más
pequeños continúan siendo muy difíciles de resolver,
entonces pueden ser divididos en instancias aún más
pequeñas. Este proceso continua hasta que los problemas
derivados son tan pequeños que fácilmente se puede
obtener una solución.
Una forma típica de representar esta técnica es por medio de
un árbol de enumeración. Un ejemplo de éste se muestra en la
siguiente figura.

La solución de un problema se obtiene yendo hacia abajo en el

árbol y con las soluciones de los casos más pequeños.
Se debe diseñar una estrategia para cada problema a tratar, la
cual debe de estar constituida de las siguientes partes:
• Dividir/Ramificar un problema en uno o más casos
pequeños. Construir un conjunto finito y contable que
contenga todas las soluciones del problema. Particionar
recursivamente un conjunto no vacío de soluciones, en
subconjuntos disjuntos.
• Conquistar/Resolver cada uno de los casos más pequeños. A
menos que uno de los casos no sea lo suficientemente
pequeño usar la recursión para realizar esto.
• Acotar. Si es necesario, combinar las soluciones de los
casos más pequeños para obtener la solución del problema
original. De lo contrario, eliminar las que no cumplen con los
objetivos propuestos.
Para escoger la variable sobre la que se ramificará se
tienen tres posibilidades ”Regla de Ramificación”.
• La primera variable no entera encontrada, es decir, la
variable no entera de subíndice menor.
• La variable no entera de mayor parte fraccionaria.
• La variable no entera “menos entera”, es decir la
variable más alejada de los dos enteros que la rodean,
o lo que es lo mismo, la variable cuya parte fraccionaria
esta más cerca de 0.5.
Escoger el nodo sobre el que se realizará la búsqueda,
escoger la rama del árbol.
• Búsqueda en Profundidad (Depth-first search). Se
selecciona un hijo del nodo precedente después de
ramificar y retrocede (moverse hacia atrás en el árbol
de búsqueda para seleccionar el siguiente nodo)
algunos nodos como sea posible después de podar el
nodo.
• Búsqueda a lo Ancho (Breadth-first search). Se
selecciona el nodo que esta más cerca de la parte
superior del árbol.
• Mejor Cota (Best Bound search). Se selecciona el nodo
con la mejor cota inferior.
Combinaciones de las anteriores:
• Búsqueda a lo ancho para cierto numero de nodos
seguido de búsqueda en profundidad.
• Búsqueda en profundidad mientras que se realice la
ramificación y entonces utilizar la Mejor Cota después de
podar el nodo.

La Búsqueda en Profundidad permite obtener soluciones

rápidas, pero con el riesgo de que la calidad de la
solución se vea afectada si se realizan malas
ramificaciones. Por otro lado, la Búsqueda a lo Ancho
rechaza el riesgo de trabajar en paralelo, por lo que en
este trabajo se utiliza este tipo de búsqueda.
Después de estudiar un nodo, se pueden presentar tres casos:
• La solución no es entera, se escoge una variable para bifurcar y
se crean dos nodos hijos.
• La solución es entera, se actualiza el valor de la función objetivo y
se descarta el nodo.
• No hay solución y se sondea el nodo.

En 1960 Land y Doing desarrollaron un mejor enfoque de este

algoritmo para los problemas MIP, posteriormente Gilmore (1962) y
Lawler (1963) independientemente resolvieron el QAP (problema
base para el FLP). El algoritmo inicia con la solución de la relajación
lineal, si la solución encontrada es entera el algoritmo termina. En
otro caso se escoge una variable xi con valor fraccional x*i y se
resuelven dos sub-problemas, uno en donde al problema original se
le añade la restricción xi ≥ [x*i] (donde [x*i] es el menor entero mayor
que x*i) y al segundo problema se le añade la restricción xi ≥ [x*i]
(donde [x*i] es el entero más grande menor que x*i).
El algoritmo continúa construyendo nuevos problemas lineales
siguiendo una estructura de árbol en donde cada nodo
representa los subproblemas a resolver (branching). Una
ramificación puede ser acotada (bounding) si es una solución
óptima entera o si el valor de la solución óptima es mayor que
la actual cota, esto es, mejora la solución actual entera.
Su principal ventaja es que elimina selectivamente la gran
mayoría de soluciones incluso antes de buscarlas. La
desventaja de esta técnica se da en los problemas en los que
la relajación lineal no se aproxima al conjunto convexo más
pequeño que contiene todos los puntos factibles enteros, por
lo que se generan una gran cantidad de subproblemas y se
tiene que explorar todos los posibles diseños hasta concluir
que no existe solución.
Cuando el numero de restricciones lineales es grande o
cuando la relajación lineal es reforzada mediante la adición de
desigualdades validas, generalmente se tiene un problema de
tamaño exponencial, por lo tanto el sistema de restricciones no
puede abordarse fácilmente; se recurre entonces a la técnica
de planos de corte para resolver el IP.

Algunas razones importantes para aceptar ampliamente el

algoritmo (B & B) son las siguientes:
1. El método es conceptualmente simple y fácil de entender.
2. Es fácilmente adaptable a un amplio rango de situaciones
problemáticas.
3. Es fácilmente adaptable para su implantación
computacional.
A continuación se muestra un ejemplo del funcionamiento
del algoritmo.

Maximizar z = 5x₁ + x₂
Sujeto a :
- x₁ + 2x₂ ≤ 4
x₁ - x₂ ≤ 1
4x₁ + x₂ ≤ 12
x₁, x₂ ≥ 0 y entero

En un problema de maximización, se inicia con un valor

de la función objetivo igual a −ꝏ, porque cualquier
solución de la RL cumplirá con el objetivo de maximizar.
Se resuelve la relajación lineal, la cual corresponde la
nodo 0 del árbol de búsqueda y cuya solución es z =
14.6 y x₁ = 2.6 , x₂ = 1.6. Para este ejemplo,
arbitrariamente se escoge la variable de decisión para
ramificar, en este caso se eligió x₁, ver la siguiente figura.
La solución para estos nuevos subproblemas se
muestra a continuación:
Dado que el nuevo valor de la función objetivo es 13 y
13 > − ꝏ, entonces la solución al problema es z = 13 y
x₁ = 2 , x₂ = 3

Grafica del problema. Representación de las

restricciones agregadas al problema original.
RAMIFICACIÓN. Definición de la regla de Ramificación.
Se selecciona una variable binaria Pij o Qij sobre la cual
se ramificaran dos nuevos subproblemas, por un lado
tendremos uno con la restricción Pij = 0 y otro con Pij =
1, la razón por la cual se ramifica con estos valores, es
precisamente porque las variables binarias solo pueden
tomar el valor de 0 o bien de 1.
El criterio para escoger la variable binaria es optar por la
“menos entera”, es decir la variable más alejada de los
dos enteros que la rodean. Además se realiza una
Búsqueda en profundidad mientras que se realice la
ramificación y después se utiliza la Mejor Cota después
de podar el nodo.
ACOTACIÓN. Los nuevos subproblemas constituyen el árbol
de ramificación o árbol de búsqueda, y se procede
nuevamente a resolver la Relajación Lineal y a generar
nuevos cortes.

SONDEO. Cada nuevo subproblema se elimina

(sondea/poda) en cualquiera de los siguientes casos:
1. El valor de la función objetivo es igual o peor que una
solución entera conocida.
2. La solución del problema es infactible.
3. Satisface todas las restricciones de integralidad, el valor de
la función objetivo es mejor que la solución actual, entonces
esta solución se convierte en la actual y se aplica de nuevo el
caso primero a todos los problemas no sondeados con el
nuevo mejor valor de la función objetivo.