Técnico

Introducción a la programación lineal de números enteros mixtos (MILP)

January 10th, 2025

Ignacio Aristimuño

Tech Lead

Introducción

Hoy en día, cuando pensamos en resolver problemas complejos con ordenadores, inmediatamente pensamos en big data y aprendizaje automático. El desarrollo de una solución de aprendizaje automático suele requerir una cantidad intensiva de datos, que utilizamos para extraer los patrones y las reglas que subyacen al comportamiento de nuestros sistemas. Pero, ¿qué sucede cuando estos datos no son suficientes o, lo que es peor, no hay datos disponibles en absoluto? Si conocemos esas reglas de antemano, la programación lineal de enteros mixtos (MILP) podría ser la elección correcta. La MILP es una subárea del área más amplia llamada optimización convexa, y básicamente implica dos pasos: el modelado y la optimización. Modelar un problema es el arte de expresar un escenario del mundo real como un conjunto de ecuaciones y restricciones objetivas. El proceso de optimización en sí mismo está relacionado con la búsqueda de la mejor solución posible para el objetivo teniendo en cuenta las restricciones. A través del MILP se pueden expresar y resolver muchos de los problemas habituales de la industria. Maximizar el flujo de caja en la industria financiera, encontrar la ruta óptima para un problema de transporte y encontrar una asignación efectiva de recursos para una aplicación de fabricación, solo por nombrar algunos. En este blog, nos sumergimos en las aplicaciones prácticas de optimización. Empezamos proponiendo un problema de asignación de productos y modelándolo utilizando un marco MILP. Este ejemplo también nos permitirá explorar algunos detalles fundamentales de las técnicas del MILP y, finalmente, implementaremos el problema modelado en Python usando la biblioteca Pyomo.

Programación lineal de números enteros mixtos versus aprendizaje automático

Aunque podemos usar el aprendizaje automático (ML) y la programación lineal de enteros mixtos (MILP) para resolver algunos de los mismos problemas (a veces de forma complementaria), el enfoque es bastante diferente. El proceso típico de aprendizaje automático comienza con la recopilación y limpieza de enormes cantidades de datos, para luego entrenar un modelo que aprenda la distribución subyacente de los datos para explicar el mundo real. En el caso del MILP, necesitamos confiar en los expertos para diseñar un conjunto de reglas que expliquen el mundo real a través de las matemáticas. Al principio, parece que el aprendizaje automático es un enfoque superior, ya que puede aprender directamente de los datos. Sin embargo, cuando no tenemos suficientes datos, tenemos reglas comerciales claramente definidas o queremos poder influir y modificar el comportamiento de nuestro sistema de forma transparente, MILP brilla. Si comparamos el campo de la optimización con los avances más vanguardistas de la inteligencia artificial, se podría argumentar que la optimización parece algo anticuada. Desde finales de los 70, los matemáticos han estado desarrollando la teoría de la optimización, especialmente la teoría de la programación lineal de números enteros mixtos. Si bien estos métodos existen desde hace bastante tiempo, los avances recientes en los algoritmos de optimización y la potencia informática bruta han permitido resolver enormes problemas de optimización multivariante con miles (o quizás millones) de parámetros en cuestión de minutos.

¿Qué podemos resolver con MILP?

Hay una gran variedad de problemas que pueden abordarse con MILP, veamos ejemplos rápidos de algunos de ellos [1]: 💵 Optimización del flujo de caja se puede lograr eligiendo en qué instrumentos financieros invertir y durante cuánto tiempo de acuerdo con nuestro capital disponible para maximizar la rentabilidad o minimizar el riesgo. 🛒 Asignación de productos es el proceso de asignar una variedad de productos a diferentes estantes para maximizar los ingresos. En el ejemplo, asignaremos libros de diferentes tamaños y precios a las estanterías disponibles, teniendo en cuenta que algunas estanterías tienen más visibilidad que otras. 🏭 Asignación de recursos es el proceso de asignar estratégicamente los recursos disponibles a diferentes tareas. En la fabricación, resolveríamos cómo asignar los trabajadores y los materiales disponibles a nuestras diferentes líneas de producción para maximizar nuestras ganancias totales o minimizar el costo total. 🕰️ Programación es similar a la asignación de recursos, pero teniendo en cuenta la temporalidad. Dado un conjunto de recursos, los asignamos a las tareas en un tiempo determinado. Por ejemplo, si necesitamos asignar a los trabajadores por turnos, teniendo en cuenta su disponibilidad y habilidades, podemos calcular el mejor cronograma posible. 🛵 Planificación de rutas es lo que hacen todas las empresas de entrega de alimentos. Dado un origen y múltiples destinos, elige la mejor ruta según algunos criterios. Minimizar el consumo de combustible, minimizar los tiempos de entrega promedio o maximizar la cantidad de artículos entregados en un tiempo determinado. ✈️ Redes de transporte son una de las muchas aplicaciones de los flujos de red. Una empresa de transporte que tiene que entregar mercancías desde una ciudad de origen a una ciudad de destino, sin embargo, no hay vuelos directos entre esas ciudades. Hay ciudades intermedias que pueden conectar indirectamente el origen y el destino, pero los vuelos tienen diferentes límites en cuanto a la cantidad de mercancías que pueden transportar. Al modelar este problema, podemos maximizar la cantidad de bienes que llegan a destino desde su origen.

Conceptos básicos de MILP

En esta sección, nos centraremos en los fundamentos de la programación lineal de enteros mixtos. No vamos a entrar en muchos detalles matemáticos sobre la formulación, pero proporcionaremos un contexto general antes de pasar directamente a una aplicación. También definiremos algo de la jerga del MILP.

Planteamiento del problema

Imagina que tenemos un función objetiva llamada Y necesitamos optimizar, por ejemplo, el número total de productos en una asignación de productos. Tenemos un conjunto de parámetros que contienen información fija previa sobre el problema, como los precios de los productos, los tamaños, las dimensiones de los estantes y otros valores fijos. Necesitamos algo que podamos modificar para lograr lo óptimo de nuestra función objetivo. Para ello, tenemos variables de decisión, que representan cualquier variable libre que deba determinarse al resolver el problema y se indican con la letra x. Por ejemplo, las posiciones de cada uno de nuestros productos. Los valores posibles de las variables de decisión deben verificar un conjunto de condiciones lineales externas denominadas restricciones. Si tenemos M restricciones que dependen linealmente de las variables de decisión, podemos formular el problema de la siguiente manera [2]:

Resolver este problema implica encontrar un conjunto de valores x que maximiza (o minimiza) el resultado Y. Las limitaciones pueden ser igualdades o desigualdades y podríamos tener un número arbitrario de ellas. Como se mencionó anteriormente, este marco puede modelar una amplia variedad de problemas en diferentes industrias. El éxito en esta área depende de la capacidad de traducir escenarios del mundo real en conjuntos de ecuaciones. A continuación, aplicamos este marco a un problema de asignación de productos.

Programación no lineal

Esta formulación del MILP se puede extender a otras áreas dentro de la investigación de operaciones. Si algunas de las restricciones, o incluso la función objetivo, incluyen alguna falta de linealidad, aún es posible resolver el problema de optimización. Esto requiere la aplicación de un conjunto diferente de técnicas, conocidas como programación no lineal de enteros mixtos (MINLP). Sin embargo, también se pueden utilizar las técnicas MILP tradicionales para aproximar variables no lineales linealizándolas en el intervalo de interés. Esto conduciría lógicamente a soluciones aproximadas, pero en la mayoría de los casos, estas soluciones son lo suficientemente buenas para los problemas de aplicación.

La optimización en la práctica: asignación de productos

Una librería en línea quiere abrir su primera tienda física, y uno de los desafíos a los que se enfrenta es cómo colocar los libros en las estanterías para maximizar los ingresos. Para solucionarlo, decidieron ponerse en contacto con nosotros, expertos en optimización, para que les ayudáramos a solucionar su problema. Resumimos sus requisitos en la siguiente declaración: Tenemos que colocar tantos libros como podamos en las estanterías, colocar los libros más populares en las estanterías más visibles y mantener a los mismos autores juntos. Como se mencionó en la sección anterior, necesitamos identificar los parámetros, las variables, las restricciones y la función objetivo, de modo que podamos encontrar la solución óptima. Es una práctica común definir verbalmente estos componentes de la solución para luego formularlos matemáticamente. Parámetros: Para cada libro, necesitamos una medida de su popularidad, precio, autor y dimensiones. A su vez, para cada estante de las estanterías, necesitamos saber las dimensiones y la visibilidad o exposición que proporcionan a los libros. Variables: Para cada libro, necesitamos saber en qué estante y en qué lugar de ese estante debe estar ubicado. Restricciones: Solo debemos incluir una copia de cada libro y deben caber en la estantería por altura. La longitud total de los libros seleccionados en una estantería debe coincidir con el ancho de la estantería. Además, los libros del mismo autor deben estar en la misma estantería. Función objetiva: Los ingresos de cada libro se definen por el precio del libro, su popularidad y la visibilidad que proporciona su ubicación. Nuestro objetivo es maximizar los ingresos totales, como la suma de los ingresos de todos los libros asignados.

Conjuntos

En primer lugar, definimos el conjunto de índices que utilizaremos para definir nuestro problema. Como tendremos muchas variables y parámetros que se repiten para cada libro, librería y autor, los índices facilitan mucho la notación.

El conjunto B representa el conjunto de libros considerados para el problema. Cada libro individual se referirá con el subíndice b.
El conjunto C representa el conjunto de estanterías consideradas para el problema. Cada estantería individual se referirá con el subíndice c.
El conjunto UN representa el conjunto de autores considerados para el problema. Cada autor individual será referido con el subíndice un.
El conjunto S representa el conjunto de estantes considerado para el problema. Cada estante individual se referirá con el subíndice s.

Parámetros

Luego definimos los parámetros del problema, que representan la información y las configuraciones anteriores, es decir, valores que no podemos modificar en nuestro proceso de optimización:

Libros

Definimos el parámetro b_pop_b como la popularidad del libro b.
Definimos el parámetro b_width_p como el ancho en mm para el libro b.
Definimos el parámetro b_height_b como la altura en mm del libro b.
Definimos el parámetro b_precio_b como precio en USD por libro b.
Definimos el parámetro booleano es_autor_{a, b}lo cual es cierto si el libro b fue escrito por el autor un y falso si no.

estanterías

Definimos el parámetro s_width_{c, s} como el ancho en mm para estante s de bookcase c.
Definimos el parámetro s_height_{c, s} como la altura en mm del estante s de bookcase c.
Definimos los parámetros s_visibilidad_c_{, s} como la visibilidad que gana un libro al colocarlo en una estantería b de bookcase c.

Variables de decisión

A continuación, debemos identificar las variables de decisión cuyos valores se deben encontrar en el proceso de optimización. Estas variables representan todos los valores que podemos modificar como profesionales:

Definimos la variable booleana Es_Book_At_{b, c, s} que representa si libro b está en el estante s de estantería c.
Definimos la variable booleana Es_Autor_En_{a, c, s} que representa si el autor un está en el estante s de estantería c.

Restricciones

Ahora, una vez definidas las variables de decisión, necesitamos definir matemáticamente todas las restricciones del problema. Nuestra primera restricción está relacionada con la limitación del número de veces que podemos asignar un libro.

De esta manera, nos aseguramos de que cada libro se asigne como máximo una vez, lo que también permite que la modelo omita libros si no caben. Hay dos restricciones que tienen que ver con el tamaño de las estanterías:

Para limitar el número de estanterías en las que aparece un autor, necesitamos rellenar la variable accesoria Es_Autor_En_{a, c, s}. Esto se puede hacer mediante la combinación de dos restricciones.

Luego debemos asegurarnos de que cada autor aparezca como máximo en una estantería:

Función objetiva

Por último, necesitamos definir la función objetivo que estamos intentando maximizar. En este caso, los ingresos esperados de una venta específica de libros:

Después de formular el problema, resolverlo pasa a ser cuestión de utilizar solucionadores de programación lineal estándar. Hay muchos solucionadores de código abierto como GLPK de GNU, GLOP, y CP-SAT desarrollado por Google y muchos más.

Optimización de la asignación de productos con Pyomo

Ahora que el problema está completamente definido, es el momento de implementarlo usando Piomón [3], una biblioteca de código abierto basada en Python que admite un conjunto diverso de capacidades de optimización para resolver modelos de optimización. Si bien la utilizaremos para resolver un problema lineal, también tiene capacidades no lineales para resolver problemas más complejos. ¡Ahora es el momento de empezar a llenar nuestras estanterías!

Conjunto de datos

Para resolver nuestro problema, necesitamos datos de libros. Trabajaremos con un conjunto de datos de libros de fantasía (inspirados en esto). conjunto de datos). Incluye características del libro, como las dimensiones, la información del autor y las ventas promedio. La popularidad de un libro se puede deducir por el promedio de ventas. Luego necesitamos medir nuestras estanterías imaginarias para definir el espacio disponible para los libros. Para este ejemplo, trabajaremos con 3 estanterías, de 5 estantes cada una, con 1 metro de ancho y lo suficientemente altas como para almacenar las más altas. Cada estantería también tiene su propio factor de visibilidad, que multiplica las ventas de libros a medida que los colocamos en esta estantería. Echemos un vistazo a los datos con los que alimentaremos el modelo.