Investigadores descubren una forma de procesar la programación lineal entera más rápido
(quantamagazine.org)- En problemas de optimización que requieren decisiones en unidades enteras, como planificación de producción, asignación de tripulación y rutas de vehículos, Victor Reis y Thomas Rothvoss presentaron un nuevo algoritmo que reduce de forma importante el tiempo de ejecución de ILP
- Como ILP es más difícil que la programación lineal general y casi no había habido mejoras récord desde la década de 1980, este resultado se considera un gran avance tras décadas
- El nuevo enfoque combina herramientas geométricas para tratar la intersección entre retículas y cuerpos convexos, acotando con más fuerza el rango de soluciones enteras posibles
- La clave está en aprovechar un resultado de 2016 sobre puntos de retícula para reducir la cota superior del covering radius, y el tiempo de ejecución baja hasta el orden de ((\log n)^{O(n)})
- Aunque todavía no se ha aplicado directamente a sistemas logísticos reales, el resultado se acerca mucho al límite teórico de velocidad de ILP y muestra una dirección de largo plazo para mejorar los solucionadores prácticos
Por qué las restricciones enteras dificultan la optimización
- El problema del viajante es un antiguo problema computacional que busca la ruta más corta entre varias ciudades, y revisar todas las rutas posibles se vuelve inmanejable incluso con un pequeño aumento en la cantidad de ciudades
- La programación lineal es un modelo matemático que trata de forma sistemática las combinaciones posibles mediante ecuaciones y desigualdades
- En los problemas de optimización del mundo real, muchas veces una respuesta decimal no sirve
- En un plan óptimo de producción para una fábrica, una respuesta que diga producir 500.7 sofás es difícil de usar como decisión real
- La programación lineal entera (ILP) es una variante de la programación lineal con este tipo de restricciones enteras, y se usa ampliamente en problemas de decisiones discretas como planificación de producción, horarios de tripulación aérea y ruteo de vehículos
- Santosh Vempala considera ILP una herramienta clave en investigación de operaciones tanto teórica como práctica
Límites de velocidad que mejoraron lentamente desde los años 80
- Desde que ILP fue formulada formalmente hace unos 60 años, han aparecido varios algoritmos, pero seguía siendo lenta en términos de la cantidad de pasos necesarios
- El punto de referencia más simple es el caso de variables binarias, donde cada variable solo puede valer 0 o 1
- Una variable tiene 2 combinaciones posibles
- Dos variables tienen 4
- Tres variables tienen 8
- En general, el tiempo de ejecución crece de forma exponencial con la cantidad de variables, es decir, con la dimensión
- Si las variables pueden tomar valores enteros más amplios que solo 0 y 1, el tiempo de ejecución se vuelve mucho mayor
- Durante mucho tiempo, los investigadores han explorado si es posible acercar la velocidad de la ILP general a la de este caso binario más simple
- Después de los récords de los años 80, solo hubo mejoras graduales
La interpretación geométrica que abrió Lenstra
- En 1983, Hendrik Lenstra demostró que el problema general de ILP podía resolverse y presentó el primer algoritmo para hacerlo
- Lenstra abordó ILP convirtiéndolo en un problema geométrico
- Las desigualdades de ILP se representan como una figura convexa, es decir, un cuerpo convexo (convex body)
- El interior de la figura corresponde a todos los valores posibles que pueden satisfacer las desigualdades
- Un problema con 2 variables se vuelve un polígono plano, y uno con 3 variables un sólido tridimensional, aumentando así la dimensión
- Todos los enteros pueden verse matemáticamente como puntos de una retícula (lattice)
- En 2 dimensiones parece un mar de puntos
- En 3 dimensiones se convierte en una estructura como las uniones del armazón de acero de un edificio
- Al final, resolver ILP equivale a encontrar la intersección entre el cuerpo convexo y la retícula, es decir, dónde las soluciones posibles coinciden con puntos enteros
- El algoritmo de Lenstra podía explorar este espacio, pero para ganar eficiencia a veces tenía que dividir el problema en partes de menor dimensión, y ese proceso aumentaba el tiempo de ejecución
El covering radius, cuello de botella durante 30 años
- En 1988, Ravi Kannan y László Lovász intentaron tratar de manera más eficiente la intersección entre cuerpos convexos y retículas usando el concepto de covering radius, tomado de la investigación sobre códigos de corrección de errores
- El covering radius está relacionado con el tamaño que garantiza que, sin importar dónde se coloque un cuerpo convexo sobre la retícula, contenga al menos un punto entero
- La magnitud de este valor determina qué tan eficientemente puede resolverse un problema de ILP
- Encontrar el tamaño ideal del covering radius era en sí mismo un problema difícil
- Kannan y Lovász acotaron los valores posibles con cotas superior e inferior, y mostraron que la cota superior crecía linealmente con la dimensión
- Aun así, ese resultado no bastó para reducir de forma drástica el tiempo de ejecución de ILP, y durante los 30 años siguientes las mejoras fueron limitadas
El nuevo algoritmo de Reis y Rothvoss
- Victor Reis y Thomas Rothvoss lograron el avance aprovechando un resultado matemático independiente centrado en retículas
- En 2016, Oded Regev y Noah Stephens-Davidowitz mostraron cuántos puntos de retícula pueden caber dentro de cierta figura
- Reis y Rothvoss aplicaron ese resultado a otras figuras para estimar mejor cuántos puntos de retícula quedan contenidos dentro del covering radius de ILP
- Con esta estimación, la cota superior bajó y el tiempo total de ejecución del algoritmo de ILP se redujo de forma importante
- El nuevo tiempo de ejecución es ((\log n)^{O(n)}), donde (n) es el número de variables y (O(n)) es proporcional linealmente a (n)
- Esta expresión se considera “casi” del mismo nivel que el tiempo de ejecución del problema con variables binarias
La distancia entre el logro teórico y la aplicación práctica
- Noah Stephens-Davidowitz considera este nuevo algoritmo la primera gran mejora de un solucionador de ILP en casi 40 años
- Daniel Dadush valora el resultado como un logro surgido en la intersección entre matemáticas, ciencias de la computación y geometría
- El nuevo algoritmo todavía no se ha usado para resolver problemas logísticos reales
- Actualizar los programas actuales para adaptarlos a este enfoque requeriría mucho trabajo
- Rothvoss considera que el foco de este resultado está en la comprensión teórica de un problema con aplicaciones fundamentales
- Aunque todavía existe la posibilidad de mejorar más la eficiencia computacional de ILP, Vempala cree que harían falta ideas fundamentalmente nuevas para acercarse más al tiempo de ejecución ideal
1 comentarios
Opiniones en Hacker News
Siempre es muy interesante bajar la cota superior algorítmica de un problema clave NP-completo, pero eso no necesariamente significa que el problema se resuelva más rápido en implementaciones reales.
Los solvers de programación entera mixta (MIP) usan muchos algoritmos junto con una gran cantidad de heurísticas, y la acumulación de bibliotecas de heurísticas y estrategias ha sido una razón central por la que las mejoras de los solvers MIP han superado la ley de Moore.
Según https://www.math.uwaterloo.ca/~hwolkowi/henry/teaching/f16/6..., entre 1990 y 2014 las mejoras de hardware fueron de 6500 veces, mientras que las mejoras de software contribuyeron a un aumento de rendimiento de 870000 veces.
Este artículo también podría ser una pieza del rompecabezas para seguir mejorando el rendimiento de los solvers MIP, pero no está garantizado que lo sea.
No termino de entender la explicación de que el nuevo algoritmo aún no se use para resolver problemas de logística porque “actualizar los programas actuales requiere demasiado trabajo”.
La mayoría de los modelos específicos de dominio llaman a solvers como Gurobi, CPLEX y FICO para problemas grandes, y usan solvers open source como SCIP para problemas pequeños.
Se pueden intercambiar modelos entre estos solvers en el formato MPS estándar; la formulación del problema no cambia y solo tendría que cambiar el método de resolución interno del solver, ¿no?
Si lo que quieren decir es que hace falta una nueva implementación, el beneficio para el mundo al implementarla también parece enorme.
Estas herramientas son productos de ingeniería muy complejos, construidos sobre décadas de mejoras incrementales, así que probablemente haría falta bastante esfuerzo de investigación solo para descubrir cómo integrar el nuevo hallazgo en esos motores.
Es cierto que existen formas estándar de intercambiar la formulación del problema mediante formatos como MPS, y hoy en día parece que se usan más los lenguajes de modelado algebraico como AMPL, pero esos formatos solo proporcionan una formulación matemática estándar.
La resolución real está muy especializada en cada solver, con sus propias estructuras de datos, algoritmos y técnicas heurísticas.
No son intercambiables entre sí, tampoco están publicados deliberadamente, y no se pueden insertar algunos números externos en medio sin conocer el código del solver y todo el proceso.
Quería aclarar el malentendido.
En la medida de lo posible, uno evita implementar cosas directamente sobre eso.
Aun así, no deja de ser un resultado excelente.
Desde la perspectiva de la complejidad computacional teórica, los mejores algoritmos para “programación lineal entera” [2] se basan en retículas y tienen la mejor complejidad Big O en el peor caso.
Pero las implementaciones actuales por lo general (1) requieren aritmética racional de tamaño arbitrario, como gmplib [3], lo que consume mucha memoria y en la práctica también es lento, y (2) necesitan un paso de reducción de retículas tipo LLL [4], pero no pueden aprovechar la dispersión de las matrices.
Como resultado, estos algoritmos normalmente ni siquiera caben en memoria, por lo que no pueden empezar con problemas de matrices mayores que 1000x1000, y aunque cupieran serían demasiado lentos.
En cambio, los solvers de programación entera usados en la práctica se basan en branch and bound, un algoritmo de backtracking similar a los usados en resolución SAT, y en cada iteración resuelven un problema de “programación lineal” obtenido al convertir todas las variables del problema original en variables continuas.
Cada problema de programación lineal puede resolverse con algoritmos de tiempo polinomial como los métodos de punto interior, pero en la práctica se usa el método símplex, que en el peor caso tiene tiempo exponencial.
La razón es que los problemas de programación lineal que hay que resolver son muy parecidos entre sí, y el método símplex aprovecha muy bien eso en la práctica.
Además, los algoritmos relacionados aprovechan en gran medida la dispersión de vectores y matrices.
Por eso algunas personas logran resolver problemas de programación entera con millones de variables en cuestión de días, o incluso de horas.
Quienes implementan solvers no persiguen la mejor complejidad teórica absoluta, y puede decirse que la teoría y la práctica de la optimización discreta se han separado hasta cierto punto.
Aun así, el artículo de Reis & Rothvoss [1] es un trabajo matemático profundo y, para cualquiera interesado en matemática discreta, es muy impresionante por sí mismo.
Resolvió una conjetura de Dadush de hace 10 años y fue presentado en noviembre del año pasado en FOCS, una de las dos principales conferencias de teoría de la informática.
La utilidad práctica directa no es el punto central, y los autores probablemente lo reconocerían en ámbitos informales.
Claro que en las solicitudes de financiamiento dirán otra cosa, pero eso es parte del juego.
Eso no significa que sea inútil; avanzar el conocimiento matemático ya tiene mucho valor por sí mismo, y quizá dentro de algunas generaciones otros investigadores construyan algoritmos prácticos a partir de estas ideas y empujen el estado del arte de los solvers.
Al final, todos estos algoritmos tienen tiempo exponencial en el peor caso.
En teoría se intenta reducir un poco el polinomio que aparece en el exponente de la complejidad del peor caso, pero en la práctica normalmente no se quiere resolver una familia de problemas donde crece el tamaño n, sino un único problema grande de optimización.
Más que la tasa de crecimiento de la línea de tendencia del tiempo de resolución, importa si se puede resolver la gran instancia que uno tiene enfrente, y esa instancia suele tener una estructura que evita que sea un caso peor entre las de su mismo tamaño.
Por eso las decisiones de ingeniería también son distintas.
[1] https://arxiv.org/abs/2303.14605
[2] min { c^T x : A x >= b, x in R^n, some components of x in Z }
[3] https://gmplib.org/
[4] https://www.math.leidenuniv.nl/~hwl/PUBLICATIONS/1982f/art.p...
El resumen es más informativo: https://arxiv.org/abs/2303.14605
Dice que obtuvieron un algoritmo aleatorizado de tiempo (log(2n))^O(n) para resolver programación entera con n variables
Es decir, este trabajo es un resultado teórico que, con base en el análisis de la estructura de cuerpos convexos en R^n y de cómo cubrirlos con retículas enteras, presenta un algoritmo de tiempo exponencial mejor que el mejor anterior
La mayoría de los trabajos prácticos de ILP usan heurísticas y branch and bound, y aprovechan la estructura especial de la formulación concreta del problema
No está claro si esta investigación ayudará a alguna de esas dos cosas, y creo que será difícil juzgarlo solo leyendo el paper, a menos que alguien de un lugar como Gurobi lo explique
Es una observación menor, pero el título debería especificar programación lineal entera
Porque aquí la parte de “entera” marca una diferencia mucho mayor
Para la programación lineal se conocen algoritmos de tiempo polinomial desde hace décadas, y la programación lineal entera es NP-difícil
La programación lineal continua también es difícil
No en el sentido de que sea NP-difícil, sino en que construir solvers modernos y eficientes de LP requiere mucho de algoritmos e ingeniería
Solo el cómputo numérico ya es bastante complejo
Y muchos solvers de programación lineal entera se basan en solvers de programación lineal continua
Si eres ingeniero de software con interés en machine learning o algoritmos, vale la pena aprender programación lineal
Una cantidad sorprendente de problemas puede formularse como optimización lineal
Por ejemplo, en la universidad una vez hablé con un amigo que estudiaba ingeniería industrial sobre el número mínimo promedio de intercambios necesarios para colocar las bolas de billar en posiciones iniciales válidas dentro del triángulo
Ambos escribimos programas para resolverlo con muestreo de Monte Carlo: mi solución hacía BFS sobre el espacio de estados del grafo, y la de mi amigo usaba programación lineal
Probablemente la de mi amigo era más eficiente
Por ejemplo, árbol de expansión mínima, emparejamiento en grafos bipartitos o generales, flujos de red, intersección de matroides, flujos submodulares, etc.
Las soluciones en vértices de ciertos LP también tienen propiedades interesantes que pueden aprovecharse al diseñar algoritmos de aproximación para problemas NP-completos
Por ejemplo, en las soluciones en vértices del problema Steiner forest se puede demostrar que siempre existe una variable con valor al menos 1/2, así que, si se redondean iterativamente las variables y se vuelve a resolver el LP, se obtiene un algoritmo de 2-aproximación
Cuando estaba en posgrado, ese era el único algoritmo de 2-aproximación para este problema
Otro punto interesante es que, si tienes un oráculo de separación en tiempo polinomial, puedes resolver un LP aunque tenga un número exponencial de restricciones
Fue realmente divertida y la recomiendo
Incluso hoy, en investigación de operaciones, hay una cantidad sorprendente de solapamiento, pero me impacta que demasiados egresados de ingeniería industrial no sepan programar bien
Es una verdadera lástima
Recuerdo que la parte entera era bastante importante, porque normalmente solo se puede operar con montos enteros en centavos
Es un artículo corto, pero bueno
Aún no he revisado la matemática en profundidad, pero el preprint parece ser este: https://arxiv.org/pdf/2303.14605.pdf
No parece que estén mirando directamente los grupos espaciales como una forma de simplificar generalizando el “espacio” del problema mediante la reducción de simetrías o repeticiones, pero sería interesante ver si una estructura así puede aplicarse
Como alguien que usa software que aplica grupos espaciales y describe las celdas de Voronoi alrededor de puntos o conjuntos de puntos distribuidos dentro de ellos, estoy acostumbrado a las formas “espeluznantes” en que los efectos se propagan [1]
No soy matemático, solo arquitecto, así que este campo excede mis capacidades, pero como alguien que observa trayectorias a través de estructuras de panal generadas, este resultado merece investigarse más
[0] https://arxiv.org/pdf/2303.14605.pdf
[1] Si conocen a algún matemático con quien valga la pena colaborar en este trabajo, me gustaría que se pongan en contacto
Es un trabajo en curso y, como dije, matemáticamente excede mis capacidades, pero me he topado con propiedades interesantes que merecerían una mirada más profunda de un verdadero experto
Respecto al problema del viajante, me pareció interesante una cita del libro más reciente de Sapolsky, Determined: A Science of Life without Free Will
No sé qué tan relevante sea para los desarrolladores de software, pero es fascinante
Cuando una hormiga busca alimento revisando ocho lugares, idealmente debería visitar cada lugar una sola vez y elegir la ruta más corta entre las 5,040 rutas posibles, es decir, 7!
Esto es una forma del famoso problema del viajante, en el que los matemáticos llevan siglos trabajando sin encontrar una solución general
Una estrategia es la fuerza bruta: revisar y comparar todas las rutas posibles para elegir la mejor, pero con solo 10 lugares a visitar ya hay más de 360 mil posibilidades, y con 15 lugares hay más de 80 mil millones
Pero el punto es que, si se sueltan unas 10 mil hormigas —lo normal en una colonia— sobre un problema de ocho puntos de alimento, aunque ninguna hormiga sepa más que la ruta que tomó y dos reglas, encuentran una solución casi óptima entre las 5,040 en mucho menos tiempo que la fuerza bruta
Este método funciona tan bien que los científicos de la computación también resuelven este tipo de problemas con “hormigas virtuales”, y eso es lo que hoy se conoce como inteligencia de enjambre
Y la reacción estándar es: “algoritmos de computadora muy simples también hacen eso”
Para el problema del viajante con distancias euclidianas —es decir, cuando cada nodo tiene coordenadas fijas y el costo de una ruta es la distancia euclidiana entre dos puntos—, incluso se puede dar un algoritmo en tiempo polinomial que encuentre una ruta dentro de un factor ε de la solución óptima
Aunque con respecto a ε es exponencial
El prefacio también trae una excelente cláusula de descargo
“Personalmente creemos que la literatura de este campo debería tener menos marsupiales y más matemáticas, y que como comunidad deberíamos dejar atrás este periodo abundante en metáforas, de forma similar a como la química dejó atrás la alquimia. Sin embargo, esta lista no hace ninguna afirmación sobre la calidad científica de los artículos enumerados.”
[1]: https://fcampelo.github.io/EC-Bestiary/
Es un algoritmo modelado a partir de este comportamiento de las colonias de hormigas
Como dijeron otros, es bueno para encontrar óptimos locales, al igual que la búsqueda tabú, el recocido simulado y los algoritmos genéticos
Para la mayoría de los objetivos de negocio, como el caso de “producción de sofás” del artículo, eso es suficiente
Pero no es lo mismo que encontrar una “solución general”
La comparación de Sapolsky entre nuestra dificultad para encontrar “soluciones generales” y la capacidad de las hormigas para encontrar óptimos locales parece un poco engañosa
No significa que la forma general del problema no sea NP-difícil, sino que, si se agrega más información, se puede aproximar una solución suficientemente buena o hacer manejable la búsqueda óptima
Esta perspectiva fue especialmente marcada durante la primera “revolución” de la IA, cuando se popularizó ver la IA como un problema de búsqueda reforzado con conocimiento humano
¿Es eso a lo que el libro se refiere con “inteligencia de enjambre”?
Muchos problemas de optimización discreta pueden traducirse a programación lineal
Es una herramienta realmente poderosa si la conoces, igual que los solucionadores SAT
Como desarrollador, fue uno de esos momentos de “¿cómo se me pudo haber pasado esto hasta ahora?”
Es un resultado excelente, pero probablemente no sea práctico
Es parecido a cómo, en programación lineal, los métodos de punto interior tienen mejor complejidad teórica que el método símplex, pero en la práctica el símplex bien ajustado casi siempre gana
¿Hay alguna “razón” ampliamente aceptada por la que los métodos de punto interior suelan ser más lentos en la práctica?
Parecería que atravesar el interior debería acercarte más rápido a una buena solución que estar pegado a la frontera, aunque quizá en dimensiones altas esa diferencia importe menos
La forma en que está expresado aquí me resulta un poco confusa
Hay una frase que dice: “La mejor versión que se les ocurrió, una especie de límite de velocidad, proviene del caso trivial en el que las variables del problema solo pueden tomar valores binarios, es decir, 0 o 1, como si un viajante visita o no una ciudad”. ¿Están llamando trivial a un problema NP-completo?
Tenía entendido que todo ILP puede reducirse a 01-ILP y viceversa
Además, por la parte que dice: “Por desgracia, cuando las variables toman valores más allá de 0 y 1, el tiempo de ejecución del algoritmo aumenta mucho. Durante mucho tiempo, los investigadores se preguntaron si podían acercarse más a ese ideal trivial”, me pregunto si esta investigación es un solucionador que mejora la cota inferior de 01-ILP, o si es un algoritmo que acerca más la frontera entre 01-ILP e ILP general