El problema del viajante de comercio es una de las cuestiones computacionales más antiguas que se conocen. Solicita la ruta ideal a través de una determinada lista de ciudades, minimizando el kilometraje. Aunque parezca sencillo, el problema es notoriamente difícil. Si bien puedes usar la fuerza bruta para comprobar todas las rutas posibles hasta encontrar el camino más corto, esa estrategia se vuelve insostenible después de solo un puñado de ciudades. En su lugar, se puede aplicar un modelo matemático riguroso llamado programación lineal, que aproxima aproximadamente el problema como un conjunto de ecuaciones y verifica metódicamente las posibles combinaciones para encontrar la mejor solución.

Pero a veces es necesario optimizar para problemas que involucran cantidades de números enteros. ¿De qué sirve un plan de optimización de una fábrica que fabrica 500.7 sofás? Para ello, los investigadores suelen recurrir a una variante de la programación lineal llamada programación lineal entera (IL P). Es popular en aplicaciones que implican decisiones discretas, incluida la planificación de la producción, la programación de la tripulación de las aerolíneas y las rutas de los vehículos. "Básicamente, ILP es el pan de cada día de la investigación de operaciones, tanto en la teoría como en la práctica", dijo santosh vempala, científico informático del Instituto de Tecnología de Georgia.

Desde que formularon por primera vez ILP hace más de 60 años, los investigadores han descubierto varios algoritmos que resuelven problemas de ILP, pero todos han sido relativamente lentos en términos de la cantidad de pasos requeridos. 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 (como si un vendedor visita una ciudad o no) sólo pueden asumir valores binarios (cero o 1). En este caso, ILP tiene un tiempo de ejecución que escala exponencialmente con el número de variables, también llamado dimensión. (Si sólo hay una variable, sólo se necesitan dos pasos para probar todas las combinaciones posibles y resolver el problema; dos variables significan cuatro pasos, tres significan ocho pasos, y así sucesivamente).

Desafortunadamente, una vez que las variables toman un valor más allá de cero y 1, el tiempo de ejecución del algoritmo aumenta mucho más. Los investigadores se han preguntado durante mucho tiempo si podrían acercarse al ideal trivial. Los avances han sido lentos, con la grabar establecido en la década de 1980 y sólo incremental mejoras hecho desde entonces.

Pero reciente TRABAJO by Víctor Reyes, actualmente en el Instituto de Estudios Avanzados, y Thomas Rothvoss, en la Universidad de Washington, ha dado el mayor salto en tiempo de ejecución en décadas. Combinando herramientas geométricas para limitar las posibles soluciones, crearon un algoritmo nuevo y más rápido para resolver ILP casi al mismo tiempo que el caso binario trivial. El resultado recibió el premio al mejor artículo en la edición de 2023. Fundamentos de la informática conferencia.

"Este nuevo algoritmo es extremadamente emocionante", dijo Noah Stephens-Davidowitz, matemático e informático de la Universidad de Cornell. "Representa la primera mejora [importante] en los solucionadores de ILP en casi 40 años".

ILP funciona transformando un problema dado en un conjunto de ecuaciones lineales que deben satisfacer algunas desigualdades. Las ecuaciones específicas se basan en los detalles del problema original. Pero si bien estos detalles pueden diferir, la composición básica de los problemas de ILP sigue siendo la misma, lo que brinda a los investigadores una forma única de atacar una multitud de problemas.

Eso no quiere decir que sea un trabajo fácil. No fue hasta 1983 que el matemático Hendrik Lenstra demostrado que el problema general era incluso solucionable, proporcionando el primer algoritmo que podía hacerlo. Lenstra pensó en ILP geométricamente. Primero, convirtió las desigualdades centrales de ILP en una forma convexa, como cualquier polígono regular. Esta forma representa las limitaciones del problema individual que estás resolviendo, ya sea la producción de sofás o la programación de líneas aéreas, por lo que el interior de la forma corresponde a todos los valores posibles que podrían resolver las desigualdades y, por tanto, el problema. Lenstra llamó a esta forma cuerpo convexo. La dimensión del problema influye en la dimensión de esta forma: con dos variables toma la forma de un polígono plano; en tres dimensiones es un Sólido platónico, Y así sucesivamente.

A continuación, Lenstra imaginó todos los números enteros como un conjunto infinito de puntos de cuadrícula, conocido en matemáticas como red. Una versión bidimensional parece un mar de puntos, y en tres dimensiones parece los puntos donde se conectan las vigas de acero de un edificio. La dimensión de la red también depende de la dimensión de un problema determinado.

Para resolver un problema ILP dado, Lenstra demostró que simplemente se busca dónde las posibles soluciones se encuentran con el conjunto de números enteros: en la intersección del cuerpo convexo y la red. Y se le ocurrió un algoritmo que podía buscar este espacio de manera exhaustiva, pero para que fuera efectivo, a veces tenía que dividir el problema en partes de dimensiones más pequeñas, agregando muchos pasos al tiempo de ejecución.

En los años siguientes, varios investigadores exploraron cómo hacer que este algoritmo se ejecutara más rápido. En 1988, Ravi Kannan y László Lovász introdujeron un concepto llamado radio de cobertura, prestado del estudio de códigos de corrección de errores, para ayudar a que el cuerpo convexo y la red se crucen de manera más eficiente. Aproximadamente, el radio de cobertura garantiza que el cuerpo convexo siempre contenga al menos un punto entero, sin importar dónde lo coloque en la red. Como resultado, el tamaño del radio de cobertura también determina la eficacia con la que se puede resolver el problema ILP.

Todo se redujo a determinar el tamaño del radio de cobertura ideal. Desafortunadamente, esto resultó ser un problema difícil por sí solo, y lo mejor que Kannan y Lovász pudieron hacer fue reducir un posible valor buscando límites superior e inferior. Demostraron que el límite superior (el tamaño máximo del radio de cobertura) aumentaba linealmente con la dimensión. Esto fue bastante rápido, pero no lo suficiente como para acelerar significativamente el tiempo de ejecución del ILP. Durante los siguientes 30 años, otros investigadores sólo pudieron hacerlo un poco mejor.

Lo que finalmente ayudó a Reis y Rothvoss a avanzar fue un resultado matemático no relacionado que se centró exclusivamente en las redes. En 2016, Oded Regev y Stephens-Davidowitz mostró, de hecho, cuántos puntos de la red podrían caber dentro de una forma específica. Reis y Rothvoss aplicaron esto a otras formas, lo que les permitió estimar mejor el número de puntos de red contenidos en un radio de cobertura ILP, reduciendo el límite superior. "El último avance se produjo cuando nos dimos cuenta de que en realidad se pueden hacer otros tipos de formas", dijo Regev.

Este nuevo límite superior más estricto supuso una gran mejora, ya que permitió a Reis y Rothvoss lograr una aceleración espectacular del algoritmo ILP general. Su trabajo lleva el tiempo de ejecución a (log n)^O(n), Donde n es el número de variables y O (n)significa que escala linealmente con n. (Esta expresión se considera “casi” igual que el tiempo de ejecución del problema binario).

"Es un triunfo en la intersección de las matemáticas, la informática y la geometría", dijo Daniel Dadush del instituto nacional de investigación CWI en los Países Bajos, quien ayudó a ser pionero en el algoritmo que Reis y Rothvoss utilizaron para medir el tiempo de ejecución del ILP.

Por ahora, el nuevo algoritmo no se ha utilizado para resolver ningún problema logístico, ya que requeriría demasiado trabajo actualizar los programas actuales para poder utilizarlo. Pero para Rothvoss, eso no viene al caso. "Se trata de la comprensión teórica de un problema que tiene aplicaciones fundamentales", dijo.

En cuanto a si la eficiencia computacional de ILP podría mejorarse aún más, los investigadores todavía tienen la esperanza de seguir acercándose al tiempo de ejecución ideal, pero no en el corto plazo. "Eso requeriría una idea fundamentalmente nueva", dijo Vempala.