Вчені виявили новий метод вирішення цілісного лінійного програмування, який може значно прискорити вирішення широкого спектра завдань, від виробничого планування до авіаперельотів. Цілочисленне лінійне програмування (ЦЛП) є ключовим інструментом у дослідженнях операцій, як зазначив Сантош Вемпала, вчений із Технологічного інституту Джорджії, що спеціалізується на комп’ютерних науках.

Дослідження , нещодавно представлене Віктором Рейсом з Інституту передових досліджень та Томасом Ротвоссом з Вашингтонського університету, виявилося проривом у галузі ЦЛП, значно прискоривши процес вирішення проблем. Їхня робота удостоїлася нагороди за найкращу статтю на конференції з основ інформатики у 2023 році.

ЦЛП працює шляхом перетворення завдання на набір лінійних рівнянь, які повинні задовольняти певні нерівності. Специфічні рівняння ґрунтуються на деталях вихідного завдання, але основна структура ЦЛП залишається незмінною, що дає дослідникам єдиний підхід до вирішення багатьох проблем.

Математик Хендрік Ленстра в 1983 році довів, що загальне завдання ЦЛП можна розв’язати, запропонувавши перший алгоритм для її вирішення. Він використовував геометричний підхід, перетворюючи нерівності, що лежать в основі ЦЛП, у опуклу форму, наприклад, у правильний багатокутник. Завдання вирішується шляхом пошуку перетину цієї форми з набором цілих чисел.

Робота Рейсу і Ротвосса ґрунтується на використанні геометричних інструментів для обмеження можливих рішень, що дозволило створити новий, швидший алгоритм для вирішення ЦЛП. Це суттєве поліпшення прискорило загальний час виконання алгоритму ЦЛП (log n)O(n), де n — кількість змінних.

Даніель Дадуш із Національного дослідницького інституту CWI в Нідерландах, який допоміг розробити алгоритм, використаний Рейсом та Ротвосом для вимірювання часу виконання ЦЛП, назвав це досягнення «тріумфом на стику математики, інформатики та геометрії».

На даний момент новий алгоритм ще не використовувався для вирішення практичних завдань через значне оновлення сучасних програм. Однак, як зазначає Ротвосс, головне тут — теоретичне розуміння проблеми, яка має фундаментальні програми.

Дослідники продовжують роботу над покращенням обчислювальної ефективності ЦЛП, сподіваючись наблизитися до ідеального часу виконання. Вемпала підкреслив, що для подальшого прогресу буде потрібна фундаментально нова ідея.