Дослідники підходять до нового обмеження швидкості для серйозної проблеми | Журнал Quanta

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

Але іноді вам потрібно оптимізувати для проблем, пов’язаних із цілими числами. Яка користь від плану оптимізації заводу, який виробляє кушетки 500.7? Для цього дослідники часто звертаються до варіанту лінійного програмування, який називається ціле лінійне програмування (ILP). Він популярний у додатках, які включають окремі рішення, включаючи планування виробництва, планування екіпажу авіакомпанії та маршрутизацію транспортних засобів. «По суті, ILP — це хліб і масло дослідження операцій як у теорії, так і на практиці», — сказав Сантош Вемпала, фахівець з інформатики в Технологічному інституті Джорджії.

Оскільки вони вперше сформулювали ILP понад 60 років тому, дослідники виявили різні алгоритми, які вирішують проблеми ILP, але всі вони були відносно повільними з точки зору кількості необхідних кроків. Найкраща версія, яку вони могли придумати — своєрідне обмеження швидкості — походить із тривіального випадку, коли змінні проблеми (наприклад, відвідує продавець місто чи ні) можуть приймати лише двійкові значення (нуль або 1). У цьому випадку ILP має середовище виконання, яке експоненціально масштабується з кількістю змінних, які також називають розмірністю. (Якщо є лише одна змінна, потрібно лише два кроки, щоб перевірити кожну можливу комбінацію та вирішити проблему; дві змінні означають чотири кроки, три означають вісім кроків і так далі.)

На жаль, як тільки змінні приймають значення, що перевищує лише нуль і 1, час роботи алгоритму значно збільшується. Дослідники довго гадали, чи зможуть вони наблизитися до тривіального ідеалу. Прогрес був повільним, з запис створений у 1980-х роках і лише поступовий поліпшення зроблено з тих пір.

Але нещодавно робота by Віктор Рейс, зараз в Інституті перспективних досліджень, і Томас Ротвосс, у Вашингтонському університеті, зробив найбільший стрибок у часі виконання за десятиліття. Комбінуючи геометричні інструменти для обмеження можливих рішень, вони створили новий, швидший алгоритм для розв’язання ILP майже за той самий час, що й у тривіальному бінарному випадку. Результат отримав нагороду за найкращу роботу у 2023 році Основи інформатики конференція

«Цей новий алгоритм надзвичайно захоплюючий», — сказав Ной Стівенс-Девідовіц, математик і інформатик Корнельського університету. «Це перше [значне] вдосконалення розв’язувачів ILP за майже 40 років».

ILP працює, перетворюючи задану задачу на набір лінійних рівнянь, які повинні задовольняти деякі нерівності. Конкретні рівняння базуються на деталях вихідної проблеми. Але хоча ці деталі можуть відрізнятися, основний склад проблем ILP залишається тим самим, що дає дослідникам єдиний спосіб атакувати безліч проблем.

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

Далі Ленстра уявив усі цілі числа як нескінченний набір точок сітки, відомий у математиці як решітка. Двовимірна версія виглядає як море точок, а в тривимірному – як точки з’єднання сталевих балок у будівлі. Розмір решітки також залежить від розмірності даної задачі.

Щоб розв’язати задану задачу ILP, Ленстра показав, що ви просто шукаєте, де можливі рішення зустрічаються з набором цілих чисел: на перетині опуклого тіла та решітки. І він винайшов алгоритм, який міг би вичерпно шукати цей простір — але щоб бути ефективним, йому іноді доводилося розбивати проблему на частини менших розмірів, додаючи багато кроків до середовища виконання.

У наступні роки кілька дослідників досліджували, як прискорити роботу цього алгоритму. У 1988 році Раві Каннан і Ласло Ловас представили концепцію під назвою радіус покриття, запозичений з вивчення коди для виправлення помилок, щоб опукле тіло та решітка перетиналися ефективніше. Грубо кажучи, радіус покриття гарантує, що опукле тіло завжди містить принаймні одну цілу точку, незалежно від того, де ви розмістите його на решітці. Як результат, розмір радіуса покриття також визначає, наскільки ефективно ви можете вирішити проблему ILP.

Отже, все звелося до визначення розміру ідеального радіуса покриття. На жаль, це виявилося важкою проблемою само по собі, і найкраще, що могли зробити Каннан і Ловас, це звузити можливе значення шляхом пошуку верхньої та нижньої меж. Вони показали, що верхня межа — максимальний розмір радіуса покриття — лінійно збільшується з розміром. Це було досить швидко, але недостатньо, щоб значно прискорити час виконання ILP. Протягом наступних 30 років інші дослідники могли зробити лише трохи краще.

Те, що зрештою допомогло Рейсу та Ротвоссові прорватися, так це непов’язаний математичний результат, який зосереджувався виключно на решітках. У 2016 році Одед Регев і Стівенс-Давідовіц показав, по суті, скільки точок решітки може поміститися в певну форму. Рейс і Ротвосс застосували це до інших форм, що дозволило їм краще оцінити кількість точок решітки, що містяться в радіусі покриття ILP, знизивши верхню межу. «Останній прорив стався з усвідомленням того, що насправді можна створювати інші форми», — сказав Регев.

Ця нова жорстка верхня межа була суттєвим покращенням, що дозволило Райсу та Ротвоссові досягти значного прискорення загального алгоритму ILP. Їхня робота доводить час виконання до (журнал n)^O(n), Де n є число змінних і О (п)означає, що масштабується лінійно n. (Цей вираз вважається «майже» таким самим, як час виконання бінарної задачі.)

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

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

Щодо того, чи можна ще покращити обчислювальну ефективність ILP, дослідники все ще сподіваються, що вони продовжуватимуть наближатися до ідеального часу виконання, але не найближчим часом. «Це потребує принципово нової ідеї», — сказав Вемпала.