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

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

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

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

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

Источник: noworries.news