Ученые обнаружили новый метод решения целочисленного линейного программирования, который может значительно ускорить решение широкого спектра задач, от производственного планирования до планирования авиаперелетов. Целочисленное линейное программирование (ЦЛП) является ключевым инструментом в исследованиях операций, как отметил Сантош Вемпала, ученый из Технологического института Джорджии, специализирующийся в компьютерных науках.
Исследование , недавно представленное Виктором Рейсом из Института передовых исследований и Томасом Ротвоссом из Вашингтонского университета, оказалось прорывом в области ЦЛП, значительно ускорив процесс решения проблем. Их работа удостоилась награды за лучшую статью на конференции по основам информатики в 2023 году.
ЦЛП работает путем преобразования задачи в набор линейных уравнений, которые должны удовлетворять определенным неравенствам. Специфические уравнения основываются на деталях исходной задачи, но основная структура ЦЛП остается неизменной, что дает исследователям единый подход к решению множества проблем.
Математик Хендрик Ленстра в 1983 году доказал, что общая задача ЦЛП разрешима, предложив первый алгоритм для ее решения. Он использовал геометрический подход, преобразуя неравенства, лежащие в основе ЦЛП, в выпуклую форму, например, в правильный многоугольник. Задача решается путем поиска пересечения этой формы с набором целых чисел.
Работа Рейса и Ротвосса основана на использовании геометрических инструментов для ограничения возможных решений, что позволило создать новый, более быстрый алгоритм для решения ЦЛП. Это существенное улучшение ускорило общее время выполнения алгоритма ЦЛП до (log n)O(n), где n – количество переменных.
Даниэль Дадуш из Национального исследовательского института CWI в Нидерландах, который помог разработать алгоритм, использованный Рейсом и Ротвоссом для измерения времени выполнения ЦЛП, назвал это достижение “триумфом на стыке математики, информатики и геометрии”.
На данный момент новый алгоритм еще не использовался для решения практических задач из-за необходимости значительного обновления современных программ. Однако, как отмечает Ротвосс, главное здесь – теоретическое понимание проблемы, имеющей фундаментальные приложения.
Исследователи продолжают работу над улучшением вычислительной эффективности ЦЛП, надеясь приблизиться к идеальному времени выполнения. Вемпала подчеркнул, что для дальнейшего прогресса потребуется фундаментально новая идея.