Целочисленное линейное программирование может помочь найти ответ на множество реальных проблем. Теперь исследователи нашли гораздо более быстрый способ это сделать.
Задача коммивояжера — одна из старейших известных вычислительных задач. Она заключается в поиске кратчайшего маршрута через определённый список городов. Несмотря на кажущуюся простоту, проблема, как известно, сложна. И хотя вы можете использовать перебор, чтобы проверить все возможные маршруты, пока не найдете кратчайший путь, такая стратегия становится несостоятельной, уже когда в списке всего лишь несколько городов. Вместо этого вы можете применить строгую математическую модель, называемую линейным программированием, которая грубо аппроксимирует задачу как набор уравнений и методично проверяет возможные комбинации, чтобы найти лучшее решение.
Но иногда вам необходимо оптимизировать задачи, связанные с целыми числами. Какая польза от плана оптимизации завода, который производит 500,7 диванов? Для этого исследователи часто обращаются к варианту линейного программирования, называемому целочисленным линейным программированием (ILP). Он популярен в приложениях, требующих принятия дискретных решений, включая планирование производства, составление расписания работы экипажей авиакомпаний и маршрутизацию транспортных средств. «По сути, ILP — это хлеб и масло исследования операций как в теории, так и на практике», — сказал Сантош Вемпала, учёный из Технологического института Джорджии.
С тех пор как учёные впервые сформулировали ILP более 60 лет назад, были открыты различные алгоритмы, решающие проблемы ILP, но все они были относительно медленными с точки зрения количества необходимых шагов. Лучшая версия, которую учёные смогли придумать (своего рода лимит скорости), исходит из тривиального случая, когда переменные задачи (например, посещает ли коммивояжер город или нет) могут принимать только двоичные значения (0 или 1). В этом случае ILP имеет сложность, которая экспоненциально масштабируется в зависимости от количества переменных, также называемом размерностью. (Если переменная всего одна, то для проверки всех возможных комбинаций и решения задачи потребуется всего два шага; две переменные означают четыре шага, три — восемь шагов и так далее.)
К сожалению, как только переменные принимают значения, выходящие за пределы 0 и 1, время работы алгоритма значительно увеличивается. Исследователи уже давно задаются вопросом, смогут ли они приблизиться к тривиальному идеалу. Прогресс был медленным: рекорд был установлен в 1980-х годах, и с тех пор были достигнуты лишь небольшие улучшения.
Но недавняя работа Виктора Рейса, который в настоящее время работает в Институте перспективных исследований, и Томаса Ротвосса из Вашингтонского университета, совершила самый большой скачок за последние десятилетия. Объединив геометрические инструменты для ограничения возможных решений, они создали новый, более быстрый алгоритм решения ILP почти за то же время, что и в тривиальном двоичном случае. Результат получил награду за лучшую статью на конференции Foundations of Computer Science 2023 года.
«Этот новый алгоритм чрезвычайно интересен, — сказал Ной Стивенс-Давидовиц, математик и учёный из Корнелльского университета. — Это первое крупное улучшение в ILP почти за 40 лет».
ILP работает путем преобразования заданной проблемы в набор линейных уравнений, которые должны удовлетворять некоторым неравенствам. Конкретные уравнения основаны на деталях исходной задачи. Но хотя эти детали могут различаться, основная структура проблем ILP остается прежней, что дает исследователям единый способ решения множества проблем.
Нельзя сказать, что это лёгкая работа. Лишь в 1983 году математик Хендрик Ленстра доказал, что общая проблема вообще разрешима, и предложил первый алгоритм, который мог это сделать. Ленстра думал об ILP геометрически. Во-первых, он превратил неравенства, лежащие в основе ILP, в выпуклую форму, например, в любой правильный многоугольник. Эта фигура представляет ограничения отдельной задачи, которую вы решаете, будь то производство диванов или планирование полётов, поэтому внутренняя часть фигуры соответствует всем возможным значениям, которые могут решить неравенства и, следовательно, проблему. Ленстра назвал эту форму выпуклым телом. Размер задачи влияет на размер этой фигуры: с двумя переменными она принимает форму плоского многоугольника; в трех измерениях это платоново тело и так далее.
Затем Ленстра представил все целые числа как бесконечный набор точек сетки, известный в математике как решётка. Двухмерная версия выглядит как море точек, а в трех измерениях — как точки соединения стальных балок в здании. Размерность решётки также зависит от размерности данной задачи.
Ленстра показал, что для решения данной задачи ILP нужно просто искать место, где возможные решения встречаются с набором целых чисел: на пересечении выпуклого тела и решётки. И он придумал алгоритм, который мог бы изучить это пространство исчерпывающим образом, но чтобы быть эффективным, ему иногда приходилось разбивать задачу на части меньшего размера, добавляя множество шагов ко времени выполнения.
В последующие годы несколько исследователей изучали, как заставить этот алгоритм работать быстрее. В 1988 году Рави Каннан и Ласло Ловас представили концепцию, называемую радиусом покрытия, заимствованную из теории кодов коррекции ошибок, чтобы помочь выпуклому телу и решётке эффективнее пересекаться. Грубо говоря, радиус покрытия гарантирует, что выпуклое тело всегда содержит хотя бы одну целочисленную точку, независимо от того, где вы разместите его на решётке. В результате размер радиуса покрытия также определяет, насколько эффективно вы сможете решить проблему ILP.
Итак, всё свелось к определению размера идеального радиуса покрытия. К сожалению, это само по себе оказалось сложной проблемой, и лучшее, что могли сделать Каннан и Ловас, — это сузить возможное значение путём поиска верхних и нижних границ. Они показали, что верхняя граница — максимальный размер радиуса покрытия — линейно увеличивается с размером измерения. Это было довольно быстро, но недостаточно, чтобы значительно ускорить работу ILP. В течение следующих 30 лет другие исследователи смогли добиться лишь немного большего успеха.
Что в конечном итоге помогло Рейсу и Ротвоссу добиться прорыва, так это несвязанный математический результат, который был сосредоточен исключительно на решётках. В 2016 году Одед Регев и Стивенс-Давидовиц фактически показали, сколько точек решётки может уместиться в определённой геометрической фигуре. Рейс и Ротвосс применили это к другим фигурам, что позволило им лучше оценить количество точек решётки, содержащихся в радиусе покрытия ILP, снизив верхнюю границу. «Последний прорыв произошёл с осознанием того, что вы в реальности можете создавать другие виды фигур», — сказал Регев.
Эта новая уточнённая верхняя граница стала невероятным улучшением, что позволило Рейсу и Ротвоссу добиться значительного ускорения общего алгоритма ILP. Их работа доводит время выполнения до (log n)O(n), где n — количество запросов, а O(n) означает, что оно линейно масштабируется с ростом n. (У этого выражения «почти» такое же время выполнения, как и у бинарной задачи.)
«Это триумф на стыке математики, информатики и геометрии», — сказал Дэниэл Дадуш из национального исследовательского института CWI в Нидерландах, именно он помог разработать алгоритм, который Рейс и Ротвосс использовали для измерения времени выполнения ILP.
На данный момент новый алгоритм фактически не использовался для решения каких-либо логистических проблем, поскольку для его использования потребовалось бы слишком много работы по обновлению сегодняшних программ. Но для Ротвосса это не имеет значения. «Речь идет о теоретическом понимании проблемы, имеющей фундаментальное применение», — сказал он.
Что касается возможности дальнейшего повышения вычислительной эффективности ILP, исследователи всё ещё надеются, что они будут продолжать приближаться к идеальной скорости, но не в ближайшее время. «Для этого потребуется принципиально новая идея», — сказал Вемпала.
Автор перевода @arielf
НЛО прилетело и оставило здесь промокод для читателей нашего блога:
— 15% на заказ любого VDS (кроме тарифа Прогрев) — HABRFIRSTVDS.
