Ученые обнаружили новый метод решения целочисленного линейного программирования, который может значительно ускорить решение широкого спектра задач, от производственного планирования до планирования авиаперелетов. Целочисленное линейное программирование (ЦЛП) является ключевым инструментом в исследованиях операций, как отметил Сантош Вемпала, ученый из Технологического института Джорджии, специализирующийся в компьютерных науках.
Исследование , недавно представленное Виктором Рейсом из Института передовых исследований и Томасом Ротвоссом из Вашингтонского университета, оказалось прорывом в области ЦЛП, значительно ускорив процесс решения проблем. Их работа удостоилась награды за лучшую статью на конференции по основам информатики в 2023 году.
ЦЛП работает путем преобразования задачи в набор линейных уравнений, которые должны удовлетворять определенным неравенствам. Специфические уравнения основываются на деталях исходной задачи, но основная структура ЦЛП остается неизменной, что дает исследователям единый подход к решению множества проблем.
Математик Хендрик Ленстра в 1983 году доказал, что общая задача ЦЛП разрешима, предложив первый
Источник: SecurityLab