branch and bound Archivos - Gestión de Operaciones

Qué es la Programación Entera

¿Qué es la Programación Entera?: Un modelo de Programación Entera es aquel cuya solución óptima tiene sentido solamente si una parte o todas las variables de decisión toman valores restringidos a números enteros, permitiendo incorporar en el modelamiento matemático algunos aspectos que quedan fuera del alcance de los modelos de Programación Lineal.

En este sentido los algoritmos de resolución de los modelos de Programación Entera difieren a los utilizados en los modelos de Programación Lineal, destacándose entre ellos el Algoritmo de Ramificación y Acotamiento (o Branch & Bound), Branch & Cut, Planos Cortantes, Relajación Lagrangeana, entre otros.

Los modelos de Programación Entera se pueden clasificar en 2 grandes áreas: Programación Entera Mixta (PEM) y Programación Entera Pura (PEP).

Programación Entera Mixta (PEM)

A esta categoría pertenecen aquellos problemas de optimización que consideran variables de decisión enteras o binarias pero no de forma exclusiva. De esta forma un problema de PEM puede considerarse como un híbrido entre distintas categorías de modelamiento, siendo un caso típico aquel que considera la mezcla de variables enteras y variables continuas (estas últimas características de los modelos de Programación Lineal). A modo de ejemplo los siguientes artículos que hemos abordado en el Blog dan cuenta de modelos de Programación Entera Mixta:

Programación Entera Pura (PEP)

En esta categoría encontramos aquellos modelos de Programación Entera que consideran exclusivamente variables de decisión que adoptan valores enteros o binarios. Un ejemplo de ello son las siguientes aplicaciones:

Problema de Asignación
Problema de Corte de Rollos
Selección de Invitados a una Boda
Programación de la Explotación Forestal
Problema de la Mochila

Notar que en los problemas anteriores (PEP) el conjunto de las soluciones factibles (o dominio de soluciones factibles) es finito. Esto ocurrirá generalmente con los problemas de Programación Entera (puros).

Adicionalmente resulta interesante hacer un contrastes entre las propiedades de un modelo de Programación Lineal (PL) y uno de Programación Entera (PE). A continuación se presentan 2 modelos de optimización que se diferencian únicamente en que al segundo de ellos (PE) se le exige que las variables de decisión adopten valores enteros.

Para los problemas propuestos realizamos una representación gráfica haciendo uso del software Geogebra. El dominio de soluciones factibles del Problema Lineal (PL) corresponde al área achurada de color verde. Por otro lado el dominio de soluciones factibles del Problema Entero (PE) es enumerable y corresponde a las coordenadas denotadas por A, E, F, B, G, H, I, J, K, C, L, M, D (que es un subconjunto del dominio de factibilidad del PL). En este caso en particular la solución óptima de ambos problemas coincide (en el vértice C), no obstante, perfectamente podrían ser distintas (bastaría con modificar los parámetros del problema).

En este contexto y dada la naturaleza de los problemas propuestos, el valor óptimo del Problema Lineal (PL) será una cota superior del valor óptimo del Problema Entero (PE). También se concluye que el dominio de soluciones factibles de un modelo de Programación Lineal (cuando existe) representa un conjunto convexo (los problemas de Programación Lineal son convexos) y en el caso del problema de Programación Entera Pura su conjunto de soluciones factibles es discreto.

Adicionalmente según tratamos en el artículo Por qué no aparece el Informe de Confidencialidad (o Informe de Sensibilidad) en Solver de Excel se debe tener en cuenta que en la utilización de software para la resolución computacional del modelos de Programación Entera no tendremos acceso a los reportes de sensibilidad como en el caso de la implementación de modelos de Programación Lineal. De esta forma ante la necesidad de analizar el impacto en los resultados ante la modificación de los parámetros del problema será necesario reoptimizar ante la información que brinde el o los nuevos escenarios.

Es importante destacar que las aplicaciones de la Programación Entera no reemplaza la versatilidad que ofrece el disponer de modelos de Programación Lineal. Más aún, se pueden considerar estas categorías de modelamiento matemático como complementarias en el ámbito de la Investigación de Operaciones.

En este sentido en términos abstractos los modelos de Programación Entera imponen un desafío mayor al momento de la resolución en comparación a las propiedades simplificadoras que están asociadas a los problemas de Programación Lineal. De esta forma se espera que el tomador de decisiones sea capaz de evaluar la relación rigurosidad del modelado con el costo (complejidad) de la resolución del mismo.

Solución del Problema del Vendedor Viajero

El Problema del Vendedor Viajero (conocido también como Travelling Salesman Problem o simplemente TSP) consiste en encontrar el circuito óptimo (en términos del viaje más corto) que deberá seguir un vendedor en un caso con n ciudades, en el que cada ciudad se visita exactamente una vez. Básicamente es una adaptación del Problema de Asignación que considera restricciones adicionales que garantiza la exclusión de subcircuitos en la solución óptima.

Específicamente en el caso de n ciudades se define las variables de decisión de la siguiente forma:

Sea $d_{ij}$ la distancia de la ciudad i a la ciudad j, donde $d_{ij}=\infty$ , el modelo del agente o vendedor viajero corresponde a:

El conjunto de restricciones (1) y (2) definen un modelo de asignación tradicional. Lamentablemente en general, el problema de asignación producirá soluciones de subcircuito más que circuitos completos que abarque las n ciudades.

Para ilustrar los conceptos de circuito y subcircuito en el contexto del Problema del Vendedor Viajero, consideremos un agente de venta que vive en la ciudad 1. Miami (Florida) en Estados Unidos y debe visitar a importantes clientes en las siguientes ciudades: 2. Chicago (Illinois), 3. Houston (Texas), 4. Las Vegas (Nevada) y 5. San Francisco (California). Para mayor claridad se han destacado los estados mencionados anteriormente con un color distintivo.

Un circuito factible sería viajar en el siguiente orden: Miami (FL), Chicago (IL), Houston (TX), Las Vegas (NV), San Francisco (CA), Miami (FL). Es decir, $x_{12}=x_{23}=x_{34}=x_{45}=x_{51}=1$ .

Por otra parte un subcircuito correspondería, por ejemplo, a Miami (FL), San Francisco (CA), Las Vegas (NV), Miami (FL), junto a Houston (TX), Chicago (IL), Houston (TX). Es decir, $x_{15}=x_{54}=x_{41}=x_{32}=x_{23}=1$ , lo que naturalmente no es una solución factible para el problema que se busca resolver.

El modelo del vendedor viajero se caracteriza por su versatilidad para representar otros casos prácticos en optimización. Uno de ellos es el Problema de Secuenciamiento de la Producción como el que se presenta a continuación:

El programa de producción diaria de una empresa de pinturas incluye lotes de color Blanco (B), Amarillo (A), Negro (N) y Rojo (R). Como la empresa utiliza las mismas instalaciones en las cuatro clases de pintura, es necesario hacer una limpieza entre los lotes. La siguiente tabla resume el tiempo de limpieza, en minutos, donde al color de la fila sigue el color de la columna. Por ejemplo, cuando después de la pintura Blanca sigue la Amarilla, el tiempo de limpieza en 10 minutos. Como un color no puede seguir a sí mismo, a los elementos correspondientes se les asigna un tiempo de setup infinito. Se desea determinar la secuencia óptima para la producción diaria de los cuatro colores, que minimice el tiempo total de limpieza necesario.

Se puede hacer una analogía con el problema del vendedor viajero, asumiendo que cada pintura es una «ciudad» y que las «distancias» representan el tiempo de limpieza necesario para cambiar de un lote de pintura al siguiente. En consecuencia, el problema se reduce a determinar el circuito más corto que se inicie en un lote de pintura y pase exactamente una vez por cada uno de los tres lotes restantes, para regresar al punto de partida.

En este contexto dada la cantidad de pinturas, la secuencia óptima se puede encontrar por enumeración exhaustiva de los 6 circuitos posibles $(n-1)!$ , es decir, $(4-1)!=3!=6$ . En el ejemplo dicha secuencia óptima corresponde a Blanco, Amarillo, Rojo, Negro, Blanco, con un tiempo total de setup de 98 minutos. Naturalmente esta estrategia no es eficiente y queda limitada a problemas muy pequeños.

Alternativamente se puede utilizar implementar en Solver el modelo de asignación presentado anteriormente, haciendo uso de los parámetros descritos en el ejemplo del secuenciamiento de la producción de pinturas. A continuación un extracto de los resultados donde se observa que no se alcanza una solución de circuito.

En la actualidad existen programas computacionales que permiten enfrentar estas dificultades que establece el problema del vendedor viajero. Uno de ellos es el software TSPSG (TSP Solver and Generator) que se caracteriza por una interfaz intuitiva y que a continuación se detalla la implementación de nuestro problema (recordar que la Ciudad 1 correspondería al color Blanco, y así sucesivamente).

Una vez ingresado los datos al seleccionar «Solve» el programa se ejecuta entregando los resultados alcanzados que por cierto coincide con aquellos que identificamos por enumeración.

En términos algorítmicos los métodos disponibles para resolver el problema del agente o vendedor viajero tienen su base en las ideas de los algoritmos generales de ramificación y acotamiento (Branch and Bound) o de Plano de Corte, en los cuales abordaremos en próximos artículos.

Problema de Corte Ensamblado y Producción de Sillas resuelto con Solver

Una empresa de Rústicos “El Viejo Baúl” fabrica entre muchos otros productos tres tipos de sillas A, B y C, las cuales se venden a precio de 11, 13 y 12 dólares cada una y respectivamente. Las sillas pasan por tres procesos, Corte, Ensamblado y Pintado, para lo cual se dispone máximo de 17, 13 y 15 horas respectivamente a la semana para dedicar a estas operaciones a estos productos. La silla tipo A requiere 3 horas para corte, 1 hora para ensamblado y 3 horas para pintura. La silla tipo B requiere 1 hora para corte, 4 horas para ensamblado y 3 horas para pintura. Y finalmente la silla tipo C, requiere de 5 horas para corte, 2 para ensamblado y 2 horas para pintura. De acuerdo a la anterior información:

a. Resuelva el problema con variables continuas y señale los resultados para cada variable.

Variables de Decisión: Se estable el nivel de producción semanal para cada una de las variedades de silla según se detalla a continuación:

Función Objetivo: Maximizar los ingresos semanales asociados a la producción y venta de las sillas.

Restricciones: En los procesos de corte, ensamblado y pintura se debe respetar la disponibilidad de horas semanales. Adicionalmente se deben satisfacer las condiciones de no negatividad.

La implementación computacional del problema anterior con Solver de Excel permite alcanzar los siguientes resultados:

Donde la solución óptima es A=1,914286, B=1,828571 y C=1,885714 con valor óptimo V(P)=67,45714.

b. Modifique las condiciones de las variables y elíjalas enteras (integer) y observe el cambio entre la respuesta del punto a y esta nueva hallada.

Al definir las variables de decisión enteras estamos frente a un modelo de Programación Entera (siendo el escenario inicial un problema de Programación Lineal). Los resultados son:

La solución óptima es A=1, B=2 y C=2 con valor óptimo V(PE)=61.

c. Concluya qué sucedió entre variables continuas y variables enteras.

Es importante observar que el dominio de soluciones factibles del problema entero (parte b) es un subconjunto del dominio de soluciones factibles del problema lineal (parte a). Por tanto es natural que al no obtener una solución con valores enteros para las variables de decisión en el problema inicial, el valor óptimo necesariamente disminuirá en la variante entera de dicho problema de maximización (V(PE)<V(P)). También se puede destacar que la solución entera no necesariamente se alcanza al aproximar los resultados fraccionarios de una solución de un problema lineal al entero inferior o superior más cercano. En consecuencia, para abordar de forma eficiente la resolución de un modelo que considere valores enteros para las variables de decisión requiere de una alternativa algorítmica específica como por ejemplo el Método Branch and Bound.

A continuación encontrarás un enlace de descarga del archivo Excel utilizado para la resolución del problema de corte, ensamblado y producción de sillas. En el archivo se incluyen 2 hojas que corresponden a la parte a) y b) del problema propuesto. Produccion de Sillas.

Ejemplo del Algoritmo de Branch and Bound (Ramificación y Acotamiento)

El método de Branch and Bound (o Ramificación y Acotamiento) es un algoritmo diseñado para la resolución de modelos de Programación Entera. Su operatoria consiste en linealizar el modelo de Programación Entera, es decir, resolver éste como si fuese un modelo de Programación Lineal y luego generar cotas en caso que al menos una variable de decisión (entera) adopte un valor fraccionario.

El algoritmo genera en forma recursiva cotas (o restricciones adicionales) que favorecen la obtención de valores enteros para las variables de decisión. En este contexto resolver el modelo lineal asociado a un modelo de Programación Entera se conoce frecuentemente como resolver la relajación continua del modelo entero.

Ejemplo Branch & Bound (Ramificación y Acotamiento)

Consideremos el siguiente modelo de Programación Entera el cual resolveremos con el algoritmo de Branch and Bound:

El paso inicial consiste en resolver este problema como si fuese un modelo de Programación Lineal (relajación continua). Si la solución de dicho problema llegara a respetar las condiciones de integralidad para las variables de decisión, ésta ya sería la solución óptima del problema entero.

Si bien este procedimiento se puede extender a problemas de mayor dimensión, utilizamos un modelo en 2 variables para poder representar los pasos del algoritmo gráficamente. El gráfico a continuación muestra dicha resolución:

La solución óptima del problema lineal asociado (que llamaremos P0) es X1=2,8 y X2=1,6 con valor óptimo V(P0)=20,8. Claramente esta solución no cumple las condiciones de integralidad para las variables de decisión por tanto es necesario generar cotas o restricciones adicionales de modo de poder obtener soluciones enteras. Para ello debemos seleccionar una de las 2 variables de decisión con valores fraccionarios para poder generar cotas. En estricto rigor es indistinto cuál de ellas seleccionemos debido a que el método nos debe llevar a conclusiones similares (aun cuando la cantidad de pasos requeridos o rapidez de convergencia cambie).

En nuestro ejemplo generaremos cotas adicionales para la variable X1 aproximando su valor actual al entero inferior más cercano (P1) y entero superior más cercano (P2).

La resolución gráfica del problema 1 (P1) nos da como solución óptima X1=2 y X2=2 que es una solución entera. El valor óptimo del problema 1 es V(P1)=20. Notar que V(P1)<V(P0) lo cual es natural dado que el dominio de soluciones factibles del P1 es menor (subconjunto) al dominio de soluciones factibles de P0.

Análogamente la resolución gráfica (Método Gráfico) del problema 2 (P2) determina que X1=3 y X2=4/3 con V(P2)=20 según se observa a continuación:

Luego no sería del todo necesario seguir desarrollando el algoritmo dado que si generamos cotas para la variable X2 del P2 en ningún caso podríamos obtener una solución entera con valor óptimo superior a 20 (valor que reporta en la función objetivo la actual solución entera de P1) y por tanto podríamos concluir que X1=2 y X2=2 es la solución óptima del problema entero. No obstante el siguiente diagrama muestra los pasos adicionales en caso que quisiera agregar cotas adicionales a partir del P2.

Un argumento similar al expuesto previamente en este caso explicaría la no necesidad de seguir ramificando el P21. Se propone al lector verificar que se obtiene la misma solución óptima si luego del P0 ramificamos a través de X2 agregando las restricciones X2<=1 y X2>=2.

Problema de la Dieta con variables enteras resuelto con Solver de Excel

En un artículo previo tratamos el Problema de la Dieta como una aplicación característica de la Programación Lineal discutido ampliamente en los Cursos de Investigación de Operaciones. El problema consiste básicamente en encontrar una combinación de alimentos óptima que permita satisfacer ciertos requerimientos nutricionales mínimos y adicionalmente tenga el menor costo asociado a la selección de los mismos.

Una vez obtenida la solución óptima y valor óptimo de dicho modelo nos podemos enfrentar al escenario donde todas o algunas de las variables de decisión adoptan valores fraccionarios. Si bien esta situación es aceptada en los modelos de Programación Lineal (en efecto constituye un supuesto básico de la Programación Lineal), puede resultar de interés simular una nueva solución donde las variables de decisión adopten valores enteros.

El siguiente tutorial muestra cómo incorporar las condiciones de integralidad al Problema de la Dieta, lo que da origen a un modelo de Programación Entera.

Se puede observar que hemos utilizado un formato similar al modelo de Programación Lineal, sin embargo, se incorpora la condición de integralidad para las variables de decisión como si fuese una restricción adicional. Adicionalmente en las Opciones de Solver debemos desactivar la selección de «Adoptar modelo lineal» debido a que ahora el modelo es de Programación Entera (esta indicación es válida para las versiones de Office 2007 y anteriores).

La tabla a continuación resume los resultados del Problema de la Dieta resuelto como un modelo de optimización lineal o entero:

Se puede observar que el valor óptimo del Problema Entero es superior al del Problema Lineal. Siendo éste un problema de minimización esta situación es natural dado que el dominio de soluciones factibles del problema entero está contenido en el dominio del problema lineal (es un subconjunto) y por tanto no podríamos encontrar nada mejor (más económico en este caso) que el valor óptimo del problema lineal.

Es importante destacar adicionalmente que para obtener la solución óptima de un problema entero NO es suficiente con aproximar los resultados fraccionarios del problema lineal asociado, por ejemplo, al entero superior o entero inferior más cercano. En consecuencia se requiere de algoritmos específicos para la resolución de modelos de Programación Entera, siendo el Algoritmo de Ramificación y Acotamiento (Branch & Bound) uno de los más populares.