Branch and Bound – Introducción antes de codificar el algoritmo desde cero

Branch and Bound - Introducción al algoritmo desde cero

Una Introducción a los Problemas de Enteros y Una de las Formas de Resolverlos

Introducción

La programación entera (IP) es un caso especial de la programación lineal (LP) donde las variables de decisión están restringidas a valores enteros. Es decir, valores como 2.5 o 4.2 no son soluciones posibles para estos problemas.

Este requisito se trata como una restricción adicional a la LP y, a su vez, hace que el proceso de encontrar el óptimo sea más desafiante.

En la vida real, muchos de los problemas que tenemos toman la forma de IP. Por ejemplo, la asignación y presupuesto de capital, donde decidimos qué inversiones hacer, requieren que las variables de decisión sean binarias y tomen solo los valores de 0 y 1. Problemas de selección de sitios en bienes raíces, rutas de vehículos e incluso problemas de programación también caerían en esta categoría.

En este artículo, exploraremos uno de los algoritmos utilizados para resolver problemas de enteros (IP), llamado algoritmo de Branch and Bound.

• Lo más difícil de Pandas pivot_table, stack y unstack claramente explicados
• Robot Blando Camina al Inflarse Repetidamente
• Utilizando Psicología para Fortalecer la Ciberseguridad

Tomaré prestados los ejemplos del libro “Optimization Methods in Finance” de Cornuejols y Tütüncü, pero agregaré mis propias explicaciones intuitivas y, por supuesto, la implementación en Python de dichos algoritmos.

Algoritmo de Branch and Bound

El algoritmo de Branch and Bound es uno de los métodos más populares para resolver un IP. El algoritmo divide el problema principal o original en subproblemas más pequeños (branching), y al hacerlo, puede probar algunas de estas soluciones y posteriormente eliminar algunos de estos subconjuntos de soluciones (bounding / pruning), cuando estos no contribuyan a un resultado mejor que el que tenemos actualmente / inicialmente.

Esto puede ser mucho para asimilar, pero sería más fácil con un ejemplo.

Problema 0 de arriba es nuestro problema entero original. Observa que es un problema simple de programación lineal con una restricción adicional en la última fila.

Paso 1 — Relajación de la Programación Lineal

We will continue to update Zepes; if you have any questions or suggestions, please contact us!