Investigadores descubren una forma de procesar la programación lineal entera más rápido

Investigadores se acercan a un nuevo límite de velocidad para la programación lineal entera

• La programación lineal entera (ILP) ayuda a encontrar respuestas para diversos problemas del mundo real.
• Los investigadores descubrieron un nuevo método para ejecutar ILP mucho más rápido.

Introducción al problema del viajante

• El problema del viajante es uno de los problemas computacionales más antiguos que se conocen, y consiste en encontrar la ruta ideal que pase por una lista específica de ciudades usando la menor cantidad de millas posible.
• Aunque parece simple, este problema es famosamente difícil, y una estrategia de fuerza bruta que revise todas las rutas posibles se vuelve inviable una vez que el número de ciudades supera una cantidad pequeña.
• En su lugar, se aplica un modelo matemático estricto llamado programación lineal para aproximar el problema como un conjunto de ecuaciones y revisar sistemáticamente las combinaciones posibles hasta encontrar la mejor solución.

La importancia de la programación lineal entera

• A veces es necesario optimizar un problema usando números enteros.
• La programación lineal entera (ILP) es popular en aplicaciones que implican decisiones discretas, incluidas la planificación de producción, la programación de tripulaciones aéreas y el enrutamiento de vehículos.
• ILP es central para la investigación de operaciones tanto en la teoría como en la práctica, según Santosh Vempala, científico de la computación en Georgia Tech.

Avances en los algoritmos de ILP

• Durante más de 60 años desde que se formuló por primera vez la ILP, los investigadores encontraron diversos algoritmos para resolver problemas de ILP, pero todos requerían una cantidad de pasos relativamente lenta.
• Investigaciones recientes de Victor Reis y Thomas Rothvoss lograron el mayor salto en tiempo de ejecución en décadas.
• Ellos combinaron herramientas geométricas para limitar las soluciones posibles y crearon un nuevo algoritmo más rápido que resuelve ILP en casi el mismo tiempo que el caso binario.

Cómo se resuelven los problemas de ILP

• La ILP convierte un problema dado en una serie de ecuaciones lineales, y estas ecuaciones deben satisfacer algunas desigualdades.
• Estas ecuaciones se basan en los detalles del problema original, pero la estructura básica de un problema de ILP es la misma, lo que les da a los investigadores una sola forma de abordar muchos problemas distintos.

Comprensión teórica de los algoritmos de ILP

• El nuevo algoritmo todavía no se ha usado para resolver problemas logísticos reales, pero eso muestra que entender los problemas teóricos sigue siendo importante.
• Los investigadores siguen siendo optimistas sobre si se puede mejorar aún más la eficiencia computacional de la ILP, aunque eso requerirá ideas fundamentalmente nuevas.

Opinión de GN⁺

• Esta investigación representa un avance importante en la intersección entre la informática y las matemáticas. En particular, tiene el potencial de mejorar de forma significativa la eficiencia de la ILP, que se usa para resolver problemas logísticos complejos.
• Aunque el nuevo algoritmo todavía requiere mucho trabajo antes de aplicarse en programas del mundo real, el avance en la comprensión teórica puede contribuir de manera importante a futuras mejoras algorítmicas y al desarrollo de tecnologías relacionadas.
• Este artículo ofrece noticias interesantes para investigadores en informática y para personas interesadas en la resolución de problemas matemáticos, y destaca la importancia de nuevos enfoques para resolver problemas complejos.

[GN⁺]

Comentarios de Hacker News

• Reducir la cota algorítmica superior de problemas NP-completos es algo muy interesante, pero puede no estar directamente relacionado con mejorar el tiempo de ejecución al resolver problemas reales.

  • Los solucionadores de programación entera mixta (MIP) usan una variedad de algoritmos y heurísticas.
  • Construir una biblioteca de heurísticas y estrategias es la razón por la que las mejoras en los solucionadores MIP superan la ley de Moore.
  • De 1990 a 2014, las mejoras del hardware fueron de 6500 veces, pero las del software fueron responsables de una mejora de rendimiento de 870000 veces.
  • El artículo citado podría ser otra pieza del rompecabezas en la mejora continua del rendimiento de los solucionadores MIP, pero no es seguro.

• El nuevo algoritmo todavía no se ha usado para resolver problemas logísticos reales.

  • Esto se debe a que actualizar los programas actuales requiere demasiado trabajo.
  • Sin embargo, según Rothvoss, esto trata sobre la comprensión teórica de un problema con aplicaciones fundamentales.

• El título "Integer Linear Programming" debería indicarse explícitamente, porque la parte entera es mucho más importante.

  • Desde hace décadas se conocen algoritmos en tiempo polinómico para programación lineal, pero la programación lineal entera es NP-hard.

• Los ingenieros de software deberían aprender sobre programación lineal.

  • Muchos problemas pueden expresarse como optimización lineal.
  • Por ejemplo, un problema sobre el número promedio mínimo de intercambios para colocar bolas de billar en la posición inicial correcta sobre un triángulo puede resolverse usando programación lineal.

• Este artículo no analiza directamente los Space Groups, pero sería interesante ver si puede usarse para generalizar la simplificación del "espacio" del problema.

  • El autor no es matemático sino arquitecto, pero como alguien que observa rutas a través de panales generados, sugiere que este resultado merece más investigación.

• Lo citado del libro de Sapolsky sobre el problema del viajante, "Determined: A Science of Life without Free Will", quizá no sea relevante para desarrolladores de software, pero sigue siendo fascinante.

  • Las hormigas revisan ocho lugares en busca de comida, y eso es una versión del famoso "problema del viajante".
  • Los científicos de la computación pueden usar "hormigas virtuales" para resolver estos problemas, algo que ahora se conoce como inteligencia de enjambre.

• El autor estudió investigación de operaciones en Stanford en 1985/86 y tomó clases con George Dantzig, pero terminó convirtiéndose en ingeniero de software en lugar de dedicarse a investigación de operaciones.

  • Le parece interesante ver cuánto se ha aprendido sobre algoritmos de programación lineal.

• Muchos problemas de optimización discreta pueden transformarse en programas lineales.

  • Es un conjunto de herramientas muy poderoso, como los solucionadores SAT.

• La complejidad teórica sugiere que los métodos de punto interior pueden ser mejores que simplex para LP, pero en la práctica un simplex bien ajustado casi siempre gana.