Непрерывная релаксация не чудодейственное средство: она по-прежнему не предлагает нам эффективный способ приблизиться к действительно оптимальным решениям, а только лишь к их приближенным значениям. Но получить в два раза больше писем или внедрить в два раза больше пожарных расчетов будет гораздо лучше, чем использовать неоптимизированные альтернативы.
Штраф за превышение скорости: Лагранжева релаксация
Виззини: Непостижимо.
Иниго Монтойя: Ты постоянно используешь это слово. Не думаю, что оно означает то, что ты думаешь, что оно означает.
Фильм «Принцесса-невеста»
Однажды в детстве Брайан полдня жаловался матери на все, что ему приходилось делать: уроки, работу по дому… «С юридической точки зрения ты не обязан ничего делать, – ответила ему мать. – Ты не обязан слушаться учителей. Ты не обязан слушаться меня. Ты не обязан даже подчиняться закону. Но у любого поступка есть последствия, и только тебе решать, когда ты захочешь с этими последствиями столкнуться».
Детский мозг Брайана взорвался. Это был мощный посыл, пробуждающий ощущение силы, ответственность, моральные суждения. Но было это также и кое-что другое: эффективная методика вычислений под названием Лагранжева релаксация. Идея Лагранжевой релаксации проста. Задача оптимизации состоит из двух частей: правила и оценка производительности. В рамках Лагранжевой релаксации мы берем некоторые из ограничивающих условий задачи и внедряем их в систему количественных показателей. Таким образом, мы превращаем невозможное в затратное. (В задаче со свадебной рассадкой, к примеру, мы можем убрать ограничение, что за каждым столом может сидеть максимум 10 человек, и допустить «перенаселение» за столами с вероятностью слегка потолкаться локтями.) Когда условие задачи оптимизации гласит «Делай только так, а не то…», Лагранжева релаксация вопрошает: «А не то что?» Однажды мы позволяем себе выйти за границы (хотя бы чуть-чуть, пусть даже за счет высоких расходов) – и вот уже задачи становятся разрешимыми.
Лагранжевы релаксации занимают огромную часть во всей теоретической литературе, посвященной задаче коммивояжера и другим сложным задачам в области информатики. Кроме того, они служат важным инструментом для ряда практических случаев. Вспомним, к примеру, Майкла Трика из Университета Карнеги – Меллон, который, как мы помним из главы 3, отвечал за расписание Главной лиги бейсбола и ряд конференций Национальной ассоциации студенческого спорта. О чем мы не упоминали, так это о том, как он это делает. Составление расписания на каждый год представляет собой гигантскую задачу дискретной оптимизации, слишком сложную для того, чтобы компьютер мог решить ее методом перебора. Поэтому каждый год Трик и его коллеги из группы спортивного планирования прибегают к помощи Лагранжевой релаксации. Каждый раз, когда вы включаете телевизор или занимаете место на трибуне стадиона, помните, благодаря чему состоялась встреча этих двух команд на этой площадке в этот конкретный вечер. Ну хорошо, необязательно это будет оптимальный спортивный матч. Но близко к тому. И поблагодарить за это нам стоит не только Майкла Трика, но и французского математика XVIII века Жозефа Луи Лагранжа.
При планировании спортивного сезона Трик обнаружил, что непрерывная релаксация, о которой мы вели речь ранее, не облегчает ему задачу. «Если в конечном итоге вы получаете дробные результаты, это не приводит ни к чему хорошему». И ладно, если дробные результаты получаются у нас в ходе решения задачи с пожарными расчетами или приглашениями – там мы можем округлить их до целых чисел в случае необходимости. Но в спорте целочисленные ограничения слишком сильны: сколько команд будет играть, сколько игр пройдет в общем счете и сколько раз каждая команда будет играть против других команд. «И тут уже мы не можем расслабиться. Мы действительно должны придерживаться основополагающей [дискретной] части модели».
Тем не менее надо же как-то справиться со сложностью задачи. Таким образом, «нам приходится работать с лигами, чтобы ослабить некоторые из ограничений, которые могут у них быть», – объясняет Трик. Число таких ограничений при планировании спортивного сезона поистине огромно, и оно включает в себя не только требования, проистекающие из базовой структуры лиги, но и всякого рода специфические запросы и сомнения. Некоторые лиги хотят играть только во второй половине сезона и только в домашних, а не выездных матчах. Другие лиги это категорически не устраивает, но они тем не менее требуют, чтобы команды не играли вместе снова, пока не сыграют со всеми остальными по разу. Некоторые настаивают, чтобы противостояние знаменитых команд имело место в финальной игре сезона. Некоторые команды не могут играть домашние матчи в определенные дни, потому что в эти даты арены уже заняты под другие мероприятия. В случае с баскетбольными играми Национальной ассоциации студенческого спорта Трику пришлось также принять во внимание требования телевизионных каналов, транслирующих игры. Телеканалы за год предугадывают, какие из матчей станут «А-играми» и «В-играми», то есть играми, которые привлекут наибольшую аудиторию (матч Duke против UNC, например, уже много лет является А-игрой). Каналы, таким образом, планируют одну А-игру и одну В-игру в неделю, но ни в коем случае не одновременно, чтобы не расколоть зрительскую аудиторию.
Неудивительно, что, столкнувшись со всеми этими требованиями, Трик понял, что составление спортивного графика зачастую возможно только при условии смягчения этих ограничений.
Как правило, когда люди приходят к нам со спортивным расписанием, они начинают качать права… «Мы никогда не будем делать x и никогда не будем делать y!» Тогда мы смотрим на их расписание и говорим: «Ну, в прошлом году вы дважды делали x и трижды делали y». Они: «О, ну ладно, что ж. Тогда мы ни за что не будем делать z». И мы возвращаемся еще на год назад… В целом мы понимаем: они думают, что есть что-то, чего они никогда не будут делать и что делают другие. В бейсболе принято считать, что The Yankees и The Mets никогда не играют домашних матчей в одно и то же время. Но это неправда. И никогда не было правдой. Они проводят как минимум три, а то и шесть домашних матчей за год в один и тот же день. Но для всего сезона в целом 81 домашний матч для каждой команды – это довольно мало. Неудивительно, что люди забывают о них.
Порой приходится прибегать к дипломатическим тонкостям, но Лагранжева релаксация – территория, где запрещенное становится наказуемым, а немыслимое нежелательным, – позволяет добиться прогресса. Как говорит Трик, вместо того чтобы тратить миллиарды лет на поиски несуществующего идеального решения, лучше использовать метод Лагранжевой релаксации и позволить себе задать вопрос наподобие: «Как близко вы можете подобраться к такому решению?» Как выясняется, достаточно близко, чтобы сделать счастливым каждого – лиги, школы, телеканалы – и разжигать огонь March Madness год за годом.
Учимся релаксации
Проблемы оптимизации (с одной стороны – цели, с другой стороны – правила), возможно, самый распространенный вид вычислительных задач, с которыми мы имеем дело. И задачи дискретной оптимизации, где наши варианты сводятся к строгому выбору «или/или» без каких-либо средних значений, – наиболее типичные из них. Здесь информатика выносит обескураживающий вердикт. Многие проблемы дискретной оптимизации действительно сложны. Самые светлые головы этой области пасовали в попытках найти короткий путь к идеальным решениям, посвящая гораздо больше времени доказательствам того, что таких путей не существует, чем поиску оных.
