Algoritmos Básicos para PE Summary

Algoritmos Exactos para PLE

1 Algoritmos Básicos para PE

Introducción
Algoritmo de Branch and Bound
Algoritmo de Cutting Plane
Algoritmo de Branch and Cut
Algoritmo de Planos de Corte para TSP
Algoritmos Básicos para PE Summary

Outline

1 Algoritmos Básicos para PE

Introducción
Algoritmo de Branch and Bound
Algoritmo de Cutting Plane
Algoritmo de Branch and Cut
Algoritmo de Planos de Corte para TSP
Algoritmos Básicos para PE Summary

Introducción a P.E.
Motivación : P.E. no es lo mismo que P.L.

Hasta ahora hemos aprendido a resolver problema de Programación

Lineal, en que las variables era continuas en cierto intervalo.

Para este tipo de problemas el Método del Símplex resulta uno de

los métodos más eficientes de resolución.

Sin embargo, sabemos que existen muchos problemas en que las

variables no son continuas, sino que sólo pueden tomar valores
enteros.
Algoritmos Básicos para PE Summary

Introducción a P.E.
Motivación : P.E. no es lo mismo que P.L.

Hasta ahora hemos aprendido a resolver problema de Programación

Lineal, en que las variables era continuas en cierto intervalo.

Para este tipo de problemas el Método del Símplex resulta uno de

los métodos más eficientes de resolución.

Sin embargo, sabemos que existen muchos problemas en que las

variables no son continuas, sino que sólo pueden tomar valores
enteros.
Algoritmos Básicos para PE Summary

Introducción a P.E.
Motivación : P.E. no es lo mismo que P.L.

Hasta ahora hemos aprendido a resolver problema de Programación

Lineal, en que las variables era continuas en cierto intervalo.

Para este tipo de problemas el Método del Símplex resulta uno de

los métodos más eficientes de resolución.

Sin embargo, sabemos que existen muchos problemas en que las

variables no son continuas, sino que sólo pueden tomar valores
enteros.
Algoritmos Básicos para PE Summary

Introducción a P.E.
Motivación : P.E. no es lo mismo que P.L.

Por ejemplo, las variables binarias presentes en muchos problemas

hacen que el problema modelado sea un problema de P.E.

Por otro lado, si estamos tratando de encontrar un planificación de

la producción de aviones de una empresa aeronáutica, es claro que
el número aviones (una de las posible variables de decisión) sólo
admite valores enteros.

En conclusión, los problema de P.E. son tan o más importantes que

los problema de P.L., pero lamentablemente no puede ser resueltos
en forma directa a través de los métodos válidos para P.L. (como
por ejemplo Símplex).
Algoritmos Básicos para PE Summary

Introducción a P.E.
Motivación : P.E. no es lo mismo que P.L.

Por ejemplo, las variables binarias presentes en muchos problemas

hacen que el problema modelado sea un problema de P.E.

Por otro lado, si estamos tratando de encontrar un planificación de

la producción de aviones de una empresa aeronáutica, es claro que
el número aviones (una de las posible variables de decisión) sólo
admite valores enteros.

En conclusión, los problema de P.E. son tan o más importantes que

los problema de P.L., pero lamentablemente no puede ser resueltos
en forma directa a través de los métodos válidos para P.L. (como
por ejemplo Símplex).
Algoritmos Básicos para PE Summary

Introducción a P.E.
Motivación : P.E. no es lo mismo que P.L.

Por ejemplo, las variables binarias presentes en muchos problemas

hacen que el problema modelado sea un problema de P.E.

Por otro lado, si estamos tratando de encontrar un planificación de

la producción de aviones de una empresa aeronáutica, es claro que
el número aviones (una de las posible variables de decisión) sólo
admite valores enteros.

En conclusión, los problema de P.E. son tan o más importantes que

los problema de P.L., pero lamentablemente no puede ser resueltos
en forma directa a través de los métodos válidos para P.L. (como
por ejemplo Símplex).
Algoritmos Básicos para PE Summary

Introducción a P.E.
Motivación : P.E. no es lo mismo que P.L.

Problema de PL Problema de P.E.

n n
max z = ∑ cj x j max z = ∑ cj x j
j=1 j=1
s.t. s.t.
n n
∑ aij xj ≤ bi , i = 1, ..., m ∑ aij xj ≤ bi , i = 1, ..., m
j=1 j=1
xj ≥ 0, j = 1, ..., n xj enteros positivos, j = 1, ..., n
Algoritmos Básicos para PE Summary

Introducción a P.E.
Motivación : P.E. no es lo mismo que P.L.

Problema de PL Problema de P.E.

n n
max z = ∑ cj x j max z = ∑ cj x j
j=1 j=1
s.t. s.t.
n n
∑ aij xj ≤ bi , i = 1, ..., m ∑ aij xj ≤ bi , i = 1, ..., m
j=1 j=1
xj ≥ 0, j = 1, ..., n xj enteros positivos, j = 1, ..., n
Algoritmos Básicos para PE Summary

Introducción a P.E.
Motivación : P.E. no es lo mismo que P.L.

Problema de PL Problema de P.E.

Algoritmos Básicos para PE Summary

Introducción a P.E.
Motivación : P.E. no es lo mismo que P.L. (pero están relacionados)

Existe un problema de programación lineal asociado, denominado

relajación lineal (RL), que corresponde al problema lineal entero sin la
restricción de integralidad.

Dado que (RL) es menos restringido que (PE), se tiene que:

Si (PE) es un problema de maximización, el valor óptimo de (RL)
será mayor o igual que el valor óptimo de (PL).

Si (PE) es un problema de minimización, el valor óptimo de (RL)

será menor o igual que el valor óptimo de (PL).
Algoritmos Básicos para PE Summary

Introducción a P.E.
Motivación : P.E. no es lo mismo que P.L. (pero están relacionados)

Existe un problema de programación lineal asociado, denominado

relajación lineal (RL), que corresponde al problema lineal entero sin la
restricción de integralidad.

Dado que (RL) es menos restringido que (PE), se tiene que:

Si (PE) es un problema de maximización, el valor óptimo de (RL)
será mayor o igual que el valor óptimo de (PL).

Si (PE) es un problema de minimización, el valor óptimo de (RL)

será menor o igual que el valor óptimo de (PL).
Algoritmos Básicos para PE Summary

Introducción a P.E.
Motivación : P.E. no es lo mismo que P.L. (pero están relacionados)

Existe un problema de programación lineal asociado, denominado

relajación lineal (RL), que corresponde al problema lineal entero sin la
restricción de integralidad.

Dado que (RL) es menos restringido que (PE), se tiene que:

Si (PE) es un problema de maximización, el valor óptimo de (RL)
será mayor o igual que el valor óptimo de (PL).

Si (PE) es un problema de minimización, el valor óptimo de (RL)

será menor o igual que el valor óptimo de (PL).
Algoritmos Básicos para PE Summary

Introducción a P.E.
Motivación : P.E. no es lo mismo que P.L. (pero están relacionados)

Existe un problema de programación lineal asociado, denominado

relajación lineal (RL), que corresponde al problema lineal entero sin la
restricción de integralidad.

Dado que (RL) es menos restringido que (PE), se tiene que:

Si (PE) es un problema de maximización, el valor óptimo de (RL)
será mayor o igual que el valor óptimo de (PL).

Si (PE) es un problema de minimización, el valor óptimo de (RL)

será menor o igual que el valor óptimo de (PL).
Algoritmos Básicos para PE Summary

Introducción a P.E.
Motivación : P.E. no es lo mismo que P.L. (pero están relacionados)

Si (RL) es no factible, (PE) también será no factible.

Si (RL) tiene una solución óptima compuesta por variables

enteras, entonces esta solución será factible y óptima para
(PE).
Puesto que es relativamente simple resolver problemas de RL, es
útil utilizar estas relaciones en los métodos de resolución de PE. En
efecto, los métodos que estudiaremos se basan en estas relaciones.
Algoritmos Básicos para PE Summary

Introducción a P.E.
Motivación : P.E. no es lo mismo que P.L. (pero están relacionados)

Si (RL) es no factible, (PE) también será no factible.

Si (RL) tiene una solución óptima compuesta por variables

enteras, entonces esta solución será factible y óptima para
(PE).
Puesto que es relativamente simple resolver problemas de RL, es
útil utilizar estas relaciones en los métodos de resolución de PE. En
efecto, los métodos que estudiaremos se basan en estas relaciones.
Algoritmos Básicos para PE Summary

Introducción a P.E.
Motivación : P.E. no es lo mismo que P.L. (pero están relacionados)

Si (RL) es no factible, (PE) también será no factible.

Si (RL) tiene una solución óptima compuesta por variables

enteras, entonces esta solución será factible y óptima para
(PE).
Puesto que es relativamente simple resolver problemas de RL, es
útil utilizar estas relaciones en los métodos de resolución de PE. En
efecto, los métodos que estudiaremos se basan en estas relaciones.
Algoritmos Básicos para PE Summary

Introducción a P.E.
Cómo resolver un problema de P.E.?

En Programación Entera, no existen algoritmos con propósito

general y computacionalmente eficaces.

Incluso, la teoría sugiere que nunca podrán ser desarrollados

algoritmos computacionalmente eficaces que sirvan para un
propósito general.
Algoritmos Básicos para PE Summary

Introducción a P.E.
Cómo resolver un problema de P.E.?

En Programación Entera, no existen algoritmos con propósito

general y computacionalmente eficaces.

Incluso, la teoría sugiere que nunca podrán ser desarrollados

algoritmos computacionalmente eficaces que sirvan para un
propósito general.
Algoritmos Básicos para PE Summary

Introducción a P.E.
Cómo resolver un problema de P.E.?

Métodos con propósito general: resuelven cualquier modelo

de PE, pero son computacionalmente ineficaces (sólo resuelven
problemas relativamente pequeños). Dos ejemplos importantes
son Branch and Bound y Cutting Planes.

Métodos con propósito específico: son desarrollados para

resolver un tipo particular de problemas de PE, pero son
computacionalmente más efectivos.
Algoritmos Básicos para PE Summary

Introducción a P.E.
Cómo resolver un problema de P.E.?

Métodos con propósito general: resuelven cualquier modelo

de PE, pero son computacionalmente ineficaces (sólo resuelven
problemas relativamente pequeños). Dos ejemplos importantes
son Branch and Bound y Cutting Planes.

Métodos con propósito específico: son desarrollados para

resolver un tipo particular de problemas de PE, pero son
computacionalmente más efectivos.
Algoritmos Básicos para PE Summary

Introducción a P.E.
Cómo resolver un problema de P.E.?

Métodos exactos: son algoritmos que, a través de

comprobación matemática, se garantiza que obtienen una
solución óptima para el problema.

Métodos heurísticos: es un algoritmo que permite obtener

una solución factible para un problema de programación
matemática, esperando que su valor en la función objetivo esté
cercano al óptimo.
Algoritmos Básicos para PE Summary

Introducción a P.E.
Cómo resolver un problema de P.E.?

Métodos exactos: son algoritmos que, a través de

comprobación matemática, se garantiza que obtienen una
solución óptima para el problema.

Métodos heurísticos: es un algoritmo que permite obtener

una solución factible para un problema de programación
matemática, esperando que su valor en la función objetivo esté
cercano al óptimo.
Algoritmos Básicos para PE Summary

Outline

1 Algoritmos Básicos para PE

Introducción
Algoritmo de Branch and Bound
Algoritmo de Cutting Plane
Algoritmo de Branch and Cut
Algoritmo de Planos de Corte para TSP
Algoritmos Básicos para PE Summary

Algoritmo de Branch and Bound

Conceptos Básicos

Se basa en la idea de desarrollar una “enumeración

inteligente” de los puntos candidatos a solución óptima
entera de un problema.

Es una instancia de “Divide y Conquista”.

Algoritmos Básicos para PE Summary

Algoritmo de Branch and Bound

Conceptos Básicos

Se basa en la idea de desarrollar una “enumeración

inteligente” de los puntos candidatos a solución óptima
entera de un problema.

Es una instancia de “Divide y Conquista”.

Algoritmos Básicos para PE Summary

Algoritmo de Branch and Bound

Conceptos Básicos: quién es el Sr. Branch y quién es el Sr. Bound?

El término Branch (o ramificación) se refiere al hecho de que

este método realiza particiones en el espacio de soluciones
(generamos “ramas”).

El término Bound (o acotamiento) resalta que la prueba de

optimalidad de la solución va eliminando las particiones
utilizando los resultados calculados a lo largo de la
enumeración (podamos “ramas”).
Algoritmos Básicos para PE Summary

Algoritmo de Branch and Bound

Conceptos Básicos: quién es el Sr. Branch y quién es el Sr. Bound?

El término Branch (o ramificación) se refiere al hecho de que

este método realiza particiones en el espacio de soluciones
(generamos “ramas”).

El término Bound (o acotamiento) resalta que la prueba de

optimalidad de la solución va eliminando las particiones
utilizando los resultados calculados a lo largo de la
enumeración (podamos “ramas”).
Algoritmos Básicos para PE Summary

Algoritmo de Branch and Bound

Conceptos Básicos: cómo generar ramas?

Consideremos un problema de PE, tal que el valor óptimo de unas de las

variables del problema relajado es xj∗ (no entera).

Generamos dos ramas:

Una añadiendo la restricción xj ≤ xj∗ .

Y otra añadiendo la restricción xj ≥ xj∗ + 1.

Por ejemplo, si xj∗ = 1.27, entonces se generan dos ramas:

Una añadiendo la restricción xj ≤ 1.

Y otra añadiendo la restricción xj ≥ 2.

Algoritmos Básicos para PE Summary

Algoritmo de Branch and Bound

Conceptos Básicos: cómo generar ramas?

Consideremos un problema de PE, tal que el valor óptimo de unas de las

variables del problema relajado es xj∗ (no entera).

Generamos dos ramas:

Una añadiendo la restricción xj ≤ xj∗ .

Y otra añadiendo la restricción xj ≥ xj∗ + 1.

Por ejemplo, si xj∗ = 1.27, entonces se generan dos ramas:

Una añadiendo la restricción xj ≤ 1.

Y otra añadiendo la restricción xj ≥ 2.

Algoritmos Básicos para PE Summary

Algoritmo de Branch and Bound

Conceptos Básicos: cómo generar ramas?

Consideremos un problema de PE, tal que el valor óptimo de unas de las

variables del problema relajado es xj∗ (no entera).

Generamos dos ramas:

Una añadiendo la restricción xj ≤ xj∗ .

Y otra añadiendo la restricción xj ≥ xj∗ + 1.

Por ejemplo, si xj∗ = 1.27, entonces se generan dos ramas:

Una añadiendo la restricción xj ≤ 1.

Y otra añadiendo la restricción xj ≥ 2.

Algoritmos Básicos para PE Summary

Algoritmo de Branch and Bound

Conceptos Básicos: cómo generar ramas?

Consideremos un problema de PE, tal que el valor óptimo de unas de las

variables del problema relajado es xj∗ (no entera).

Generamos dos ramas:

Una añadiendo la restricción xj ≤ xj∗ .

Y otra añadiendo la restricción xj ≥ xj∗ + 1.

Por ejemplo, si xj∗ = 1.27, entonces se generan dos ramas:

Una añadiendo la restricción xj ≤ 1.

Y otra añadiendo la restricción xj ≥ 2.

Algoritmos Básicos para PE Summary

Algoritmo de Branch and Bound

Conceptos Básicos: cómo generar ramas?

Consideremos un problema de PE, tal que el valor óptimo de unas de las

variables del problema relajado es xj∗ (no entera).

Generamos dos ramas:

Una añadiendo la restricción xj ≤ xj∗ .

Y otra añadiendo la restricción xj ≥ xj∗ + 1.

Por ejemplo, si xj∗ = 1.27, entonces se generan dos ramas:

Una añadiendo la restricción xj ≤ 1.

Y otra añadiendo la restricción xj ≥ 2.

Algoritmos Básicos para PE Summary

Algoritmo de Branch and Bound

Conceptos Básicos: cómo generar ramas?

Consideremos un problema de PE, tal que el valor óptimo de unas de las

variables del problema relajado es xj∗ (no entera).

Generamos dos ramas:

Una añadiendo la restricción xj ≤ xj∗ .

Y otra añadiendo la restricción xj ≥ xj∗ + 1.

Por ejemplo, si xj∗ = 1.27, entonces se generan dos ramas:

Una añadiendo la restricción xj ≤ 1.

Y otra añadiendo la restricción xj ≥ 2.

Algoritmos Básicos para PE Summary

Algoritmo de Branch and Bound

Conceptos Básicos: cómo generar ramas?

Consideremos un problema de PE, tal que el valor óptimo de unas de las

variables del problema relajado es xj∗ (no entera).

Generamos dos ramas:

Una añadiendo la restricción xj ≤ xj∗ .

Y otra añadiendo la restricción xj ≥ xj∗ + 1.

Por ejemplo, si xj∗ = 1.27, entonces se generan dos ramas:

Una añadiendo la restricción xj ≤ 1.

Y otra añadiendo la restricción xj ≥ 2.

Algoritmos Básicos para PE Summary

Algoritmo de Branch and Bound

Conceptos Básicos: cómo generar ramas?

Esquemáticamente:
Algoritmos Básicos para PE Summary

Algoritmo de Branch and Bound

Conceptos Básicos: cómo generar ramas?

En cada subproblema se definen nuevas ramas y asi

sucesivamente.

Cuando un subproblema entrega una solución entera, esa

solución se llama solución de apoyo y entrega una “cota
inferior” o “límite inferior” al problema.

Cuando un subproblema entrega una solución contínua, esa

solución entrega una “cota superior” o “límite superior” al
problema.
Algoritmos Básicos para PE Summary

Algoritmo de Branch and Bound

Conceptos Básicos: cómo generar ramas?

En cada subproblema se definen nuevas ramas y asi

sucesivamente.

Cuando un subproblema entrega una solución entera, esa

solución se llama solución de apoyo y entrega una “cota
inferior” o “límite inferior” al problema.

Cuando un subproblema entrega una solución contínua, esa

solución entrega una “cota superior” o “límite superior” al
problema.
Algoritmos Básicos para PE Summary

Algoritmo de Branch and Bound

Conceptos Básicos: cómo generar ramas?

En cada subproblema se definen nuevas ramas y asi

sucesivamente.

Cuando un subproblema entrega una solución entera, esa

solución se llama solución de apoyo y entrega una “cota
inferior” o “límite inferior” al problema.

Cuando un subproblema entrega una solución contínua, esa

solución entrega una “cota superior” o “límite superior” al
problema.
Algoritmos Básicos para PE Summary

Algoritmo de Branch and Bound

Ejemplo (1) : Definición de RLPE = P0

Consideremos el siguiente problema de PE:

max z = {5x1 + 8x2 : x1 + x2 ≤ 6, 5x1 + 9x2 ≤ 45, x1 , x2 enteros}

Entonces el problema de RL de PE (P0 ) es:

P0 : max z = {5x1 + 8x2 : x1 + x2 ≤ 6, 5x1 + 9x2 ≤ 45, x1 , x2 ≥ 0}

Algoritmos Básicos para PE Summary

Algoritmo de Branch and Bound

Ejemplo (1) : Definición de RLPE = P0

Consideremos el siguiente problema de PE:

max z = {5x1 + 8x2 : x1 + x2 ≤ 6, 5x1 + 9x2 ≤ 45, x1 , x2 enteros}

Entonces el problema de RL de PE (P0 ) es:

P0 : max z = {5x1 + 8x2 : x1 + x2 ≤ 6, 5x1 + 9x2 ≤ 45, x1 , x2 ≥ 0}

Algoritmos Básicos para PE Summary

Algoritmo de Branch and Bound

Ejemplo (1) : Definición de RLPE = P0

Consideremos el siguiente problema de PE:

max z = {5x1 + 8x2 : x1 + x2 ≤ 6, 5x1 + 9x2 ≤ 45, x1 , x2 enteros}

Entonces el problema de RL de PE (P0 ) es:

P0 : max z = {5x1 + 8x2 : x1 + x2 ≤ 6, 5x1 + 9x2 ≤ 45, x1 , x2 ≥ 0}

Algoritmos Básicos para PE Summary

Algoritmo de Branch and Bound

Ejemplo (1) : Definición de RLPE = P0

Consideremos el siguiente problema de PE:

max z = {5x1 + 8x2 : x1 + x2 ≤ 6, 5x1 + 9x2 ≤ 45, x1 , x2 enteros}

Entonces el problema de RL de PE (P0 ) es:

P0 : max z = {5x1 + 8x2 : x1 + x2 ≤ 6, 5x1 + 9x2 ≤ 45, x1 , x2 ≥ 0}

Algoritmos Básicos para PE Summary

Algoritmo de Branch and Bound

Ejemplo (1) : Definición de las primeras ramas P1 y P2

Al resolver P0 tenemos que z0∗ = 41 14 , x1 = 9

4 = 2.25, x2 = 15
4 = 3.75.

Para generar los nuevos subproblemas (P1 y P2 ) tomaremos la variable

x2 , una rama incluye la restricción x2 ≤ k3.75k ≤ 3 y la otra rama incluye
la restricción x2 ≥ k3.75k + 1 ≥ 4.
Algoritmos Básicos para PE Summary

Algoritmo de Branch and Bound

Ejemplo (1) : Definición de las primeras ramas P1 y P2

Al resolver P0 tenemos que z0∗ = 41 14 , x1 = 9

4 = 2.25, x2 = 15
4 = 3.75.

Para generar los nuevos subproblemas (P1 y P2 ) tomaremos la variable

x2 , una rama incluye la restricción x2 ≤ k3.75k ≤ 3 y la otra rama incluye
la restricción x2 ≥ k3.75k + 1 ≥ 4.
Algoritmos Básicos para PE Summary

Algoritmo de Branch and Bound

Ejemplo (1) : Definición de las primeras ramas P1 y P2

Esquemáticamente:
Algoritmos Básicos para PE Summary

Algoritmo de Branch and Bound

Ejemplo (1) : Resolución de las primeras ramas P1 y P2

El problema P1 se define por:

P1 : max z = {5x1 + 8x2 : x1 + x2 ≤ 6, 5x1 + 9x2 ≤ 45, x2 ≤ 3, x1 , x2 ≥ 0}

y su solución es z1∗ = 39, x1 = 3, x2 = 3. Debido a que esta es

una solución entera, pasa a ser una solución de apoyo.

El problema P2 se define por:

P2 : max z = {5x1 + 8x2 : x1 + x2 ≤ 6, 5x1 + 9x2 ≤ 45, x2 ≥ 4, x1 , x2 ≥ 0}

y su solución esz2∗ = 41, x1 = 59 , x2 = 4. Debido a que esta

solución no es entera, generamos nuevas ramas.

∗ ∈ [39, 41].
Sabemos que el valor óptimo cumple con zPE
Algoritmos Básicos para PE Summary

Algoritmo de Branch and Bound

Ejemplo (1) : Resolución de las primeras ramas P1 y P2

El problema P1 se define por:

P1 : max z = {5x1 + 8x2 : x1 + x2 ≤ 6, 5x1 + 9x2 ≤ 45, x2 ≤ 3, x1 , x2 ≥ 0}

y su solución es z1∗ = 39, x1 = 3, x2 = 3. Debido a que esta es

una solución entera, pasa a ser una solución de apoyo.

El problema P2 se define por:

P2 : max z = {5x1 + 8x2 : x1 + x2 ≤ 6, 5x1 + 9x2 ≤ 45, x2 ≥ 4, x1 , x2 ≥ 0}

y su solución esz2∗ = 41, x1 = 59 , x2 = 4. Debido a que esta

solución no es entera, generamos nuevas ramas.

∗ ∈ [39, 41].
Sabemos que el valor óptimo cumple con zPE
Algoritmos Básicos para PE Summary

Algoritmo de Branch and Bound

Ejemplo (1) : Resolución de las primeras ramas P1 y P2

El problema P1 se define por:

P1 : max z = {5x1 + 8x2 : x1 + x2 ≤ 6, 5x1 + 9x2 ≤ 45, x2 ≤ 3, x1 , x2 ≥ 0}

y su solución es z1∗ = 39, x1 = 3, x2 = 3. Debido a que esta es

una solución entera, pasa a ser una solución de apoyo.

El problema P2 se define por:

P2 : max z = {5x1 + 8x2 : x1 + x2 ≤ 6, 5x1 + 9x2 ≤ 45, x2 ≥ 4, x1 , x2 ≥ 0}

y su solución esz2∗ = 41, x1 = 59 , x2 = 4. Debido a que esta

solución no es entera, generamos nuevas ramas.

∗ ∈ [39, 41].
Sabemos que el valor óptimo cumple con zPE
Algoritmos Básicos para PE Summary

Algoritmo de Branch and Bound

Ejemplo (1) : Resolución de las primeras ramas P1 y P2

Esquemáticamente:
Algoritmos Básicos para PE Summary

Algoritmo de Branch and Bound

Ejemplo (1) : Definición de las ramas P3 y P4

Al resolver P2 tenemos que z2∗ = 41, x1 = 9

5 = 1.80, x2 = 4.

Para generar los nuevos subproblemas (P3 y P4 ) tomaremos la variable

x1 , una rama incluye la restricción x1 ≤ k1.80k ≤ 1 y la otra rama incluye
la restricción x1 ≥ k1.80k + 1 ≥ 2.
Algoritmos Básicos para PE Summary

Algoritmo de Branch and Bound

Ejemplo (1) : Definición de las ramas P3 y P4

Al resolver P2 tenemos que z2∗ = 41, x1 = 9

5 = 1.80, x2 = 4.

Para generar los nuevos subproblemas (P3 y P4 ) tomaremos la variable

x1 , una rama incluye la restricción x1 ≤ k1.80k ≤ 1 y la otra rama incluye
la restricción x1 ≥ k1.80k + 1 ≥ 2.
Algoritmos Básicos para PE Summary

Algoritmo de Branch and Bound

Ejemplo (1) : Definición de las ramas P3 y P4

Esquemáticamente:
Algoritmos Básicos para PE Summary

Algoritmo de Branch and Bound

Ejemplo (1) : Resolución de las ramas P3 y P4

El problema P3 se define por:

P3 : max z = {5x1 + 8x2 : x1 + x2 ≤ 6, 5x1 + 9x2 ≤ 45, x2 ≥ 4, x1 ≤ 1, x1 , x2 ≥ 0}

y su solución esz3∗ = 40 95 , x1 = 1, x2 = 40
9 ≈ 4.44. Debido a que
esta solución no es entera, generamos nuevas ramas.

El problema P4 se define por:

P4 : max z = {5x1 + 8x2 : x1 + x2 ≤ 6, 5x1 + 9x2 ≤ 45, x2 ≥ 4, x1 ≥ 2, x1 , x2 ≥ 0}

y no tiene solución factible.

Algoritmos Básicos para PE Summary

Algoritmo de Branch and Bound

Ejemplo (1) : Resolución de las ramas P3 y P4

El problema P3 se define por:

P3 : max z = {5x1 + 8x2 : x1 + x2 ≤ 6, 5x1 + 9x2 ≤ 45, x2 ≥ 4, x1 ≤ 1, x1 , x2 ≥ 0}

y su solución esz3∗ = 40 95 , x1 = 1, x2 = 40
9 ≈ 4.44. Debido a que
esta solución no es entera, generamos nuevas ramas.

El problema P4 se define por:

P4 : max z = {5x1 + 8x2 : x1 + x2 ≤ 6, 5x1 + 9x2 ≤ 45, x2 ≥ 4, x1 ≥ 2, x1 , x2 ≥ 0}

y no tiene solución factible.

Algoritmos Básicos para PE Summary

Algoritmo de Branch and Bound

Ejemplo (1) : Resolución de las ramas P3 y P4

Esquemáticamente:
Algoritmos Básicos para PE Summary

Algoritmo de Branch and Bound

Ejemplo (1) : Definición de las ramas P5 y P6

Al resolver P3 tenemos que z2∗ = 40 59 , x1 = 1, x2 = 40

9 .

Para generar los nuevos subproblemas (P5 y P6 ) tomaremos la variable

x2 , una rama incluye la restricción x2 ≤ 40
9 ≤ 4 y la otra rama incluye
la restricción x2 ≥ 40
9 + 1 ≥ 5.
Algoritmos Básicos para PE Summary

Algoritmo de Branch and Bound

Ejemplo (1) : Definición de las ramas P5 y P6

Al resolver P3 tenemos que z2∗ = 40 59 , x1 = 1, x2 = 40

9 .

Para generar los nuevos subproblemas (P5 y P6 ) tomaremos la variable

x2 , una rama incluye la restricción x2 ≤ 40
9 ≤ 4 y la otra rama incluye
la restricción x2 ≥ 40
9 + 1 ≥ 5.
Algoritmos Básicos para PE Summary

Algoritmo de Branch and Bound

Ejemplo (1) : Definición de las ramas P5 y P6

Esquemáticamente:
Algoritmos Básicos para PE Summary

Algoritmo de Branch and Bound

Ejemplo (1) : Resolución de las ramas P5 y P6

El problema P5 se define por:

P5 : max z = {5x1 + 8x2 : x1 + x2 ≤ 6, 5x1 + 9x2 ≤ 45, x2 ≥ 4, x1 ≤ 1, x2 ≤ 4, x1 , x2 ≥ 0}

y su solución es z5∗ = 37, x1 = 1, x2 = 4. Esta es una solución

entera pero no es mejor que z1∗ = 39, por lo que no pasa a ser
una solución de apoyo.
El problema P6 se define por:
P6 : max z = {5x1 + 8x2 : x1 + x2 ≤ 6, 5x1 + 9x2 ≤ 45, x2 ≥ 4, x1 ≤ 1, x2 ≤ 4, x2 ≥ 5, x1 , x2 ≥ 0}

y su solución es z6∗ = 40, x1 = 0, x2 = 5. Debido a que esta es

una solución entera y mejor que z1∗ = 39, pasa a ser la nueva
solución de apoyo.
Algoritmos Básicos para PE Summary

Algoritmo de Branch and Bound

Ejemplo (1) : Resolución de las ramas P5 y P6

Esquemáticamente:
Algoritmos Básicos para PE Summary

Algoritmo de Branch and Bound

Ejemplo (1) : Definición de nuevas ramas

Debido a que hemos obtenido una solución de apoyo y no

podemos seguir generando ramas, entonces esta solución de
apoyo es la solución óptima.
Es decir, la solución óptima al problema original de P.E. es
z ∗ = 40, x1∗ = 0 y x2∗ = 5.
Algoritmos Básicos para PE Summary

Algoritmo de Branch and Bound

Ejemplo (1) : Solución Final
Algoritmos Básicos para PE Summary

Algoritmo de Branch and Bound

Criterios para cerrar un nodo

Si la solución del sub-problema tiene variables enteras.

Si el problema no tiene solución (problema no factible).

Si el valor óptimo es menor (mayor) que el z∗apoyo encontrado

hasta esa iteración en un problema de maximización
(minimización).
Algoritmos Básicos para PE Summary

Algoritmo de Branch and Bound

Criterios para cerrar un nodo

Si la solución del sub-problema tiene variables enteras.

Si el problema no tiene solución (problema no factible).

Si el valor óptimo es menor (mayor) que el z∗apoyo encontrado

hasta esa iteración en un problema de maximización
(minimización).
Algoritmos Básicos para PE Summary

Algoritmo de Branch and Bound

Criterios para cerrar un nodo

Si la solución del sub-problema tiene variables enteras.

Si el problema no tiene solución (problema no factible).

Si el valor óptimo es menor (mayor) que el z∗apoyo encontrado

hasta esa iteración en un problema de maximización
(minimización).
Algoritmos Básicos para PE Summary

Algoritmo de Branch and Bound

Ejemplo (2) : Definición del problema de PE Binaria RLPE = P0

Consideremos el siguiente problema de PE (Binaria):

max z = 9x1 + 5x2 + 6x3 + 4x4

subject to
6x1 + 3x2 + 5x3 + 2x4 ≤ 10
x3 + x4 ≤ 1
−x1 + x3 ≤ 0
−x2 + x4 ≤ 0
xi ∈ {0, 1} ∀i
Algoritmos Básicos para PE Summary

Algoritmo de Branch and Bound

Ejemplo (2) : Definición del problema de PE Binaria RLPE = P0

Consideremos el siguiente problema de PE (Binaria):

max z = 9x1 + 5x2 + 6x3 + 4x4

subject to
6x1 + 3x2 + 5x3 + 2x4 ≤ 10
x3 + x4 ≤ 1
−x1 + x3 ≤ 0
−x2 + x4 ≤ 0
xi ∈ {0, 1} ∀i
Algoritmos Básicos para PE Summary

Algoritmo de Branch and Bound

Ejemplo (2) : Definición del problema de RLPE = P0

La relajación lineal del problema anterior está dado por:

max z = 9x1 + 5x2 + 6x3 + 4x4

subject to
6x1 + 3x2 + 5x3 + 2x4 ≤ 10
x3 + x4 ≤ 1
−x1 + x3 ≤ 0
−x2 + x4 ≤ 0
xi ∈ [0, 1] ∀i
Algoritmos Básicos para PE Summary

Algoritmo de Branch and Bound

Ejemplo (2) : Definición del problema de RLPE = P0

La relajación lineal del problema anterior está dado por:

max z = 9x1 + 5x2 + 6x3 + 4x4

subject to
6x1 + 3x2 + 5x3 + 2x4 ≤ 10
x3 + x4 ≤ 1
−x1 + x3 ≤ 0
−x2 + x4 ≤ 0
xi ∈ [0, 1] ∀i
Algoritmos Básicos para PE Summary

Algoritmo de Branch and Bound

Ejemplo (2) : Definición de los problemas P1 y P2

Al resolver P0 tenemos que z0∗ = 16.5, x1 = 56 , x2 = 1, x3 = 0 y

x4 = 1.

Para generar las ramas P1 y P2 tomemos la variable x1 ; una

rama incluirá la restricción x1 ≤ 0 y la otra x1 ≥ 1.

Sin embargo, puesto que 0 ≤ x1 ≤ 1 entonces lo que en

realidad se define que en P1 , x1 = 0; y en P2 , x1 = 1.
Algoritmos Básicos para PE Summary

Algoritmo de Branch and Bound

Ejemplo (2) : Definición de los problemas P1 y P2

Al resolver P0 tenemos que z0∗ = 16.5, x1 = 56 , x2 = 1, x3 = 0 y

x4 = 1.

Para generar las ramas P1 y P2 tomemos la variable x1 ; una

rama incluirá la restricción x1 ≤ 0 y la otra x1 ≥ 1.

Sin embargo, puesto que 0 ≤ x1 ≤ 1 entonces lo que en

realidad se define que en P1 , x1 = 0; y en P2 , x1 = 1.
Algoritmos Básicos para PE Summary

Algoritmo de Branch and Bound

Ejemplo (2) : Definición de los problemas P1 y P2

Al resolver P0 tenemos que z0∗ = 16.5, x1 = 56 , x2 = 1, x3 = 0 y

x4 = 1.

Para generar las ramas P1 y P2 tomemos la variable x1 ; una

rama incluirá la restricción x1 ≤ 0 y la otra x1 ≥ 1.

Sin embargo, puesto que 0 ≤ x1 ≤ 1 entonces lo que en

realidad se define que en P1 , x1 = 0; y en P2 , x1 = 1.
Algoritmos Básicos para PE Summary

Algoritmo de Branch and Bound

Ejemplo (2) : Definición de los problemas P1 y P2

Esquemáticamente:
Algoritmos Básicos para PE Summary

Algoritmo de Branch and Bound

Ejemplo (2) : Resolución de las primeras ramas P1 y P2

El problema P1 se define por:

P1 : {P0 : x1 = 0}

y su solución es z1∗ = 9, x1 = 0, x2 = 1, x3 = 0 y x4 = 1. Debido a

que esta es una solución entera, pasa a ser una solución de
apoyo.

El problema P2 se define por:

P2 : {P0 : x1 = 1}

y su solución esz2∗ = 16.2, x1 = 0, x2 = 45 , x3 = 0 y x4 = 45 . Debido

a que esta solución no es entera, generamos nuevas ramas.

∗ ∈ [9, 16.2].
Sabemos que el valor óptimo cumple con zPE
Algoritmos Básicos para PE Summary

Algoritmo de Branch and Bound

Ejemplo (2) : Resolución de las primeras ramas P1 y P2

El problema P1 se define por:

P1 : {P0 : x1 = 0}

y su solución es z1∗ = 9, x1 = 0, x2 = 1, x3 = 0 y x4 = 1. Debido a

que esta es una solución entera, pasa a ser una solución de
apoyo.

El problema P2 se define por:

P2 : {P0 : x1 = 1}

y su solución esz2∗ = 16.2, x1 = 0, x2 = 45 , x3 = 0 y x4 = 45 . Debido

a que esta solución no es entera, generamos nuevas ramas.

∗ ∈ [9, 16.2].
Sabemos que el valor óptimo cumple con zPE
Algoritmos Básicos para PE Summary

Algoritmo de Branch and Bound

Ejemplo (2) : Resolución de las primeras ramas P1 y P2

El problema P1 se define por:

P1 : {P0 : x1 = 0}

y su solución es z1∗ = 9, x1 = 0, x2 = 1, x3 = 0 y x4 = 1. Debido a

que esta es una solución entera, pasa a ser una solución de
apoyo.

El problema P2 se define por:

P2 : {P0 : x1 = 1}

y su solución esz2∗ = 16.2, x1 = 0, x2 = 45 , x3 = 0 y x4 = 45 . Debido

a que esta solución no es entera, generamos nuevas ramas.

∗ ∈ [9, 16.2].
Sabemos que el valor óptimo cumple con zPE
Algoritmos Básicos para PE Summary

Algoritmo de Branch and Bound

Ejemplo (2) : Resolución de las primeras ramas P1 y P2

Esquemáticamente:
Algoritmos Básicos para PE Summary

Algoritmo de Branch and Bound

Ejemplo (2) : Definición de las ramas P3 y P4

Al resolver P2 tenemos que z2∗ = 16.2, z2∗ = 16.2, x1 = 0, x2 = 4

5 = 0.8,
x3 = 0 y x4 = 54 = 0.8.

Para generar los nuevos subproblemas (P3 y P4 ) tomaremos la variable

x2 , una rama incluye la restricción x2 ≤ k0.8k ≤ 0 y la otra rama incluye
la restricción x2 ≥ k0.8k + 1 ≥ 1.

Sin embargo, puesto que 0 ≤ x2 ≤ 1 entonces lo que en realidad se define

que en P3 , x2 = 0; y en P4 , x2 = 1.
Algoritmos Básicos para PE Summary

Algoritmo de Branch and Bound

Ejemplo (2) : Definición de las ramas P3 y P4

Al resolver P2 tenemos que z2∗ = 16.2, z2∗ = 16.2, x1 = 0, x2 = 4

5 = 0.8,
x3 = 0 y x4 = 54 = 0.8.

Para generar los nuevos subproblemas (P3 y P4 ) tomaremos la variable

x2 , una rama incluye la restricción x2 ≤ k0.8k ≤ 0 y la otra rama incluye
la restricción x2 ≥ k0.8k + 1 ≥ 1.

Sin embargo, puesto que 0 ≤ x2 ≤ 1 entonces lo que en realidad se define

que en P3 , x2 = 0; y en P4 , x2 = 1.
Algoritmos Básicos para PE Summary

Algoritmo de Branch and Bound

Ejemplo (2) : Definición de las ramas P3 y P4

Al resolver P2 tenemos que z2∗ = 16.2, z2∗ = 16.2, x1 = 0, x2 = 4

5 = 0.8,
x3 = 0 y x4 = 54 = 0.8.

Para generar los nuevos subproblemas (P3 y P4 ) tomaremos la variable

x2 , una rama incluye la restricción x2 ≤ k0.8k ≤ 0 y la otra rama incluye
la restricción x2 ≥ k0.8k + 1 ≥ 1.

Sin embargo, puesto que 0 ≤ x2 ≤ 1 entonces lo que en realidad se define

que en P3 , x2 = 0; y en P4 , x2 = 1.
Algoritmos Básicos para PE Summary

Algoritmo de Branch and Bound

Ejemplo (2) : Definición de las ramas P3 y P4

Esquemáticamente:
Algoritmos Básicos para PE Summary

Algoritmo de Branch and Bound

Ejemplo (2) : Resolución de las ramas P3 y P4

El problema P3 se define por:

P3 : {P2 : x2 = 0}

y su solución esz3∗ = 13 54
= 13.8, x1 = 1, x2 = 0, x3 = 45 y x4 = 0. Debido
a que esta es una solución no entera, podemos generar ramas.

El problema P4 se define por:

P4 : {P2 : x2 = 1}

y su solución es z2∗ = 16, x1 = 1, x2 = 1, x3 = 0 y x4 = 0.5. Debido a que

esta solución no es entera pero , generamos nuevas ramas. Como z4 es
mayor que z3 entonces ramificaremos desde este problema.

∗ ∈ [9, 16].
Sabemos que el valor óptimo cumple con zPE
Algoritmos Básicos para PE Summary

Algoritmo de Branch and Bound

Ejemplo (2) : Resolución de las ramas P3 y P4

El problema P3 se define por:

P3 : {P2 : x2 = 0}

y su solución esz3∗ = 13 54
= 13.8, x1 = 1, x2 = 0, x3 = 45 y x4 = 0. Debido
a que esta es una solución no entera, podemos generar ramas.

El problema P4 se define por:

P4 : {P2 : x2 = 1}

y su solución es z2∗ = 16, x1 = 1, x2 = 1, x3 = 0 y x4 = 0.5. Debido a que

esta solución no es entera pero , generamos nuevas ramas. Como z4 es
mayor que z3 entonces ramificaremos desde este problema.

∗ ∈ [9, 16].
Sabemos que el valor óptimo cumple con zPE
Algoritmos Básicos para PE Summary

Algoritmo de Branch and Bound

Ejemplo (2) : Resolución de las ramas P3 y P4

El problema P3 se define por:

P3 : {P2 : x2 = 0}

y su solución esz3∗ = 13 54
= 13.8, x1 = 1, x2 = 0, x3 = 45 y x4 = 0. Debido
a que esta es una solución no entera, podemos generar ramas.

El problema P4 se define por:

P4 : {P2 : x2 = 1}

y su solución es z2∗ = 16, x1 = 1, x2 = 1, x3 = 0 y x4 = 0.5. Debido a que

esta solución no es entera pero , generamos nuevas ramas. Como z4 es
mayor que z3 entonces ramificaremos desde este problema.

∗ ∈ [9, 16].
Sabemos que el valor óptimo cumple con zPE
Algoritmos Básicos para PE Summary

Algoritmo de Branch and Bound

Ejemplo (2) : Resolución de las ramas P3 y P4

Esquemáticamente:
Algoritmos Básicos para PE Summary

Algoritmo de Branch and Bound

Ejemplo (2) : Definición de las ramas P5 y P6

Al resolver P4 tenemos que z4∗ = 16, x1 = 1, x2 = 1, x3 = 0 y x4 = 12 .

Para generar los nuevos subproblemas (P5 y P6 ) tomaremos la variable

x4 , una rama incluye la restricción x2 ≤ k0.5k ≤ 0 y la otra rama incluye
la restricción x2 ≥ k0.5k + 1 ≥ 1.

Sin embargo, puesto que 0 ≤ x4 ≤ 1 entonces lo que en realidad se define

que en P5 , x4 = 0; y en P6 , x4 = 1.
Algoritmos Básicos para PE Summary

Algoritmo de Branch and Bound

Ejemplo (2) : Definición de las ramas P5 y P6

Al resolver P4 tenemos que z4∗ = 16, x1 = 1, x2 = 1, x3 = 0 y x4 = 12 .

Para generar los nuevos subproblemas (P5 y P6 ) tomaremos la variable

x4 , una rama incluye la restricción x2 ≤ k0.5k ≤ 0 y la otra rama incluye
la restricción x2 ≥ k0.5k + 1 ≥ 1.

Sin embargo, puesto que 0 ≤ x4 ≤ 1 entonces lo que en realidad se define

que en P5 , x4 = 0; y en P6 , x4 = 1.
Algoritmos Básicos para PE Summary

Algoritmo de Branch and Bound

Ejemplo (2) : Definición de las ramas P5 y P6

Al resolver P4 tenemos que z4∗ = 16, x1 = 1, x2 = 1, x3 = 0 y x4 = 12 .

Para generar los nuevos subproblemas (P5 y P6 ) tomaremos la variable

x4 , una rama incluye la restricción x2 ≤ k0.5k ≤ 0 y la otra rama incluye
la restricción x2 ≥ k0.5k + 1 ≥ 1.

Sin embargo, puesto que 0 ≤ x4 ≤ 1 entonces lo que en realidad se define

que en P5 , x4 = 0; y en P6 , x4 = 1.
Algoritmos Básicos para PE Summary

Algoritmo de Branch and Bound

Ejemplo (2) : Definición de las ramas P5 y P6

Esquemáticamente
Algoritmos Básicos para PE Summary

Algoritmo de Branch and Bound

Ejemplo (2) : Resolución de las ramas P5 y P6

El problema P5 se define por:

P5 : {P4 : x4 = 0}

y su solución es z5∗ = 15 51 = 13.8, x1 = 1, x2 = 0, x3 = 15 y x4 = 0. Debido

a que esta es una solución no entera, podemos generar ramas.

El problema P6 se define por:

P6 : {P4 : x4 = 1}

y es No Factible, por lo que se cierra ese nodo de búsqueda.

∗ ∈ 9, 15 1 .
 
Sabemos que el valor óptimo cumple con zPE 5
Algoritmos Básicos para PE Summary

Algoritmo de Branch and Bound

Ejemplo (2) : Resolución de las ramas P5 y P6

El problema P5 se define por:

P5 : {P4 : x4 = 0}

y su solución es z5∗ = 15 51 = 13.8, x1 = 1, x2 = 0, x3 = 15 y x4 = 0. Debido

a que esta es una solución no entera, podemos generar ramas.

El problema P6 se define por:

P6 : {P4 : x4 = 1}

y es No Factible, por lo que se cierra ese nodo de búsqueda.

∗ ∈ 9, 15 1 .
 
Sabemos que el valor óptimo cumple con zPE 5
Algoritmos Básicos para PE Summary

Algoritmo de Branch and Bound

Ejemplo (2) : Resolución de las ramas P5 y P6

El problema P5 se define por:

P5 : {P4 : x4 = 0}

y su solución es z5∗ = 15 51 = 13.8, x1 = 1, x2 = 0, x3 = 15 y x4 = 0. Debido

a que esta es una solución no entera, podemos generar ramas.

El problema P6 se define por:

P6 : {P4 : x4 = 1}

y es No Factible, por lo que se cierra ese nodo de búsqueda.

∗ ∈ 9, 15 1 .
 
Sabemos que el valor óptimo cumple con zPE 5
Algoritmos Básicos para PE Summary

Algoritmo de Branch and Bound

Ejemplo (2) : Resolución de las ramas P5 y P6

Esquemáticamente:
Algoritmos Básicos para PE Summary

Algoritmo de Branch and Bound

Ejemplo (2) : Definición de las ramas P5 y P6

1
Al resolver P5 tenemos que z5∗ = 15 15 , x1 = 1, x2 = 1, x3 = 5 y x4 = 0.

Para generar los nuevos subproblemas (P7 y P8 ) tomaremos la variable

x3 , una rama incluye la restricción x3 ≤ 51 ≤ 0 y la otra rama incluye la
restricción x3 ≥ 15 + 1 ≥ 1.

Sin embargo, puesto que 0 ≤ x3 ≤ 1 entonces lo que en realidad se define

que en P7 , x3 = 0; y en P8 , x3 = 1.
Algoritmos Básicos para PE Summary

Algoritmo de Branch and Bound

Ejemplo (2) : Definición de las ramas P5 y P6

1
Al resolver P5 tenemos que z5∗ = 15 15 , x1 = 1, x2 = 1, x3 = 5 y x4 = 0.

Para generar los nuevos subproblemas (P7 y P8 ) tomaremos la variable

x3 , una rama incluye la restricción x3 ≤ 51 ≤ 0 y la otra rama incluye la
restricción x3 ≥ 15 + 1 ≥ 1.

Sin embargo, puesto que 0 ≤ x3 ≤ 1 entonces lo que en realidad se define

que en P7 , x3 = 0; y en P8 , x3 = 1.
Algoritmos Básicos para PE Summary

Algoritmo de Branch and Bound

Ejemplo (2) : Definición de las ramas P5 y P6

1
Al resolver P5 tenemos que z5∗ = 15 15 , x1 = 1, x2 = 1, x3 = 5 y x4 = 0.

Para generar los nuevos subproblemas (P7 y P8 ) tomaremos la variable

x3 , una rama incluye la restricción x3 ≤ 51 ≤ 0 y la otra rama incluye la
restricción x3 ≥ 15 + 1 ≥ 1.

Sin embargo, puesto que 0 ≤ x3 ≤ 1 entonces lo que en realidad se define

que en P7 , x3 = 0; y en P8 , x3 = 1.
Algoritmos Básicos para PE Summary

Algoritmo de Branch and Bound

Ejemplo (2) : Definición de las ramas P7 y P8

Esquemáticamente
Algoritmos Básicos para PE Summary

Algoritmo de Branch and Bound

Ejemplo (2) : Resolución de las ramas P7 y P8

El problema P7 se define por:

P7 : {P5 : x3 = 0}

y su solución es z7∗ = 14, x1 = 1, x2 = 1, x3 = 0 y x4 = 0. Debido a que

esta es una solución entera y z7∗ = 14 ≥ zapoyo , entonces esta pasa a ser
nuestra solución de apoyo.

El problema P8 se define por:

P8 : {P5 : x3 = 1}

y es No Factible, por lo que se cierra ese nodo de búsqueda.

∗ ∈ [9, 14].
Sabemos que el valor óptimo cumple con zPE
Algoritmos Básicos para PE Summary

Algoritmo de Branch and Bound

Ejemplo (2) : Resolución de las ramas P7 y P8

El problema P7 se define por:

P7 : {P5 : x3 = 0}

y su solución es z7∗ = 14, x1 = 1, x2 = 1, x3 = 0 y x4 = 0. Debido a que

esta es una solución entera y z7∗ = 14 ≥ zapoyo , entonces esta pasa a ser
nuestra solución de apoyo.

El problema P8 se define por:

P8 : {P5 : x3 = 1}

y es No Factible, por lo que se cierra ese nodo de búsqueda.

∗ ∈ [9, 14].
Sabemos que el valor óptimo cumple con zPE
Algoritmos Básicos para PE Summary

Algoritmo de Branch and Bound

Ejemplo (2) : Resolución de las ramas P7 y P8

El problema P7 se define por:

P7 : {P5 : x3 = 0}

y su solución es z7∗ = 14, x1 = 1, x2 = 1, x3 = 0 y x4 = 0. Debido a que

esta es una solución entera y z7∗ = 14 ≥ zapoyo , entonces esta pasa a ser
nuestra solución de apoyo.

El problema P8 se define por:

P8 : {P5 : x3 = 1}

y es No Factible, por lo que se cierra ese nodo de búsqueda.

∗ ∈ [9, 14].
Sabemos que el valor óptimo cumple con zPE
Algoritmos Básicos para PE Summary

Algoritmo de Branch and Bound

Ejemplo (2) : Resolución de las ramas P7 y P8

Esquemáticamente
Algoritmos Básicos para PE Summary

Algoritmo de Branch and Bound

Ejemplo (2) : Definición de más ramas

Sólo se podrian generar ramas a partir de P3 , sin embargo

z3 ≤ zapoyo y dado que se trata de un problema de
maximización, es posible que encontremos una mejor solución
a partir de este nodo.
Por lo tanto, hemos resuelto el problema tal que la solución
óptima está dada por la solución del nodo P7 .
Algoritmos Básicos para PE Summary

Algoritmo de Branch and Bound

Ejemplo (2) : Solución Óptima

Esquemáticamente
Algoritmos Básicos para PE Summary

Outline

1 Algoritmos Básicos para PE

Introducción
Algoritmo de Branch and Bound
Algoritmo de Cutting Plane
Algoritmo de Branch and Cut
Algoritmo de Planos de Corte para TSP
Algoritmos Básicos para PE Summary

Algoritmo de Cutting Plane

Conceptos Básicos

Los algoritmos de planos de corte son una alternativa al

algoritmo Branch & Bound para resolver problemas enteros.

Gomory propuso el primer algoritmo de plano de corte finito en

1958.
Algoritmos Básicos para PE Summary

Algoritmo de Cutting Plane

Conceptos Básicos

Los algoritmos de planos de corte son una alternativa al

algoritmo Branch & Bound para resolver problemas enteros.

Gomory propuso el primer algoritmo de plano de corte finito en

1958.
Algoritmos Básicos para PE Summary

Algoritmo de Cutting Plane

Conceptos Básicos

La idea fundamental de este algoritmo consiste en ir agregando

restricciones a un problema lineal hasta que la solución óptima
encontrada sea entera.

Se debe tener cuidado con las restricciones a ser adicionadas, ya que no se

quiere modificar el problema entero original con las nuevas restricciones.

Por lo tanto, se adicionan nuevas restricciones denominadas cortes.

Algoritmos Básicos para PE Summary

Algoritmo de Cutting Plane

Conceptos Básicos

La idea fundamental de este algoritmo consiste en ir agregando

restricciones a un problema lineal hasta que la solución óptima
encontrada sea entera.

Se debe tener cuidado con las restricciones a ser adicionadas, ya que no se

quiere modificar el problema entero original con las nuevas restricciones.

Por lo tanto, se adicionan nuevas restricciones denominadas cortes.

Algoritmos Básicos para PE Summary

Algoritmo de Cutting Plane

Conceptos Básicos

La idea fundamental de este algoritmo consiste en ir agregando

restricciones a un problema lineal hasta que la solución óptima
encontrada sea entera.

Se debe tener cuidado con las restricciones a ser adicionadas, ya que no se

quiere modificar el problema entero original con las nuevas restricciones.

Por lo tanto, se adicionan nuevas restricciones denominadas cortes.

Algoritmos Básicos para PE Summary

Algoritmo de Cutting Plane

Características de los Cortes

Un corte debe satisfacer las siguientes condiciones:

Ninguna solución entera debe ser excluida, por lo tanto, cada solución
entera debe ser factible para el corte introducido.

Cada corte reduce la región de soluciones factibles, haciendo que la

solución fraccionaria obtenida en la última iteración no sea factible.
Algoritmos Básicos para PE Summary

Algoritmo de Cutting Plane

Características de los Cortes

Un corte debe satisfacer las siguientes condiciones:

Ninguna solución entera debe ser excluida, por lo tanto, cada solución
entera debe ser factible para el corte introducido.

Cada corte reduce la región de soluciones factibles, haciendo que la

solución fraccionaria obtenida en la última iteración no sea factible.
Algoritmos Básicos para PE Summary

Algoritmo de Cutting Plane

Características de los Cortes

Un corte debe satisfacer las siguientes condiciones:

Ninguna solución entera debe ser excluida, por lo tanto, cada solución
entera debe ser factible para el corte introducido.

Cada corte reduce la región de soluciones factibles, haciendo que la

solución fraccionaria obtenida en la última iteración no sea factible.
Algoritmos Básicos para PE Summary

Algoritmo de Cutting Plane

Características de los Cortes : Ejemplo
Algoritmos Básicos para PE Summary

Algoritmo de Cutting Plane

Características de los Cortes : Ejemplo
Algoritmos Básicos para PE Summary

Algoritmo de Cutting Plane

Características de los Cortes : Ejemplo
Algoritmos Básicos para PE Summary

Algoritmo de Cutting Plane

Características de los Cortes : Ejemplo
Algoritmos Básicos para PE Summary

Algoritmo de Cutting Plane

Descripción General del Algoritmo

Resolver la relajación lineal del problema entero.

Si la solución óptima (x*) es entera, entonces x* es una

solución óptima para el problema entero.

En caso contrario, agregar una restricción lineal (corte) que

sea satisfecha por todas las soluciones enteras del problema
original pero no por x*. Volver al paso 2.
Algoritmos Básicos para PE Summary

Algoritmo de Cutting Plane

Descripción General del Algoritmo

Resolver la relajación lineal del problema entero.

Si la solución óptima (x*) es entera, entonces x* es una

solución óptima para el problema entero.

En caso contrario, agregar una restricción lineal (corte) que

sea satisfecha por todas las soluciones enteras del problema
original pero no por x*. Volver al paso 2.
Algoritmos Básicos para PE Summary

Algoritmo de Cutting Plane

Descripción General del Algoritmo

Resolver la relajación lineal del problema entero.

Si la solución óptima (x*) es entera, entonces x* es una

solución óptima para el problema entero.

En caso contrario, agregar una restricción lineal (corte) que

sea satisfecha por todas las soluciones enteras del problema
original pero no por x*. Volver al paso 2.
Algoritmos Básicos para PE Summary

Algoritmo de Cutting Plane

Ejemplo (1) : Problema de PE a resolver

Resolveremos el siguiente problema

PE: max z = 7x1 + 9x2

subject to
−x1 + 3x2 ≤ 6
7x1 + x2 ≤ 35
x1 , x2 enteros positivos
Algoritmos Básicos para PE Summary

Algoritmo de Cutting Plane

Ejemplo (1) : Problema de PE a resolver

Resolveremos el siguiente problema

PE: max z = 7x1 + 9x2

subject to
−x1 + 3x2 ≤ 6
7x1 + x2 ≤ 35
x1 , x2 enteros positivos
Algoritmos Básicos para PE Summary

Algoritmo de Cutting Plane

Ejemplo (1) : El Problema de RL

El problema de RL está dado por

PE: max z = 7x1 + 9x2

subject to
−x1 + 3x2 ≤ 6
7x1 + x2 ≤ 35
x1 , x2 ≥ 0
Algoritmos Básicos para PE Summary

Algoritmo de Cutting Plane

Ejemplo (1) : El Problema de RL

El problema de RL está dado por

PE: max z = 7x1 + 9x2

subject to
−x1 + 3x2 ≤ 6
7x1 + x2 ≤ 35
x1 , x2 ≥ 0
Algoritmos Básicos para PE Summary

Algoritmo de Cutting Plane

Ejemplo (1) : El Problema de RL

El tableau óptimo de RL (T0) está dado por:

VB x1 x2 s1 s2 b
z 0 0 28/11 15/11 63
x2 0 1 7/22 1/22 7/2
x1 1 0 −1/22 3/22 9/2

Generaremos un plano de corte agregando una restricción que

asociada a x2 (cuyo valor es no entero).
Algoritmos Básicos para PE Summary

Algoritmo de Cutting Plane

Ejemplo (1) : El Problema de RL

El tableau óptimo de RL (T0) está dado por:

VB x1 x2 s1 s2 b
z 0 0 28/11 15/11 63
x2 0 1 7/22 1/22 7/2
x1 1 0 −1/22 3/22 9/2

Generaremos un plano de corte agregando una restricción que

asociada a x2 (cuyo valor es no entero).
Algoritmos Básicos para PE Summary

Algoritmo de Cutting Plane

Ejemplo (1) : El Problema de RL

El tableau óptimo de RL (T0) está dado por:

VB x1 x2 s1 s2 b
z 0 0 28/11 15/11 63
x2 0 1 7/22 1/22 7/2
x1 1 0 −1/22 3/22 9/2

Generaremos un plano de corte agregando una restricción que

asociada a x2 (cuyo valor es no entero).
Algoritmos Básicos para PE Summary

Algoritmo de Cutting Plane

Ejemplo (1) : Generación del Primer Corte

Un corte se agrega escribiendo el coeficiente de cada variable

(coeficientes del tableau) de la forma kck + f , donde 0 ≤ f ≤ 1.

El corte asociado a x2 está dado por:

7 1 7
x 2 + s1 + s2 =
  22
 22 2
7 1 1
x2 + 0 + s1 + 0 + s2 = 3+
22 22 2
7 1 1
x2 − 3 = − s1 − s2 +
22 22 2
Algoritmos Básicos para PE Summary

Algoritmo de Cutting Plane

Ejemplo (1) : Generación del Primer Corte

Un corte se agrega escribiendo el coeficiente de cada variable

(coeficientes del tableau) de la forma kck + f , donde 0 ≤ f ≤ 1.

El corte asociado a x2 está dado por:

7 1 7
x 2 + s1 + s2 =
  22
 22 2
7 1 1
x2 + 0 + s1 + 0 + s2 = 3+
22 22 2
7 1 1
x2 − 3 = − s1 − s2 +
22 22 2
Algoritmos Básicos para PE Summary

Algoritmo de Cutting Plane

Ejemplo (1) : Generación del Primer Corte

La solución fraccionaria obtenida en la última iteración no debe ser

factible.

Por lo tanto, se introduce la restricción:

7 1 1
− s1 − s2 + ≤ 0
22 22 2

Transformando esta restricción en igualdad, se tiene:

7 1 1
− s1 − s2 + s3 = −
22 22 2
Algoritmos Básicos para PE Summary

Algoritmo de Cutting Plane

Ejemplo (1) : Generación del Primer Corte

La solución fraccionaria obtenida en la última iteración no debe ser

factible.

Por lo tanto, se introduce la restricción:

7 1 1
− s1 − s2 + ≤ 0
22 22 2

Transformando esta restricción en igualdad, se tiene:

7 1 1
− s1 − s2 + s3 = −
22 22 2
Algoritmos Básicos para PE Summary

Algoritmo de Cutting Plane

Ejemplo (1) : Generación del Primer Corte

La solución fraccionaria obtenida en la última iteración no debe ser

factible.

Por lo tanto, se introduce la restricción:

7 1 1
− s1 − s2 + ≤ 0
22 22 2

Transformando esta restricción en igualdad, se tiene:

7 1 1
− s1 − s2 + s3 = −
22 22 2
Algoritmos Básicos para PE Summary

Algoritmo de Cutting Plane

Ejemplo (1) : Generación del Primer Corte

El nuevo tableau (T1) queda:

VB x1 x2 s1 s2 s3 b
z 0 0 28/11 15/11 0 63
x2 0 1 7/22 1/22 0 7/2
x1 1 0 −1/22 3/22 0 9/2
s3 0 0 −7/22 −1/22 1 −1/2

Resolveremos ahora el problema en T1.

Algoritmos Básicos para PE Summary

Algoritmo de Cutting Plane

Ejemplo (1) : Generación del Primer Corte

El nuevo tableau (T1) queda:

VB x1 x2 s1 s2 s3 b
z 0 0 28/11 15/11 0 63
x2 0 1 7/22 1/22 0 7/2
x1 1 0 −1/22 3/22 0 9/2
s3 0 0 −7/22 −1/22 1 −1/2

Resolveremos ahora el problema en T1.

Algoritmos Básicos para PE Summary

Algoritmo de Cutting Plane

Ejemplo (1) : Generación del Primer Corte

El nuevo tableau (T1) queda:

VB x1 x2 s1 s2 s3 b
z 0 0 28/11 15/11 0 63
x2 0 1 7/22 1/22 0 7/2
x1 1 0 −1/22 3/22 0 9/2
s3 0 0 −7/22 −1/22 1 −1/2

Resolveremos ahora el problema en T1.

Algoritmos Básicos para PE Summary

Algoritmo de Cutting Plane

Ejemplo (1) : Generación del Primer Corte

Puesto que el Tableau actual define una solución que no es

factible (s3 es negativo), es necesario aplicar un procedimiento
llamado “dual-símplex” para buscar una nueva solución.

Buscamos la variable que sale observando las filas, y la variable

que entra observando las columnas.
Algoritmos Básicos para PE Summary

Algoritmo de Cutting Plane

Ejemplo (1) : Generación del Primer Corte

Puesto que el Tableau actual define una solución que no es

factible (s3 es negativo), es necesario aplicar un procedimiento
llamado “dual-símplex” para buscar una nueva solución.

Buscamos la variable que sale observando las filas, y la variable

que entra observando las columnas.
Algoritmos Básicos para PE Summary

Algoritmo de Cutting Plane

Ejemplo (1) : Generación del Primer Corte

Entonces elegimos:

−56/7 −30
VB x1 x2 s1 s2 s3 b
z 0 0 28/11 15/11 0 63
x2 0 1 7/22 1/22 0 7/2
x1 1 0 −1/22 3/22 0 9/2
s3 0 0 −7/22 −1/22 1 −1/2

Es decir, saldrá s3 y entrará s1 .

Algoritmos Básicos para PE Summary

Algoritmo de Cutting Plane

Ejemplo (1) : Generación del Primer Corte

Entonces elegimos:

−56/7 −30
VB x1 x2 s1 s2 s3 b
z 0 0 28/11 15/11 0 63
x2 0 1 7/22 1/22 0 7/2
x1 1 0 −1/22 3/22 0 9/2
s3 0 0 −7/22 −1/22 1 −1/2

Es decir, saldrá s3 y entrará s1 .

Algoritmos Básicos para PE Summary

Algoritmo de Cutting Plane

Ejemplo (1) : Generación del Primer Corte

Entonces elegimos:

−56/7 −30
VB x1 x2 s1 s2 s3 b
z 0 0 28/11 15/11 0 63
x2 0 1 7/22 1/22 0 7/2
x1 1 0 −1/22 3/22 0 9/2
s3 0 0 −7/22 −1/22 1 −1/2

Es decir, saldrá s3 y entrará s1 .

Algoritmos Básicos para PE Summary

Algoritmo de Cutting Plane

Ejemplo (1) : Generación del Primer Corte

Luego de las correspondientes operaciones fila, obtenemos:

VB x1 x2 s1 s2 s3 b
z 0 0 0 1 8 59
x2 0 1 0 0 1 3
x1 1 0 0 1/7 −1/7 32/7
s1 0 0 1 1/7 −22/7 11/7

Tenemos que generar un plano de corte considerando x1 , puesto

que no es entera.
Algoritmos Básicos para PE Summary

Algoritmo de Cutting Plane

Ejemplo (1) : Generación del Primer Corte

Luego de las correspondientes operaciones fila, obtenemos:

VB x1 x2 s1 s2 s3 b
z 0 0 0 1 8 59
x2 0 1 0 0 1 3
x1 1 0 0 1/7 −1/7 32/7
s1 0 0 1 1/7 −22/7 11/7

Tenemos que generar un plano de corte considerando x1 , puesto

que no es entera.
Algoritmos Básicos para PE Summary

Algoritmo de Cutting Plane

Ejemplo (1) : Generación del Primer Corte

Luego de las correspondientes operaciones fila, obtenemos:

VB x1 x2 s1 s2 s3 b
z 0 0 0 1 8 59
x2 0 1 0 0 1 3
x1 1 0 0 1/7 −1/7 32/7
s1 0 0 1 1/7 −22/7 11/7

Tenemos que generar un plano de corte considerando x1 , puesto

que no es entera.
Algoritmos Básicos para PE Summary

Algoritmo de Cutting Plane

Ejemplo (1) : Generación del Segundo Corte

Consideramos ahora la fila correspondiente a x1 .

Esta fila se puede escribir como:

1 1 32
x1 + s2 − s3 =
   7 7 7
1 6 4
x1 + 0 + s2 + −1 + s3 = 4 +
7 7 7
1 6 4
x1 − s3 − 4 = − s2 − s3 +
7 7 7
Algoritmos Básicos para PE Summary

Algoritmo de Cutting Plane

Ejemplo (1) : Generación del Segundo Corte

Consideramos ahora la fila correspondiente a x1 .

Esta fila se puede escribir como:

1 1 32
x1 + s2 − s3 =
   7 7 7
1 6 4
x1 + 0 + s2 + −1 + s3 = 4 +
7 7 7
1 6 4
x1 − s3 − 4 = − s2 − s3 +
7 7 7
Algoritmos Básicos para PE Summary

Algoritmo de Cutting Plane

Ejemplo (1) : Generación del Segundo Corte

La solución fraccionaria obtenida en la última iteración no

debe ser factible.

Por lo tanto, se introduce la restricción:

1 6 4
− s2 − s3 + ≤ 0
7 7 7

Transformando esta restricción en igualdad, se tiene:

1 6 4
− s2 − s3 + s4 = −
7 7 7
Algoritmos Básicos para PE Summary

Algoritmo de Cutting Plane

Ejemplo (1) : Generación del Segundo Corte

La solución fraccionaria obtenida en la última iteración no

debe ser factible.

Por lo tanto, se introduce la restricción:

1 6 4
− s2 − s3 + ≤ 0
7 7 7

Transformando esta restricción en igualdad, se tiene:

1 6 4
− s2 − s3 + s4 = −
7 7 7
Algoritmos Básicos para PE Summary

Algoritmo de Cutting Plane

Ejemplo (1) : Generación del Segundo Corte

La solución fraccionaria obtenida en la última iteración no

debe ser factible.

Por lo tanto, se introduce la restricción:

1 6 4
− s2 − s3 + ≤ 0
7 7 7

Transformando esta restricción en igualdad, se tiene:

1 6 4
− s2 − s3 + s4 = −
7 7 7
Algoritmos Básicos para PE Summary

Algoritmo de Cutting Plane

Ejemplo (1) : Generación del Segundo Corte

Debemos incluir esta restricción en el tableau, obteniéndo:

VB x1 x2 s1 s2 s3 s4 b
z 0 0 0 1 8 0 59
x2 0 1 0 0 1 0 3
x1 1 0 0 1/7 −1/7 0 32/7
s1 0 0 1 1/7 −22/7 0 11/7
s4 0 0 0 −1/7 −6/7 1 −4/7

Debemos hacer nuevamente operaciones filas con tal de encontrar

una solución factible.
Algoritmos Básicos para PE Summary

Algoritmo de Cutting Plane

Ejemplo (1) : Generación del Segundo Corte

Debemos incluir esta restricción en el tableau, obteniéndo:

VB x1 x2 s1 s2 s3 s4 b
z 0 0 0 1 8 0 59
x2 0 1 0 0 1 0 3
x1 1 0 0 1/7 −1/7 0 32/7
s1 0 0 1 1/7 −22/7 0 11/7
s4 0 0 0 −1/7 −6/7 1 −4/7

Debemos hacer nuevamente operaciones filas con tal de encontrar

una solución factible.
Algoritmos Básicos para PE Summary

Algoritmo de Cutting Plane

Ejemplo (1) : Generación del Segundo Corte

Debemos incluir esta restricción en el tableau, obteniéndo:

VB x1 x2 s1 s2 s3 s4 b
z 0 0 0 1 8 0 59
x2 0 1 0 0 1 0 3
x1 1 0 0 1/7 −1/7 0 32/7
s1 0 0 1 1/7 −22/7 0 11/7
s4 0 0 0 −1/7 −6/7 1 −4/7

Debemos hacer nuevamente operaciones filas con tal de encontrar

una solución factible.
Algoritmos Básicos para PE Summary

Algoritmo de Cutting Plane

Ejemplo (1) : Generación del Segundo Corte

La variable que entra y la variable que sale se muestran a

continuación:

−7 −56/7
VB x1 x2 s1 s2 s3 s4 b
z 0 0 0 1 8 0 59
x2 0 1 0 0 1 0 3
x1 1 0 0 1/7 −1/7 0 32/7
s1 0 0 1 1/7 −22/7 0 11/7
s4 0 0 0 −1/7 −6/7 1 −4/7

Entonces, saldrá s4 y entrará s2 .

Algoritmos Básicos para PE Summary

Algoritmo de Cutting Plane

Ejemplo (1) : Generación del Segundo Corte

La variable que entra y la variable que sale se muestran a

continuación:

−7 −56/7
VB x1 x2 s1 s2 s3 s4 b
z 0 0 0 1 8 0 59
x2 0 1 0 0 1 0 3
x1 1 0 0 1/7 −1/7 0 32/7
s1 0 0 1 1/7 −22/7 0 11/7
s4 0 0 0 −1/7 −6/7 1 −4/7

Entonces, saldrá s4 y entrará s2 .

Algoritmos Básicos para PE Summary

Algoritmo de Cutting Plane

Ejemplo (1) : Generación del Segundo Corte

La variable que entra y la variable que sale se muestran a

continuación:

−7 −56/7
VB x1 x2 s1 s2 s3 s4 b
z 0 0 0 1 8 0 59
x2 0 1 0 0 1 0 3
x1 1 0 0 1/7 −1/7 0 32/7
s1 0 0 1 1/7 −22/7 0 11/7
s4 0 0 0 −1/7 −6/7 1 −4/7

Entonces, saldrá s4 y entrará s2 .

Algoritmos Básicos para PE Summary

Algoritmo de Cutting Plane

Ejemplo (1) : Generación del Segundo Corte

Realizando las correspondiente operaciones fila, obtenemos el

siguiente Tableau (T2):

VB x1 x2 s1 s2 s3 s4 b
z 0 0 0 0 2 7 55
x2 0 1 0 0 1 0 3
x1 1 0 0 0 −1 1 4
s1 0 0 1 0 −4 1 1
s2 0 0 0 1 6 −7 4

En este tableau hemos encontrado una solución entera, por lo que

no es necesario generar un nuevo corte. Esta es la solución óptima
al problema de PE.
Algoritmos Básicos para PE Summary

Algoritmo de Cutting Plane

Ejemplo (1) : Generación del Segundo Corte

Realizando las correspondiente operaciones fila, obtenemos el

siguiente Tableau (T2):

VB x1 x2 s1 s2 s3 s4 b
z 0 0 0 0 2 7 55
x2 0 1 0 0 1 0 3
x1 1 0 0 0 −1 1 4
s1 0 0 1 0 −4 1 1
s2 0 0 0 1 6 −7 4

En este tableau hemos encontrado una solución entera, por lo que

no es necesario generar un nuevo corte. Esta es la solución óptima
al problema de PE.
Algoritmos Básicos para PE Summary

Algoritmo de Cutting Plane

Ejemplo (1) : Generación del Segundo Corte

Realizando las correspondiente operaciones fila, obtenemos el

siguiente Tableau (T2):

VB x1 x2 s1 s2 s3 s4 b
z 0 0 0 0 2 7 55
x2 0 1 0 0 1 0 3
x1 1 0 0 0 −1 1 4
s1 0 0 1 0 −4 1 1
s2 0 0 0 1 6 −7 4

En este tableau hemos encontrado una solución entera, por lo que

no es necesario generar un nuevo corte. Esta es la solución óptima
al problema de PE.
Algoritmos Básicos para PE Summary

Algoritmo de Cutting Plane

Ejemplo (1) : Solución Óptima al Problema de PE

La solución al problema de PE es z ∗ = 55, x1∗ = 4 y x2∗ = 3

Algoritmos Básicos para PE Summary

Algoritmo de Cutting Plane

Problemas con el Algoritmo

Cada corte generalmente elimina una parte muy pequeña

de la región factible.

Aunque es un algoritmo finito, ningún algoritmo de plano

de corte converge en tiempo polinomial.

Mientras más se conozca sobre la estructura del

problema, se podrán generar mejores planos de corte.
Algoritmos Básicos para PE Summary

Algoritmo de Cutting Plane

Problemas con el Algoritmo

Cada corte generalmente elimina una parte muy pequeña

de la región factible.

Aunque es un algoritmo finito, ningún algoritmo de plano

de corte converge en tiempo polinomial.

Mientras más se conozca sobre la estructura del

problema, se podrán generar mejores planos de corte.
Algoritmos Básicos para PE Summary

Algoritmo de Cutting Plane

Problemas con el Algoritmo

Cada corte generalmente elimina una parte muy pequeña

de la región factible.

Aunque es un algoritmo finito, ningún algoritmo de plano

de corte converge en tiempo polinomial.

Mientras más se conozca sobre la estructura del

problema, se podrán generar mejores planos de corte.
Algoritmos Básicos para PE Summary

Outline

1 Algoritmos Básicos para PE

Introducción
Algoritmo de Branch and Bound
Algoritmo de Cutting Plane
Algoritmo de Branch and Cut
Algoritmo de Planos de Corte para TSP
Algoritmos Básicos para PE Summary

Algoritmo de Branch and Cut

La idea es Branch and Bound + Cutting Planes = Branchand Cut

Tanto Branch and Bound como Cutting Planes son algoritmos

exactos que podrían tener un pobre desempeño.

¿Será posible encontrar un algoritmo de mejor desempeño

mezclando ambos elementos?

Es decir, ¿existe algún algoritmo que mezcle Branch and Bound y

Cutting Planes pero que sea mejor, al menos en la práctica?

La respuesta es sí:Branch and Cut (Ramificación y corte).

Algoritmos Básicos para PE Summary

Algoritmo de Branch and Cut

La idea es Branch and Bound + Cutting Planes = Branchand Cut

Tanto Branch and Bound como Cutting Planes son algoritmos

exactos que podrían tener un pobre desempeño.

¿Será posible encontrar un algoritmo de mejor desempeño

mezclando ambos elementos?

Es decir, ¿existe algún algoritmo que mezcle Branch and Bound y

Cutting Planes pero que sea mejor, al menos en la práctica?

La respuesta es sí:Branch and Cut (Ramificación y corte).

Algoritmos Básicos para PE Summary

Algoritmo de Branch and Cut

La idea es Branch and Bound + Cutting Planes = Branchand Cut

Tanto Branch and Bound como Cutting Planes son algoritmos

exactos que podrían tener un pobre desempeño.

¿Será posible encontrar un algoritmo de mejor desempeño

mezclando ambos elementos?

Es decir, ¿existe algún algoritmo que mezcle Branch and Bound y

Cutting Planes pero que sea mejor, al menos en la práctica?

La respuesta es sí:Branch and Cut (Ramificación y corte).

Algoritmos Básicos para PE Summary

Algoritmo de Branch and Cut

La idea es Branch and Bound + Cutting Planes = Branchand Cut

Tanto Branch and Bound como Cutting Planes son algoritmos

exactos que podrían tener un pobre desempeño.

¿Será posible encontrar un algoritmo de mejor desempeño

mezclando ambos elementos?

Es decir, ¿existe algún algoritmo que mezcle Branch and Bound y

Cutting Planes pero que sea mejor, al menos en la práctica?

La respuesta es sí:Branch and Cut (Ramificación y corte).

Algoritmos Básicos para PE Summary

Algoritmo de Branch and Cut

La idea es Branch and Bound + Cutting Planes = Branchand Cut
Algoritmos Básicos para PE Summary

Algoritmo de Branch and Cut

Branchand Cut (Ejemplo 1)

Consideremos el siguiente problema de PE:

max z = {5x1 + 8x2 : x1 + x2 ≤ 6, 5x1 + 9x2 ≤ 45, x1 , x2 enteros}

Entonces el problema de RL de PE (P0 ) es:

P0 : max z = {5x1 + 8x2 : x1 + x2 ≤ 6, 5x1 + 9x2 ≤ 45, x1 , x2 ≥ 0}

Algoritmos Básicos para PE Summary

Algoritmo de Branch and Cut

Branchand Cut (Ejemplo 1)

Consideremos el siguiente problema de PE:

max z = {5x1 + 8x2 : x1 + x2 ≤ 6, 5x1 + 9x2 ≤ 45, x1 , x2 enteros}

Entonces el problema de RL de PE (P0 ) es:

P0 : max z = {5x1 + 8x2 : x1 + x2 ≤ 6, 5x1 + 9x2 ≤ 45, x1 , x2 ≥ 0}

Algoritmos Básicos para PE Summary

Algoritmo de Branch and Cut

Branchand Cut (Ejemplo 1)

Consideremos el siguiente problema de PE:

max z = {5x1 + 8x2 : x1 + x2 ≤ 6, 5x1 + 9x2 ≤ 45, x1 , x2 enteros}

Entonces el problema de RL de PE (P0 ) es:

P0 : max z = {5x1 + 8x2 : x1 + x2 ≤ 6, 5x1 + 9x2 ≤ 45, x1 , x2 ≥ 0}

Algoritmos Básicos para PE Summary

Algoritmo de Branch and Cut

Branchand Cut (Ejemplo 1)

Consideremos el siguiente problema de PE:

max z = {5x1 + 8x2 : x1 + x2 ≤ 6, 5x1 + 9x2 ≤ 45, x1 , x2 enteros}

Entonces el problema de RL de PE (P0 ) es:

P0 : max z = {5x1 + 8x2 : x1 + x2 ≤ 6, 5x1 + 9x2 ≤ 45, x1 , x2 ≥ 0}

Algoritmos Básicos para PE Summary

Algoritmo de Branch and Cut

Branchand Cut (Ejemplo 1)

Al resolver P0 tenemos que z0∗ = 41 14 , x1 = 9

4 = 2.25, x2 = 15
4 = 3.75.

Para generar los nuevos subproblemas (P1 y P2 ) tomaremos la variable

x2 , una rama incluye la restricción x2 ≤ k3.75k ≤ 3 y la otra rama incluye
la restricción x2 ≥ k3.75k + 1 ≥ 4.
Algoritmos Básicos para PE Summary

Algoritmo de Branch and Cut

Branchand Cut (Ejemplo 1)

Al resolver P0 tenemos que z0∗ = 41 14 , x1 = 9

4 = 2.25, x2 = 15
4 = 3.75.

Para generar los nuevos subproblemas (P1 y P2 ) tomaremos la variable

x2 , una rama incluye la restricción x2 ≤ k3.75k ≤ 3 y la otra rama incluye
la restricción x2 ≥ k3.75k + 1 ≥ 4.
Algoritmos Básicos para PE Summary

Algoritmo de Branch and Cut

Branchand Cut (Ejemplo 1) Definición de P1 y P2

Esquemáticamente:
Algoritmos Básicos para PE Summary

Algoritmo de Branch and Cut

Branchand Cut (Ejemplo 1) Resolución de P1 y P2

Ahora, comenzamos a diferenciarnos del algoritmo de Branch and Bound,

pues los problemas P1 y P2 serán resueltos para luego agregar un plano
de corte.

El problema P1 se define por:

P1 : max z = {5x1 + 8x2 : x1 + x2 ≤ 6, 5x1 + 9x2 ≤ 45, x2 ≤ 3, x1 , x2 ≥ 0}

y su solución es z1∗ = 39, x1 = 3, x2 = 3. Debido a que esta es una

solución entera, pasa a ser una solución de apoyo.

El problema P2 se define por:

P2 : max z = {5x1 + 8x2 : x1 + x2 ≤ 6, 5x1 + 9x2 ≤ 45, x2 ≥ 4, x1 , x2 ≥ 0}

y su solución esz2∗ = 41, x1 = 59 , x2 = 4. Debido a que esta solución no

es entera, agregaremos un plano de corte.
Algoritmos Básicos para PE Summary

Algoritmo de Branch and Cut

Branchand Cut (Ejemplo 1) Resolución de P1 y P2

Ahora, comenzamos a diferenciarnos del algoritmo de Branch and Bound,

pues los problemas P1 y P2 serán resueltos para luego agregar un plano
de corte.

El problema P1 se define por:

P1 : max z = {5x1 + 8x2 : x1 + x2 ≤ 6, 5x1 + 9x2 ≤ 45, x2 ≤ 3, x1 , x2 ≥ 0}

y su solución es z1∗ = 39, x1 = 3, x2 = 3. Debido a que esta es una

solución entera, pasa a ser una solución de apoyo.

El problema P2 se define por:

P2 : max z = {5x1 + 8x2 : x1 + x2 ≤ 6, 5x1 + 9x2 ≤ 45, x2 ≥ 4, x1 , x2 ≥ 0}

y su solución esz2∗ = 41, x1 = 59 , x2 = 4. Debido a que esta solución no

es entera, agregaremos un plano de corte.
Algoritmos Básicos para PE Summary

Algoritmo de Branch and Cut

Branchand Cut (Ejemplo 1) Resolución de P1 y P2

Ahora, comenzamos a diferenciarnos del algoritmo de Branch and Bound,

pues los problemas P1 y P2 serán resueltos para luego agregar un plano
de corte.

El problema P1 se define por:

P1 : max z = {5x1 + 8x2 : x1 + x2 ≤ 6, 5x1 + 9x2 ≤ 45, x2 ≤ 3, x1 , x2 ≥ 0}

y su solución es z1∗ = 39, x1 = 3, x2 = 3. Debido a que esta es una

solución entera, pasa a ser una solución de apoyo.

El problema P2 se define por:

P2 : max z = {5x1 + 8x2 : x1 + x2 ≤ 6, 5x1 + 9x2 ≤ 45, x2 ≥ 4, x1 , x2 ≥ 0}

y su solución esz2∗ = 41, x1 = 59 , x2 = 4. Debido a que esta solución no

es entera, agregaremos un plano de corte.
Algoritmos Básicos para PE Summary

Algoritmo de Branch and Cut

Branchand Cut (Ejemplo 1) Resolución de P1 y P2

Esquemáticamente:
Algoritmos Básicos para PE Summary

Algoritmo de Branch and Cut

Branchand Cut (Ejemplo 1) Agregar un corte en P2

Al resolver P2 se llega al siguiente Tableu:

s džϭ džϮ Ɛϭ ƐϮ Ɛϯ ď
nj Ϭ Ϭ Ϭ ϭ ϭ ϰϭ
džϭ ϭ Ϭ Ϭ ϭͬϱ ϵͬϱ ϵͬϱ
Ɛϭ Ϭ Ϭ ϭ Ͳϭͬϱ Ͳϰͬϱ ϭͬϱ
džϮ Ϭ ϭ Ϭ Ϭ Ͳϭ ϰ

Es claro que debemos generar un corte para la variable x1 .

Algoritmos Básicos para PE Summary

Algoritmo de Branch and Cut

Branchand Cut (Ejemplo 1) Agregar un corte en P2

Al resolver P2 se llega al siguiente Tableu:

s džϭ džϮ Ɛϭ ƐϮ Ɛϯ ď
nj Ϭ Ϭ Ϭ ϭ ϭ ϰϭ
džϭ ϭ Ϭ Ϭ ϭͬϱ ϵͬϱ ϵͬϱ
Ɛϭ Ϭ Ϭ ϭ Ͳϭͬϱ Ͳϰͬϱ ϭͬϱ
džϮ Ϭ ϭ Ϭ Ϭ Ͳϭ ϰ

Es claro que debemos generar un corte para la variable x1 .

Algoritmos Básicos para PE Summary

Algoritmo de Branch and Cut

Branchand Cut (Ejemplo 1) Agregar un corte en P2

La fila de x1 se puede escribir como:

1 9 9
x1 + s2 + s3 =
  5 5 5
1 4 4
x1 + 0 + s2 + 1 + s3 = 1 +
5 5 5
1 4 4
x1 + s3 − 1 = − s2 − s3 +
5 5 5

Por lo que se agrega la siguiente restricción (corte)

1 4 4
− s2 − s3 + s4 = −
5 5 5
Algoritmos Básicos para PE Summary

Algoritmo de Branch and Cut

Branchand Cut (Ejemplo 1) Agregar un corte en P2

La fila de x1 se puede escribir como:

1 9 9
x1 + s2 + s3 =
  5 5 5
1 4 4
x1 + 0 + s2 + 1 + s3 = 1 +
5 5 5
1 4 4
x1 + s3 − 1 = − s2 − s3 +
5 5 5

Por lo que se agrega la siguiente restricción (corte)

1 4 4
− s2 − s3 + s4 = −
5 5 5
Algoritmos Básicos para PE Summary

Algoritmo de Branch and Cut

Branchand Cut (Ejemplo 1) Agregar un corte en P2

El nuevo tableu es

s džϭ džϮ Ɛϭ ƐϮ Ɛϯ Ɛϰ ď
nj Ϭ Ϭ Ϭ ϭ ϭ Ϭ ϰϭ
džϭ ϭ Ϭ Ϭ ϭͬϱ ϵͬϱ Ϭ ϵͬϱ
Ɛϭ Ϭ Ϭ ϭ Ͳϭͬϱ Ͳϰͬϱ Ϭ ϭͬϱ
džϮ Ϭ ϭ Ϭ Ϭ Ͳϭ Ϭ ϰ
Ɛϰ Ϭ Ϭ Ϭ Ͳϭͬϱ Ͳϰͬϱ ϭ Ͳϰͬϱ
Algoritmos Básicos para PE Summary

Algoritmo de Branch and Cut

Branchand Cut (Ejemplo 1) Agregar un corte en P2

Las variables a entrar y salir se muestran a continuación

Ͳϱ Ͳϱͬϰ
s džϭ džϮ Ɛϭ ƐϮ Ɛϯ Ɛϰ ď
nj Ϭ Ϭ Ϭ ϭ ϭ Ϭ ϰϭ
džϭ ϭ Ϭ Ϭ ϭͬϱ ϵͬϱ Ϭ ϵͬϱ
Ɛϭ Ϭ Ϭ ϭ Ͳϭͬϱ Ͳϰͬϱ Ϭ ϭͬϱ
džϮ Ϭ ϭ Ϭ Ϭ Ͳϭ Ϭ ϰ
Ɛϰ Ϭ Ϭ Ϭ Ͳϭͬϱ Ͳϰͬϱ ϭ Ͳϰͬϱ
Algoritmos Básicos para PE Summary

Algoritmo de Branch and Cut

Branchand Cut (Ejemplo 1) Agregar un corte en P2

Al aplicar las operaciones fila, el tableau es:

s džϭ džϮ Ɛϭ ƐϮ Ɛϯ Ɛϰ ď
nj Ϭ Ϭ Ϭ ϯͬϰ Ϭ ϱͬϰ ϰϬ
džϭ ϭ Ϭ Ϭ Ͳϭͬϰ Ϭ ϵͬϰ Ϭ
Ɛϭ Ϭ Ϭ ϭ Ϭ Ϭ Ͳϭ ϭ
džϮ Ϭ ϭ Ϭ ϭͬϰ Ϭ Ͳϱͬϰ ϱ
Ɛϯ Ϭ Ϭ Ϭ ϭͬϰ ϭ Ͳϱͬϰ ϭ
Algoritmos Básicos para PE Summary

Algoritmo de Branch and Cut

Branchand Cut (Ejemplo 1) Agregar un corte en P2

Agregado el nuevo corte, el esquema del algoritmo es el siguiente:

P0: z 0*=41 1/4,

x1=2.25, x 2=3.75

x2≤3 x2≥4

P 0: z 1*=39, x 1=3, P 2: z 2*=41,

x 2=3 x 1=9/5, x 2=4

Agregamos corte para x 1

P2: z2*=40,
x 1=0, x 2=5
Algoritmos Básicos para PE Summary

Algoritmo de Branch and Cut

Branchand Cut (Ejemplo 1) Agregar un corte en P2

Es claro que ya no podemos seguir generando ramas, pues no

hay nodos con variables fracionarias.

La nueva solución del problema P2 mejora el valor de z1∗ , por

lo tanto es la solución de P2 obtenida luego de agregar el corte
la solución óptima del problema.
Algoritmos Básicos para PE Summary

Algoritmo de Branch and Cut

Branchand Cut (Ejemplo 1) Agregar un corte en P2

Es claro que ya no podemos seguir generando ramas, pues no

hay nodos con variables fracionarias.

La nueva solución del problema P2 mejora el valor de z1∗ , por

lo tanto es la solución de P2 obtenida luego de agregar el corte
la solución óptima del problema.
Algoritmos Básicos para PE Summary

Outline

1 Algoritmos Básicos para PE

Introducción
Algoritmo de Branch and Bound
Algoritmo de Cutting Plane
Algoritmo de Branch and Cut
Algoritmo de Planos de Corte para TSP
Algoritmos Básicos para PE Summary

Diferentes tipos de “cortes”

Extensiones del algoritmo de Branch and Cut

Tanto el algoritmo de Cutting Planes como el Algoritmo de

Branch and Cut que hemos mostrado, ambos consideran
planos de corte denominados “cortes de Gomory”.

Los cortes de Gomory son un tipo de corte que puede aplicarse

a cualquier problema de Programación Lineal Entera.

Sin embargo, es posible que dado un problema particular se

puedan generar “cortes” o restricciones que permiten resolver
en forma más eficiente ese problema en particular.
Algoritmos Básicos para PE Summary

Diferentes tipos de “cortes”

Extensiones del algoritmo de Branch and Cut

Tanto el algoritmo de Cutting Planes como el Algoritmo de

Branch and Cut que hemos mostrado, ambos consideran
planos de corte denominados “cortes de Gomory”.

Los cortes de Gomory son un tipo de corte que puede aplicarse

a cualquier problema de Programación Lineal Entera.

Sin embargo, es posible que dado un problema particular se

puedan generar “cortes” o restricciones que permiten resolver
en forma más eficiente ese problema en particular.
Algoritmos Básicos para PE Summary

Diferentes tipos de “cortes”

Extensiones del algoritmo de Branch and Cut

Tanto el algoritmo de Cutting Planes como el Algoritmo de

Branch and Cut que hemos mostrado, ambos consideran
planos de corte denominados “cortes de Gomory”.

Los cortes de Gomory son un tipo de corte que puede aplicarse

a cualquier problema de Programación Lineal Entera.

Sin embargo, es posible que dado un problema particular se

puedan generar “cortes” o restricciones que permiten resolver
en forma más eficiente ese problema en particular.
Algoritmos Básicos para PE Summary

Diferentes tipos de “cortes”

Extensiones del algoritmo de Branch and Cut

Por ejemplo, el Problema del Vendedor Viajero, TSP, podría ser

resuelto considerando tres estrategias de generación de corte:
Algoritmo basado en Gomory Cuts estándar.

Algoritmo basado en agregación de “restricción de eliminación

de subtour más violada”.

Algoritmo basado en agregación de “restricción asociada al

subtour de mayor tamaño”.
Algoritmos Básicos para PE Summary

Diferentes tipos de “cortes”

Extensiones del algoritmo de Branch and Cut

Por ejemplo, el Problema del Vendedor Viajero, TSP, podría ser

resuelto considerando tres estrategias de generación de corte:
Algoritmo basado en Gomory Cuts estándar.

Algoritmo basado en agregación de “restricción de eliminación

de subtour más violada”.

Algoritmo basado en agregación de “restricción asociada al

subtour de mayor tamaño”.
Algoritmos Básicos para PE Summary

Diferentes tipos de “cortes”

Extensiones del algoritmo de Branch and Cut

Por ejemplo, el Problema del Vendedor Viajero, TSP, podría ser

resuelto considerando tres estrategias de generación de corte:
Algoritmo basado en Gomory Cuts estándar.

Algoritmo basado en agregación de “restricción de eliminación

de subtour más violada”.

Algoritmo basado en agregación de “restricción asociada al

subtour de mayor tamaño”.
Algoritmos Básicos para PE Summary

Diferentes tipos de “cortes”

Extensiones del algoritmo de Branch and Cut

Por ejemplo, el Problema del Vendedor Viajero, TSP, podría ser

resuelto considerando tres estrategias de generación de corte:
Algoritmo basado en Gomory Cuts estándar.

Algoritmo basado en agregación de “restricción de eliminación

de subtour más violada”.

Algoritmo basado en agregación de “restricción asociada al

subtour de mayor tamaño”.
Algoritmos Básicos para PE Summary

Estrategias de Planos de Corte para el TSP

Extensiones del algoritmo de Branch and Cut

Consideremos la siguiente formulación para el TSP

min ∑ ∑ cij xij (1)

i∈V j∈V
subject to (2)
∑ xij = 1 ∀j ∈ V (3)
i∈V

∑ xij = 1 ∀i ∈ V (4)
j∈V

∑ ∑ xij ≥ ∑ yi − ys s ∈ S, S ⊆ V (5)
i∈S j∈S i∈S
xij ∈ {0, 1} ∀i ∈ V , j ∈ V (6)
yi ∈ {0, 1} ∀i ∈ V (7)
(8)
Algoritmos Básicos para PE Summary

Estrategias de Planos de Corte para el TSP

Extensiones del algoritmo de Branch and Cut

En esta formulación existe un número exponencial de

restricciones del tipo (5).

Las estrategias eficientes de resolución consideran la

agregación sucesiva de restricciones de tipo (5), hay varios
criterios posibles, pero particularmente:
Agregar una restricción asociada al conjunto S que produzca el
máximo valor de ∑i ∈S ∑j ∈S xij − ∑i ∈S yi + ys .

O aquel que tenga el mayor número de elementos.

Algoritmos Básicos para PE Summary

Estrategias de Planos de Corte para el TSP

Extensiones del algoritmo de Branch and Cut

En esta formulación existe un número exponencial de

restricciones del tipo (5).

Las estrategias eficientes de resolución consideran la

agregación sucesiva de restricciones de tipo (5), hay varios
criterios posibles, pero particularmente:
Agregar una restricción asociada al conjunto S que produzca el
máximo valor de ∑i ∈S ∑j ∈S xij − ∑i ∈S yi + ys .

O aquel que tenga el mayor número de elementos.

Algoritmos Básicos para PE Summary

Estrategias de Planos de Corte para el TSP

Extensiones del algoritmo de Branch and Cut

En esta formulación existe un número exponencial de

restricciones del tipo (5).

Las estrategias eficientes de resolución consideran la

agregación sucesiva de restricciones de tipo (5), hay varios
criterios posibles, pero particularmente:
Agregar una restricción asociada al conjunto S que produzca el
máximo valor de ∑i ∈S ∑j ∈S xij − ∑i ∈S yi + ys .

O aquel que tenga el mayor número de elementos.

Algoritmos Básicos para PE Summary

Estrategias de Planos de Corte para el TSP

Extensiones del algoritmo de Branch and Cut

En esta formulación existe un número exponencial de

restricciones del tipo (5).

Las estrategias eficientes de resolución consideran la

agregación sucesiva de restricciones de tipo (5), hay varios
criterios posibles, pero particularmente:
Agregar una restricción asociada al conjunto S que produzca el
máximo valor de ∑i ∈S ∑j ∈S xij − ∑i ∈S yi + ys .

O aquel que tenga el mayor número de elementos.

Algoritmos Básicos para PE Summary

Summary

The first main message of your talk in one or two lines.

The second main message of your talk in one or two lines.
Perhaps a third message, but not more than that.

Outlook
What we have not done yet.
Even more stuff.
Appendix

For Further Reading I

A. Author.
Handbook of Everything.
Some Press, 1990.
S. Someone.
On this and that.
Journal on This and That. 2(1):50–100, 2000.