Ведущий подход к симплекс-методу, широко используемой технике для уравновешивания сложных логистических ограничений, не подлежит улучшению

В 1939 году, опоздав на занятие по статистике в Калифорнийском университете в Беркли, Джордж Данциг, студент первого курса магистратуры, скопировал с доски две задачи, думая, что это домашнее задание. Позже он вспоминал, что задание показалось ему «сложнее, чем обычно», и извинился перед профессором за то, что на его выполнение у него ушло на несколько дней больше, чем обычно. Через несколько недель профессор сказал ему, что он решил две известные нерешённые задачи по статистике. Работа Данцига стала основой для его докторской диссертации, а спустя десятилетия — источником вдохновения для фильма «Умница Уилл Хантинг».

Данциг получил докторскую степень в 1946 году, сразу после Второй мировой войны, и вскоре стал математическим консультантом новообразованных ВВС США. Как и во всех современных войнах, исход Второй мировой войны зависел от разумного распределения ограниченных ресурсов. Но в отличие от предыдущих войн, этот конфликт был поистине глобальным по масштабам, и победа в нём была во многом достигнута благодаря огромной промышленной мощи. США могли просто производить больше танков, авианосцев и бомбардировщиков, чем их враги. Зная об этом, военные были очень заинтересованы в задачах оптимизации, то есть в том, как стратегически распределять ограниченные ресурсы в ситуациях, которые могли включать сотни или тысячи переменных.

Военно-воздушные силы поручили Данцигу найти новые способы решения подобных оптимизационных задач. В ответ он изобрёл симплекс-метод — алгоритм, основанный на некоторых математических методах, которые он разработал почти за десять лет до этого, решая те самые задачи с доски.

Спустя почти 80 лет симплекс-метод по-прежнему остаётся одним из наиболее широко используемых инструментов при принятии решений в области логистики или цепочки поставок в условиях сложных ограничений. Он эффективен и он работает. «Он всегда работал быстро, и никто никогда не видел, чтобы он работал медленно», — сказала Софи Хубертс из Французского национального центра научных исследований (CNRS).

В то же время, у него есть любопытное свойство, которое долгое время бросало тень на метод Данцига. В 1972 году математики доказали, что время, необходимое для выполнения задачи, может расти экспоненциально с увеличением числа ограничений. Таким образом, независимо от того, насколько быстрым может быть этот метод на практике, теория постоянно выдвигала наихудшие сценарии, из которых следовало, что он может занять экспоненциально больше времени. Для симплекс-метода «наши традиционные инструменты для изучения алгоритмов не работают», — сказала Хубертс.

Но в новой статье, которая будет представлена в декабре на конференции «Основы компьютерных наук», Хубертс и Элеон Бах, докторант Мюнхенского технического университета, похоже, преодолели эту проблему. Они ускорили алгоритм, а также предоставили теоретические обоснования того, почему экспоненциальное время выполнения, которое долгое время вызывало опасения, на практике не реализуется. Эта работа, основанная на знаковом результате 2001 года Даниэля Спилмана и Шан-Хуа Тенга, по словам Тенга, «блестящая [и] прекрасная».

«Это очень впечатляющая техническая работа, в которой мастерски сочетаются многие идеи, разработанные в предыдущих исследованиях, [а также добавлены] некоторые действительно интересные новые технические идеи», — сказал Ласло Вег, математик из Боннского университета, который не участвовал в этой работе.

Оптимальная геометрия

Симплекс-метод был разработан для решения следующего класса задач: предположим, что мебельная компания производит шкафы, кровати и стулья. Так получилось, что каждый шкаф приносит в три раза больше прибыли, чем каждый стул, а каждая кровать — в два раза больше. Если мы хотим выразить это в виде выражения, используя a, b и c для обозначения количества произведённой мебели, мы скажем, что общая прибыль пропорциональна 3a + 2b + c.

Чтобы максимизировать прибыль, сколько единиц каждого товара должна произвести компания? Ответ зависит от ограничений, с которыми она сталкивается. Допустим, что компания может производить не более 50 единиц в месяц, поэтому a + b + c меньше или равно 50. Шкафы сложнее в производстве — их можно изготовить не более 20, поэтому a меньше или равно 20. Для производства стульев требуется специальная древесина, запасы которой ограничены, поэтому c должно быть меньше 24.

Симплекс-метод превращает подобные ситуации — хотя и часто с гораздо большим количеством переменных — в геометрическую задачу. Представьте себе графическое изображение наших ограничений для a, b и c в трёх измерениях. Если a меньше или равно 20, мы можем представить плоскость на трёхмерном графике, перпендикулярную оси a, пересекающую её в точке a = 20. Мы бы определили, что наше решение должно лежать где-то на этой плоскости или ниже неё. Аналогичным образом мы можем провести границы, связанные с другими ограничениями. В совокупности эти границы могут вырезать в пространстве сложную трёхмерную фигуру, называемую многогранником.

Софи Хубертс держит в руках геометрическую модель оптимизационной задачи

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

Найти быстрый и прямой путь было бы легко, если бы не две вещи: во-первых, исходная форма, скорее всего, будет гораздо сложнее, чем в нашем примере – у неё будет гораздо больше граней, вершин и рёбер. А во-вторых, у нас нет карты, которая могла бы нас направлять. Вы не можете увидеть весь объект, по которому пытаетесь перемещаться. Вместо этого вы начинаете с одной вершины и выбираете, по какому ребру двигаться в первую очередь. Вы делаете то же самое на следующей вершине и так далее, не зная наверняка, куда приведёт вас выбранное ребро.

Если вам чрезвычайно не повезёт, вы можете пойти не в ту сторону на каждом перекрёстке и застрять в лабиринте. «Вы можете пройти самый длинный путь, чтобы добраться из точки А в точку Б, — сказал Бах, — потому что на каждом углу кто-нибудь скажет вам, что вы должны пойти в неправильном направлении». Именно такая ситуация может привести к худшему из возможных сценариев, реализация которого займёт экспоненциальное количество времени.

В 2001 году Спилман и Тенг доказали, что даже малейшая доля случайности может помочь предотвратить такой исход. Вернёмся к предыдущему примеру — с риском значительного упрощения аргументации Спилмана и Тенга — и предположим, что на каждом повороте у вас есть шесть вариантов выбора. Если вам всегда указывают худшее направление, у вас будут проблемы. Однако, если вы вместо этого будете полагаться на бросок кубика, у вас будет пять из шести шансов избежать худшего выбора, и катастрофа вряд ли случится. Внедрение элемента случайности и неопределённости в процесс является разумным, учитывая, что в реальном мире измерения никогда не бывают точными. Шпильман и Тенг ввели случайность совершенно иным способом, но они показали, что время выполнения никогда не может быть хуже, чем количество ограничений, возведённых в фиксированную степень — например, n^2 — что является примером так называемого полиномиального времени. Это намного лучше, чем экспоненциальное время, которое имеет форму, скажем, 2^n.

Шан-Хуа Тенг и Дэниел Спилман использовали случайность в своём знаковом результате 2001 года.

Тем не менее, это не решило проблему полностью. Их значения полиномиального времени по-прежнему были довольно высокими, отметил Хубертс — они включали член, возведённый в степень 30, что довольно много для показателя степени. Таким образом, за последние два десятилетия исследователи добились постепенного прогресса в снижении этого значения.

В своей новой статье Бах и Хубертс использовали в своём алгоритме ещё больше случайности, чтобы показать, что время выполнения гарантированно будет значительно ниже, чем было установлено ранее. Они также показали, что алгоритм, основанный на подходе, разработанном Спилманом и Тенгом, не может работать быстрее, чем полученное ими значение. По словам Хубертс, это говорит нам о том, что «мы полностью понимаем [эту] модель симплекс-метода».

«Это знаменует собой значительный прорыв в нашем понимании [симплексного] алгоритма, — сказал Хайко Рёглин, компьютерный учёный из Боннского университета, — предлагая первое действительно убедительное объяснение практической эффективности этого метода».

Тем не менее, Хубертс не считает, что на этом всё закончилось. Подход, начатый в 2001 году Спилманом и Тенгом, показал, как время выполнения можно сократить с экспоненциального до полиномиального. Следующим логическим шагом является изобретение способа линейного масштабирования с учётом количества ограничений. «Это путеводная звезда для всех этих исследований», — сказала она. Но для этого потребуется совершенно новая стратегия. «Мы не рискуем достичь этого в ближайшее время».

Хотя усилия Баха и Хубертс представляют теоретический интерес для коллег в их области, эта работа не приносит какой-либо непосредственной практической пользы. Тем не менее, она может помочь устранить некоторые опасения, которые могут возникнуть у людей в связи с использованием доступного сегодня программного обеспечения, основанного на симплекс-методе. «Хотя практические эксперименты показывают, что эти проблемы всегда решаются за полиномиальное время», — сказал Джулиан Холл, преподаватель математики в Эдинбургском университете, который разрабатывает программное обеспечение для линейного программирования, Бах и Хубертс предоставили более весомую математическую поддержку этой интуиции.
«Таким образом, теперь нам легче убедить тех, кто опасается экспоненциальной сложности алгоритма».

Исследователи обнаружили эффективный способ оптимизации