Рисунок: Галя Панченко
иллюстрации Галя Панченко
Понятие "сложность" как фундамент компьютерной науки
Когда школьника учат решать задачи, понятие "сложность" для него исключительно субъективно, таким и остается на всю жизнь. Да и математики на протяжении веков не были озабочены объективной оценкой сложности задач, пока к этому их не подтолкнуло появление компьютеров. На первых порах теория алгоритмов ограничилась бинарной классификацией сложности: класс задач, которые можно решить за конечное время, и класс задач, для которых можно доказать принципиальную невозможность решения в конечное время. До середины прошлого века ученый, предлагающий новый алгоритм, не считал необходимым оценивать время его работы. Важно было лишь, что оно конечно, то есть алгоритм сходится. А неявно предполагалось, что усовершенствование компьютеров делает вопрос об оценке необходимых ресурсов бессмысленным.
Но в СССР с 1960-х годов возникает несколько математических семинаров, участники которых пытаются понять, что такое "сложность" решения задачи в конечное время. Результаты математические оказались чрезвычайно интересными и неожиданными. Результаты же "метафизические" могли вызвать тревогу. Стало очевидно, что теория алгоритмической сложности плохо дружит с так называемым здравым смыслом, а получение новых результатов, как правило, требует отказа от привычных методов и подходов.
Задача тысячелетия
В 1970 году Л.А. Левин — ученик А.Н. Колмогорова и А.А. Маркова и недавний выпускник мехмата МГУ — сделал работу, которая у многих специалистов вызвала разве что недоумение. Трехстраничная заметка "Универсальные задачи перебора" была опубликована в журнале "Проблемы передачи информации" только в 1973 году, на третий год после поступления. А годом ранее (в Союзе об этом тогда никто не подозревал) вышла статья американского математика Р.М. Карпа "Сводимость комбинаторных проблем". Эти пионерские статьи и последовавший за ними шквал работ, развивающих идеи Левина и Карпа, предопределили пути развития всей области computer sciences на следующие десятилетия.
В 2000 году Математический институт Клея сформулировал семь "задач тысячелетия". За решение каждой обещан The Millennium Prize в $ 1 000 000. Первой значилась проблема, поставленная в работах Левина и Карпа и до сих пор не решенная.
Современная теория алгоритмической сложности ограничивается рассмотрением двух ее классов: экспоненциальной и полиномиальной. Эти названия показывают, с какой именно трудоемкостью (по порядку величины числа шагов вычисления, например) возможно решение любой задачи из заданного класса. В качестве аргумента функции, определяющей трудоемкость, служит длина n того входного слова, которое задает эту задачу. Если число шагов вычисления оценивается сверху некоторым полиномом от n, соответствующую задачу называют полиномиально разрешимой. Принято считать, что если задача полиномиально разрешима, то она может быть решена за "приемлемое" время.
В работах Левина и Карпа было доказано существование универсальных задач, из полиномиальной разрешимости которых следует полиномиальная разрешимость любой так называемой переборной задачи. В настоящее время известно более 2000 таких задач, причем техника сводимости позволяет (как правило, без особого труда) каждую новую вычислительную задачу проверять на "универсальность".
Таким образом, нет необходимости отдельно выяснять трудоемкость задачи — достаточно установить ее сводимость к любой из полиномиально разрешимых задач. А после этого остается "самая малость" — хотя бы для одной из тысяч универсальных задач найти алгоритм, который позволит решить ее за полиномиальное время. Если такой алгоритм найдется, станет ясно, что все остальные задачи из этого класса решаются в полиномиальное время тем же самым алгоритмом. А если хотя бы для одной из них будет доказано, что такого алгоритма не существует, это будет означать отсутствие полиномиальной разрешимости для любой универсальной задачи. Так что институт Клея не продешевил, назначая приз за решение вопроса о совпадении классов переборных и полиномиально разрешимых задач. Хотя подавляющая часть специалистов не верит, что задачи из класса универсальных переборных могут быть полиномиально разрешимы (только 9 из 100 опрошенных математиков допустили такую возможность), точного доказательства еще никто не представил.
Сложность решения "простых" задач линейного программирования
Советский математик Л.В. Канторович и американец Тьяллинг Купманс стали лауреатами Нобелевской премии по экономике 1975 года за работы по "оптимальному распределению ресурсов". Результаты их работ применяются при решении практических задач оптимального проектирования всего, что производится в современном обществе, — особенно после того, как в 1947 году американский математик Дж. Данциг предложил алгоритм решения задач линейного программирования, которому он дал имя симплекс-метода. Это до сих пор наиболее известный и используемый вычислительный алгоритм.
Его эффективность подтверждалась решением сотен тысяч задач линейного программирования. Для сонма прикладников сомнения в эффективности симплекс-метода были равноценны сомнениям в законе тяготения. Но у чистых математиков основания для сомнений были. Ведь в процессе решения симплекс-метод перебирает по специальным правилам некоторое число вариантов. Опасность в том, что это число растет экспоненциально с ростом числа переменных. Почему же симплекс-метод, который в принципе может столкнуться с необходимостью перебора астрономического числа вариантов, на практике с этим не сталкивается?
25 лет потребовалось, чтобы гипотезе о необыкновенной эффективности симплекс-метода пришел конец: появились примеры задач линейного программирования, для которых оптимальное решение симплекс-методом невозможно быстрее, чем за экспоненциально растущее (с ростом параметров задачи) число шагов. Прикладники не беспокоились — они продолжали использовать симплекс-метод и получать оптимальные решения за приемлемое время. Но математики не были готовы смириться со странной ситуацией: существуют задачи, на которых симплекс-метод не должен сходиться, но почему-то сходится. Как же устроен класс задач линейного программирования: то ли доля сложных задач в нем мала, то ли этот класс задач полиномиально разрешим, но симплекс-метод не обеспечивает полиномиальных оценок трудоемкости. В последнем случае следует искать другой алгоритм, который любую задачу из класса задач линейного программирования будет решать за время, растущее не быстрее полинома от числа переменных и ограничений.
О разрешимости задач в линейном программировании
Соученик Л.А. Левина А.С. Немировский после защиты кандидатской диссертации оказался в теоретическом отделе одного московского "почтового ящика". Начальник отдела профессор Д.Б. Юдин предложил новичку исследовать "сложность задач математического программирования". Проблемами алгоритмической сложности Немировский дотоле не интересовался, а дискретную математику вообще не жаловал. Потому и обратился к тому, что понимал: подходу к оценке сложности непрерывных задач, предложенному проф. Н.С. Бахваловым для оценок скорости сходимости решений дифференциальных и интегральных уравнений.
Если в компьютерной науке оценки сложности носили дискретный характер (число шагов вычислений, количество элементов в схемах или букв в формулах), то методология Бахвалова предполагала, что численный метод решения может быть связан с накоплением информации о решаемой задаче — путем задания "оракулу" вопросов из заданного множества. Минимально возможное количество вопросов, достаточных, чтобы сформировать решение с заданной точностью, как раз и оценивало "сложность" задачи. Подход предполагает, что "оракул" не всеведущ, то есть не может сразу указать решение задачи (ему можно задавать только локальные вопросы типа: "Куда пойти на следующем шаге?"). За методом, предложенным Немировским, в мире впоследствии закрепилось название "метод эллипсоидов".
После того как эти результаты Немировского были опубликованы, Л.Г. Хачиян, молодой математик, работавший в Вычислительном центре АН СССР, заметил, как их можно "подать" наиболее впечатляющим образом. Он показал, что на основании метода эллипсоидов можно доказать полиномиальную разрешимость задач линейного программирования. Вскоре после опубликования работы Хачияна американская New York Times вышла со статьей, озаглавленной "Русская атомная бомба в линейном программировании". В 1982 году Mathematical Optimization Society and the American Mathematical Society наградили А. Немировского, Л. Хачияна и Д. Юдина премией Фалкерсона (Fulkerson Prize) за статьи, в которых содержались результаты, позволившие получить полиномиальный алгоритм для задач линейного программирования.
В Штатах сразу же после появления информации об оптимальном методе развернулась работа по доведению алгоритмов "эллипсоидального типа" до программной реализации, способной соперничать с лучшими версиями симплекс-метода. Уже в новом тысячелетии были продемонстрированы примеры задач, для которых алгоритмы этого класса работают в сотни раз эффективнее стандартных реализаций симплекс-метода. А в американских учебниках по исследованию операций алгоритмы, основанные на методе эллипсоидов, без обиняков называют "методом Кармаркара" по имени американского математика, который усовершенствовал программную реализацию метода, изложенную в статье Хачияна.
Оптимальность vs робастность
В 1997 году А.С. Немировским сделан решающий шаг, который не удался его предшественникам (в том числе и нобелевскому лауреату Г. Саймону). Он впервые обнаружил, что задачи линейного программирования могут обладать особенностями, крайне неприятным для пользователя. Разница (даже в доли процента) между данными, которыми оперирует оптимальный алгоритм решения, и теми, которые будут иметь место в случае применения полученного решения, может привести к тому, что в большой доле задач полученное оптимальное решение окажется не только не оптимальным, но и вообще недопустимым, то есть будут нарушены заданные ограничения.
Следовательно, доверять оптимальному решению можно лишь, если заранее определить подверженность задачи "болезни неопределенности" — и найти "лекарство". Немировский предложил математически строгий способ, который обеспечивает надежность применения оптимального решения, назвав его "робастная оптимизация" (англ. robust-- надежный, устойчивый, грубый). Этот способ менял и традиционную постановку задач линейного программирования, и алгоритм ее решения. Задача решалась при дополнительном условии, что все коэффициенты могут принимать любые значения из некоторого множества — множества неопределенности. Какими бы ни оказались коэффициенты, если они принадлежат множеству неопределенности, решение обязательно будет допустимым (точнее, робастно допустимым). Робастная оптимизация находит оптимальное решение только среди всех робастно допустимых решений.
Введение множества неопределенностей в стандартную задачу линейного программирования превращает ее в некоторое множество задач. А значит, стандартные методы решения задач линейного программирования непригодны. Но такая задача может быть решена как задача "выпуклой оптимизации", а для этого класса Немировским ранее уже были получены оптимальные алгоритмы решения (метод эллипсоидов). Это открывало дорогу для широкого применения методов робастной оптимизации в прикладных задачах. Сразу после опубликования первых результатов идеи робастности были подхвачены всеми, кто на практике или в теории занимался теорией оптимизации. Было ощущение, что именно такого подхода специалисты ожидали долгие годы.
Любой прикладник мечтает, чтобы полученное им решение обеспечивало максимум возможного в реальном мире. До сих пор математика предлагала ему этот реальный мир задать некоторым вероятностным распределением и максимизировать ожидаемый результат. Хотя все понимали, что задание такого распределения в большинстве реальных ситуаций не более чем фикция. Робастная оптимизация гарантирует максимум возможного при самом неблагоприятном стечении обстоятельств. Если вдуматься, это единственное, на что можно всерьез рассчитывать в реальном мире, не будучи патологическим оптимистом. И хотя за все приходится платить, в данном случае природа оказалась "не злонамеренна" — плата за гарантированно допустимое решение вполне приемлема как по сложности алгоритма (он полиномиальный), так и по потере в качестве решения, которое во многих случаях лишь на единицы процентов хуже номинальных оптимальных решений.
Робастная оптимизация — наиболее последовательная из существующих сегодня методология преодоления неопределенности будущего. Признавая невозможность победить неопределенность, мы согласны платить, но платим справедливую цену.
Одним из первых больших проектов, в где была испробована робастная оптимизация, стал проект ЕС по оптимальному распределению водных ресурсов в крупных городах. Нужно было выбрать такой режим насосных станций, чтобы он обеспечил минимальную стоимость энергии и учел некоторые гидравлических ограничений (например, давление). Почти все данные в реальных гидравлических системах (истинные диаметры труб, электрические и гидравлические характеристики насосов, поведение потребителей) — это трудно измеряемые и предсказываемые величины.
Немировский считал, что решение можно найти с помощью точных методов робастной оптимизации. Дело в том, что многие практические задачи оптимизации обладают достаточно большим множеством "почти оптимальных" решений. Игнорируя неопределенность и решая задачу с номинальными данными, такие методы, как симплекс, получают в качестве решения граничную точку допустимого множества, которая часто становится недопустимой при возмущении данных. Робастные методы выбирают в допустимом множестве не граничное, а внутреннее решение, и, если множество "почти оптимальных" решений номинальной задачи достаточно массивно, близкое к оптимальному внутреннее решение всегда будет робастно допустимым [рис. ].
Робастное решение — всегда допустимое — Задача линейного программирования может быть представлена в виде многогранника ограничений. Область внутри многогранника — это множество допустимых решений, а вне его — область недопустимых решений, так как нарушаются условия задачи. Известно, что оптимальное решение всегда находится в одной из вершин многогранника, и симплекс-метод обходит вершины в поиске оптимального решения. Но малейшее отклонение от условий может допустимое решение превратить в недопустимое. В отличие от симплекса, робастное решение ищется как внутреннее и поэтому всегда остается допустимым, хотя может быть несколько хуже истинно оптимального решения.
Фото: Галя Панченко
Численное моделирование показало, что по затрачиваемой энергии метод вполне сопоставим с эвристическими подходами, но, в отличие от них, точно указывает, в каком интервале неопределенности исходных данных он робастно допустим. Задача оптимального распределения водных ресурсов — типичная задача управления любыми ресурсами: и распределение энергоресурсов в электрических сетях, и выбор оптимальных биржевых портфелей.
Область практического применения робастной оптимизации давно вышла за пределы линейного программирования и включает в себя, например, оптимизацию инженерных конструкций и нанофотонный инжиниринг. В 2003 году Institute for Operations Research and the Management Sciences за работы по робастной оптимизации наградил А.С. Немировского премией Дж. Неймана (John von Neumann Theory Prize).
Как можно ошибиться на 15%, сделав неверное допущение в 1%
Одной из причин существенного влияния малых воздействий на результат являются "уравнения баланса", наиболее общий тип уравнений, как в экономике, так и во многих физических процессах.
Вот простой пример. Пусть работа автозавода описана линейной моделью, в которой показателем качества является годовая прибыль. Предположим, что в соответствующей модели оптимизации (в задаче линейного программирования) необходимо максимизировать прибыль. Среди различных линейных неравенств обязательно возникнет уравнение баланса следующего вида:
(количество проданных за год автомобилей) х (средняя цена одного проданного автомобиля) — (количество произведенных за год автомобилей) х (себестоимость производства одного автомобиля) <= годовой прибыли.
Предположим, за год было произведено 200 000 автомобилей и себестоимость производства каждого составляет 10 000 условных единиц. Анализ рынка показал, что можно будет продать не менее 180 000 автомобилей по цене 14 000. Таким образом, предполагаемая прибыль должна быть не меньше 180 000 x 14 000-200 000 x 10 000 = 5,2 x 108 условных единиц. Теперь представим, что в связи с неточностью экономических прогнозов реально было продано не 180 000 автомобилей, а 178 000 (разница чуть больше 1%), а себестоимость каждого из реально произведенных составила 10 200 условных единиц (разница 2%). Реальная прибыль составит 178 000 x 14 000-200 000 x 10200 = 4,5x108 условных единиц. Неточность в 1-2 процента в расчетных данных привела к ошибке в значении предполагаемой прибыли в 15%. А ведь реальные расхождения данных, как правило, превышают один процент.Люди
Леонид Анатольевич Левин — Род. в 1948 г., российский математик. В 1978 году эмигрировал в США, профессор Бостонского университета. Теория вычислительной сложности.
Ричард М. Карп — Род. в 1935 г., американский математик. Теория вычислительной сложности, биоинформатика.
Аркадий Семенович Немировский — Род. в 1947 г., российский математик, доктор физико-математических наук, работает в ЦЭМИ РАН. Автор метода эллипсоидов и робастной оптимизации.
Леонид Витальевич Канторович — 1912-1986, российский математик и экономист. Академик, Нобелевская премия по экономике 1975 года. Линейное программирование, теория оптимального распределения ресурсов.
Джордж Бернард Данциг — 1914-2005, американский математик, автор симплекс-метода. Линейное программирование.
Тьяллинг Купманс — 1910-1985, американский математик и экономист голландского происхождения. Нобелевская премия по экономике 1975 года. Теория оптимального распределения ресурсов.
Леонид Генрихович Хачиян — 1952-2005, российский математик, доктор физико-математических наук. В 1989 году эмигрировал в США. Автор полиномиального алгоритма для задач линейного программирования.