Исследователи приближаются к новому ограничению скорости для решения основополагающей проблемы | Журнал Кванта

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

Но иногда вам необходимо оптимизировать задачи, связанные с целыми числами. Какая польза от плана оптимизации завода, производящего 500.7 диванов? Для этого исследователи часто обращаются к варианту линейного программирования, называемому целочисленное линейное программирование (ИЛП). Он популярен в приложениях, требующих принятия дискретных решений, включая планирование производства, составление расписания работы экипажей авиакомпаний и маршрутизацию транспортных средств. «По сути, ILP — это хлеб с маслом исследования операций как в теории, так и на практике», — сказал Сантош Вемпала, ученый-компьютерщик из Технологического института Джорджии.

С тех пор как они впервые сформулировали ПДОДИ за 60 лет назадИсследователи обнаружили различные алгоритмы, решающие проблемы ILP, но все они были относительно медленными с точки зрения количества необходимых шагов. Лучшая версия, которую они смогли придумать (своего рода ограничение скорости), исходит из тривиального случая, когда переменные задачи (например, посещает ли продавец город или нет) могут принимать только двоичные значения (ноль или 1). В этом случае ILP имеет среду выполнения, которая экспоненциально масштабируется в зависимости от количества переменных, также называемых измерением. (Если имеется только одна переменная, для проверки каждой возможной комбинации и решения задачи потребуется всего два шага; две переменные означают четыре шага, три — восемь шагов и так далее.)

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

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

«Этот новый алгоритм чрезвычайно интересен», — сказал Ной Стивенс-Давидовиц, математик и ученый-компьютерщик из Корнелльского университета. «Это первое [крупное] улучшение решателей ILP почти за 40 лет».

ILP работает путем преобразования заданной проблемы в набор линейных уравнений, которые должны удовлетворять некоторым неравенствам. Конкретные уравнения основаны на деталях исходной задачи. Но хотя эти детали могут различаться, основная структура проблем ПДОДИ остается прежней, что дает исследователям единый способ решения множества проблем.

Это не значит, что это легкая работа. Лишь в 1983 году математик Хендрик Ленстра доказанный что общая проблема даже разрешима, и появился первый алгоритм, который мог это сделать. Ленстра думал о ILP геометрически. Во-первых, он превратил неравенства, лежащие в основе ILP, в выпуклую форму, например, в любой правильный многоугольник. Эта фигура представляет ограничения отдельной задачи, которую вы решаете, будь то производство диванов или планирование полетов, поэтому внутренняя часть фигуры соответствует всем возможным значениям, которые могут решить неравенства и, следовательно, проблему. Ленстра назвал эту форму выпуклым телом. Размер задачи влияет на размер этой фигуры: с двумя переменными она принимает форму плоского многоугольника; в трёх измерениях это Платоническое тело, И так далее.

Затем Ленстра представил все целые числа как бесконечный набор точек сетки, известный в математике как решетка. Двумерная версия выглядит как море точек, а в трехмерном — как точки соединения стальных балок в здании. Размерность решетки также зависит от размерности данной задачи.

Ленстра показал, что для решения данной задачи ILP нужно просто искать место, где возможные решения встречаются с набором целых чисел: на пересечении выпуклого тела и решетки. И он придумал алгоритм, который мог бы обследовать это пространство исчерпывающим образом, но чтобы быть эффективным, ему иногда приходилось разбивать задачу на части меньшего размера, добавляя множество шагов во время выполнения.

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

Итак, все сводилось к определению размера идеального радиуса покрытия. К сожалению, это само по себе оказалось сложной проблемой, и лучшее, что могли сделать Каннан и Ловас, — это сузить возможное значение путем поиска верхних и нижних границ. Они показали, что верхняя граница — максимальный размер радиуса покрытия — линейно увеличивается с размером. Это было довольно быстро, но недостаточно, чтобы значительно ускорить работу ILP. В течение следующих 30 лет другие исследователи смогли добиться лишь немного большего успеха.

Что в конечном итоге помогло Рейсу и Ротвоссу добиться прорыва, так это несвязанный математический результат, который был сосредоточен исключительно на решетках. В 2016 году Одед Регев и Стивенс-Давидовиц показалпо сути, сколько точек решетки может поместиться в определенную форму. Рейс и Ротвосс применили это к другим формам, что позволило им лучше оценить количество точек решетки, содержащихся в радиусе покрытия ILP, снизив верхнюю границу. «Последний прорыв произошел с осознанием того, что вы действительно можете создавать другие виды фигур», — сказал Регев.

Эта новая ужесточенная верхняя граница стала огромным улучшением, позволившим Рейсу и Ротвоссу добиться значительного ускорения общего алгоритма ILP. Их работа приводит к тому, что среда выполнения (log n)^O(n), Где n количество переменных и О (п)означает, что он масштабируется линейно с n. (Это выражение считается «почти» таким же, как время выполнения бинарной задачи.)

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

На данный момент новый алгоритм фактически не использовался для решения каких-либо логистических проблем, поскольку для его использования потребовалось бы слишком много работы по обновлению сегодняшних программ. Но для Ротвосса это не имеет значения. «Речь идет о теоретическом понимании проблемы, имеющей фундаментальное применение», — сказал он.

Что касается возможности дальнейшего повышения вычислительной эффективности ILP, исследователи все еще надеются, что они будут продолжать приближаться к идеальному времени выполнения, но не в ближайшее время. «Для этого потребуется принципиально новая идея», — сказал Вемпала.