Линейное программирование (ЛП) - это задача оптимизации линейной функции при линейных же на нее ограничениях. В наиболее простой переформулировке она сводится к тому, разрешима ли данная система линейных неравенств. Эта кажущаяся абстрактной задача имеет огромное количество применений и возникает в самых разных оптимизационных приложениях. В клиентах у крупнейшего производителя софта для решения задач ЛП - французской компании - ходят такие индустриальные гиганты, как Siemens, IBM, Visa International, France Telecom, United Airlines и многие другие. Говорят, что когда-то советская государственная программа развития Госплана фактически сводилась к тому, чтобы закодировать всю экономику СССР в виде огромной задачи линейного программирования, а потом ее решить и получить оптимальный план[Об этом Л. В. Канторович говорил в своей Нобелевской лекции. Кстати, векторы, лежащие в ограниченном задачей многограннике, в русской терминологии до сих пор называют планами].
Хотя о пользе решения систем линейных неравенств размышлял еще Фурье, впервые о применениях ЛП заговорили во второй четверти XX века. Начавшиеся исследования сразу же привели к успеху: по всей видимости, независимо друг от друга американец Джордж Данциг (George Dantzig) и советский математик Леонид Витальевич Канторович пришли (для разных, но эквивалентных формулировок исходной задачи) фактически к одному и тому же результату. Этот результат называется сейчас симплекс-методом; суть его - в обходе вершин соответствующего задаче многогранника в поиске оптимума. Симплекс-метод прост как для математического интуитивного понимания, так и для реализации, и преподается ныне в базовых вузовских курсах оптимальных задач. Важность его столь велика и бесспорна, что после того, как работы Канторовича были опубликованы, его приоритет доказан, а сам математик начал активно пропагандировать применение оптимизационных задач на практике, Л. В. Канторович получил Нобелевскую премию - по экономике, разумеется.
Симплекс-метод был прост и понятен, но оказался экспоненциальным - для разных эвристик выбора следующей вершины обхода исследователи сумели построить набор задач, для решения которых симплекс-методу было необходимо экспоненциально большое число итераций. И все же долгое время симплекс-метод был даже теоретически лучшим известным алгоритмом для решения задач линейного программирования. Однако в конце 1970-х годов здесь состоялся один из самых знаменитых прорывов в теории сложности: Л. Г. Хачиян[Как я узнал во время подготовки статьи, 29 апреля 2005 года Леонид Генрихович, в последние годы работавший в США, скоропостижно скончался] (везло нашим соотечественникам на фундаментальные открытия в этой области) построил алгоритм, который решает задачу линейного программирования за полиномиальное число шагов - так называемый метод эллипсоидов Хачияна. Суть алгоритма в том, чтобы окружить данный многогранник эллипсоидом, а затем постепенно сжимать этот эллипсоид; оказывается, на каждом этапе объем эллипсоида уменьшается в константное число раз.
Казалось бы, радость практиков должна быть беспредельной: полиномиальный алгоритм мог бы стать новым стандартом программирования. Но увы. Алгоритм Хачияна не просто плох, он безнадежен на практике. Существуют задачи размером в 50 переменных, для которых требуются более 24 тысяч итераций метода Хачияна, причем итерации эти отнюдь не тривиальны (хоть и полиномиальны, конечно). Количество итераций симплекс-метода в таких случаях исчисляется сотнями, если не десятками, и пересчет каждой из них гораздо проще. Метод эллипсоидов несравним с симплекс-методом: последний хоть и экспоненциален в худшем случае, однако на практике справляется с задачами ЛП многократно лучше. Все промышленные (да и кустарные) реализации решения ЛП основаны на симплекс-методе и его вариантах (которых - столь же экспоненциальных, сколь и их прародитель - уже накопилось довольно много).
Кстати, симплекс-метод для решения ЛП тоже отнюдь не стоит на месте, и производительность софта прирастает не только благодаря закону Мура. Один из основателей компании ILOG Роберт Биксби (Robert E. Bixby) рассказывал, что как-то раз, забавы ради, он взял ILOG 1.0 (выпущенный в середине восьмидесятых) и установил (видимо, перекомпилировал) его на современном компьютере. Разница между ILOG 1.0 и последней версией нынешнего ILOG оказалась видна невооруженным взглядом - свежий софт работал в несколько тысяч раз быстрее.
Метод эллипсоидов Хачияна стал, наверное, самым ярким примером разграничения между теоретически и практически успешными алгоритмами. Алгоритм, имеющий лучшую верхнюю оценку сложности, вовсе не обязательно будет наиболее удачен для практической реализации.
Хотите миллион долларов? Нет проблем. Clay Mathematics Institute давно уже опубликовал список математических «задач на миллион». Решайте любую, ждите два года после публикации (нужно, чтобы никто не нашел ошибок в течение двух лет) - и золотой ключик у вас в кармане[Наш соотечественник, петербуржец Григорий Перельман уже года два как одну из них решил. Но почему-то не хочет публиковать свое решение (которое уже, по всей видимости, общепризнано) в официальных журналах, а интернет-публикации и прочие препринты для доллароносного фонда не годятся (что вполне логично). Но это, опять же, тема для совсем другого разговора]. Кстати, заработаете вы, конечно, гораздо больше миллиона, хоть бы и с учетом налогов: положение человека, решившего великую задачу, весьма завидно.
Одна из этих задач - центральная проблема современной теории сложности: равны ли P и NP? Sapienti sat, а поля этой статьи не настолько шире полей «Арифметики» Диофанта, чтобы вдаваться в подробные объяснения того, что же такое класс задач NP (с P мы уже разобрались - это задачи, которые можно решить полиномиальным алгоритмом). Однако простую переформулировку привести можно: рассмотрим булевскую формулу - то есть формулу, составленную из логических переменных при помощи дизъюнкции, конъюнкции и отрицания (обычно рассматривают формулы в конъюнктивной нормальной форме - это когда формула представлена как большая конъюнкция маленьких дизъюнкций, а отрицания бывают только непосредственно перед входящими в эти дизъюнкции переменными). Внимание, вопрос: существуют ли такие значения переменных, входящих в формулу, что значение всей формулы будет истинным? Такая задача называется задачей пропозициональной выполнимости (satisfiability, SAT). Если вам удастся найти полиномиальный (от длины формулы) алгоритм для решения SAT, вам обеспечен не только миллион долларов, но и вечная память благодарного потомства.
А пока информатика ждет новых гениев, простые (и даже совсем не простые) смертные совершенствуют экспоненциальные алгоритмы для решения этой задачи - ибо она тоже весьма полезна, а кое-где жизненно важна.
Лирическое отступление. Помните знаменитый баг в процессорах Intel, который принес компании несколько миллиардов долларов убытка? Подобные истории до сих пор не редкость. Схемы современных процессоров (и даже отдельных компонентов этих процессоров) настолько сложны, что вручную проверить их соответствие спецификациям не представляется возможным. Оказывается, математически проверка на вшивость базовой схемы из логических компонентов записывается именно в виде SAT, когда решения описывающей схему (точнее - описывающей соответствие схемы модельной схеме или спецификации) формулы соответствуют ошибкам. Невыполнима формула - значит, багов нет, можно запускать в производство.
Сейчас существуют два основных типа алгоритмов для решения SAT: алгоритмы локального поиска, которые начинают с какого-то набора значений (он, конечно, не выполняет всю формулу), а затем модифицируют его, пытаясь последовательно приблизиться к выполняющему набору, и так называемые DPLL-алгоритмы[По именам создателей: Davis, Putnam, Logemann, Loveland; их описание базовых принципов работы этого метода относится к 1968 году], которые обходят дерево всевозможных наборов и выполняют поиск в глубину. Анализ сложности алгоритмов локального поиска, как правило, носит вероятностный характер - ведь нужно начать с какого-то набора, который иначе как случайно выбрать трудно, а от него может зависеть очень многое.
