Мартин Гретшель: Геометрия сложных проблем

В 1982 году премия Фалкерсона (Fulkerson Prize) — самая строгая награда в области дискретной математики, присуждаемая совместно Американским математическим обществом и Обществом математической оптимизации, — была вручена за работу над методом эллипсоидов (ellipsoid method). Результат, стоящий за этим, разработанный Мартином Гретшелем (Martin Grötschel) совместно с Ласло Ловасом (László Lovász) и Александром Схрейвером (Alexander Schrijver), установил принцип, который до сих пор определяет то, как теоретики мыслят о комбинаторной оптимизации: для очень широкого класса задач умение отделять (отвечать на вопрос, лежит ли точка внутри множества, а если нет, то построить гиперплоскость, доказывающую это) вычислительно эквивалентно умению оптимизировать на этом множестве. Оптимизация и разделение — это одна и та же трудность под разными названиями.

От Швельма до Бонна

Гретшель родился 10 сентября 1948 года в Швельме (Schwelm), небольшом промышленном городе в земле Северный Рейн-Вестфалия. С 1969 года он изучал математику с дополнительной специализацией по экономике в Рурском университете Бохума (University of Bochum), в 1973 году получил диплом, а затем перешел в Боннский университет (University of Bonn) на должность научного сотрудника, где проработал девять лет. Степень доктора он получил в 1977 году под руководством Бернхарда Корте (Bernhard Korte), одного из основателей немецкой дискретной оптимизации; хабилитацию в области исследования операций он получил в Бонне в 1981 году.

Докторская работа была посвящена самой известной и труднорешаемой задаче дисциплины. Гретшель продвинул метод отсекающих плоскостей для задачи коммивояжера (Traveling Salesman Problem) — подход, при котором сложная комбинаторная задача релаксируется до непрерывной, решается ее упрощенная версия, а затем добавляются неравенства, отсекающие дробные ответы, полученные в результате релаксации, до тех пор, пока решение не станет целочисленным. Успех этой техники зависит от выбора добавляемых неравенств, и поиск этих неравенств, ставший многогранной комбинаторикой (polyhedral combinatorics), стал центром его карьеры: понимание геометрии выпуклой оболочки допустимых решений задачи, потому что именно в этой геометрии и заключается основная сложность.

Эллипсоиды

Метод эллипсоидов появился на Западе в 1979 году как первое доказательство того, что задачи линейного программирования решаемы за полиномиальное время. На практике он был и остается неэффективным — гораздо медленнее симплекс-метода, над которым он теоретически доминировал. Гретшель, Ловас и Схрейвер увидели, что его реальная сила не в том, чтобы быть алгоритмом, а в том, чтобы служить инструментом доказательства.

Поскольку методу эллипсоидов нужен только оракул отделения (separation oracle), а не явный список ограничений, он может оптимизировать многогранники с экспоненциально большим количеством граней, при условии, что вы можете эффективно распознать нарушенное ограничение. Это наблюдение мгновенно превратило груду открытых вопросов в решенные: целые семейства комбинаторных задач оказались решаемыми за полиномиальное время без необходимости построения для них прямого алгоритма. Этот каркас был полностью изложен в монографии Geometric Algorithms and Combinatorial Optimization, которая стала одним из стандартных справочников в области. В 1982 году эта работа была отмечена премией Фалкерсона, а в 1991 году — премией Джорджа Б. Данцига (George B. Dantzig Prize).

Берлин

Гретшель занимал кафедру прикладной математики в Аугсбургском университете (University of Augsburg) с 1982 по 1991 год, а затем переехал в Берлин, где провел остаток своей карьеры. В 1991 году он стал профессором информационных технологий в Берлинском техническом университете (Technische Universität Berlin) и в том же году — вице-президентом Института Цузе в Берлине (Zuse Institute Berlin, ZIB), а в 2012 году возглавил институт, оставаясь на этом посту до 2015 года. С 2015 по 2020 год он был президентом Берлинско-Бранденбургской академии наук (Berlin-Brandenburg Academy of Sciences and Humanities), а с 2011 года является почетным профессором Мюнхенского технического университета (Technical University of Munich).

Десятилетия в Берлине сместили его акцент в сторону приложений, не отказываясь от теории. Он стал сооснователем и председателем исследовательского центра DFG Matheon, созданного на основе идеи о том, что промышленные и инфраструктурные проблемы порождают по-настоящему новую математику, а не просто потребляют старую. Его прикладная работа охватывает планирование производства, составление расписаний общественного транспорта, энергетические системы и логистику — области, где улучшение комбинаторного расписания на несколько процентов означает огромные деньги и измеримое сокращение выбросов углерода.

Он также был необычайно активным институциональным строителем. Он занимал пост президента Немецкого математического общества (German Mathematical Society) в 1993–94 годах, генерального секретаря Международного математического союза (International Mathematical Union) с 2007 по 2014 год и председателя фонда Einstein Foundation Berlin с 2011 по 2015 год. Он был соредактором Handbook of Combinatorics. Награды накапливались: премия Карла Хайнца Бекуртса в 1990 году, премия Готфрида Вильгельма Лейбница (Gottfried Wilhelm Leibniz Prize) — самая престижная исследовательская премия Германии — в 1995 году, золотая медаль EURO в 2004 году, премия Джона фон Неймана по теории (John von Neumann Theory Prize) в 2006 году, а также звание фелло SIAM и премия за выдающиеся заслуги SIAM около 2009–10 годов. Он имеет почетные докторские степени четырех университетов и является членом семи академий, включая Национальную инженерную академию США, Леопольдину (Leopoldina), acatech, Academia Europaea и Китайскую академию наук.

Почему Мартина называют гением

Это слово не используется в его профессиональной среде, и честное описание более уместно и полезно: Гретшель — математик первого ранга, чьи выдающиеся достижения исключительно хорошо документированы внешними экспертными оценками. Три высшие награды в области оптимизации (Фалкерсона, Данцига, фон Неймана), плюс премия Лейбница и членство в национальных академиях США, Германии и Китая составляют послужной список непрерывного технического мастерства, который удается накопить лишь очень немногим математикам.

Его специфическое качество скорее архитектурное, чем блестящее. Инсайт метода эллипсоидов — ярчайший пример: достижение заключалось не в изобретении нового алгоритма, а в распознавании того, что существующий, практически бесполезный алгоритм кодирует общую эквивалентность, и в извлечении из этой эквивалентности инструмента для решения вопросов во всей предметной области. Это особый тип ума — тот, что смотрит на инструмент и видит теорему. Та же интуиция проявляется в многогранной программе, где задача состоит в том, чтобы превратить дискретный поиск в вопрос о форме выпуклого тела, и снова в Matheon, где промышленная задача планирования рассматривается как источник математики, а не просто объект ее применения.

Контраргумент прост и заслуживает упоминания. Основные результаты Гретшеля были получены совместно с коллегами, главным образом Ловасом и Схрейвером, и было бы искажением фактов приписывать эквивалентность разделения и оптимизации только ему. Его известность ограничена его специальностью; за пределами комбинаторной оптимизации и исследования операций он практически неизвестен, и ни один результат не носит его имени в общематематическом словаре. Значительная часть его поздней карьеры была посвящена административной работе, руководству фондами и обществами, а не доказательству теорем. Записи свидетельствуют не о прославленном гении, а о чем-то более точном: карьере первоклассных результатов, каркасе, который область использует ежедневно, и институциональном наследии в Берлине, которое переживет любую отдельную теорему.

Наследие

Эквивалентность разделения и оптимизации сегодня является стандартным инструментом, которому обучают каждого аспиранта в этой области, и к которому обращаются всякий раз, когда предлагается новый класс релаксаций. Многогранный подход, который он помог установить, лежит в основе коммерческих решателей целочисленного программирования, которые управляют авиаперевозками, составляют расписания поездов и планируют электросети. А Институт Цузе, Matheon и берлинская школа оптимизации — это институциональные факты, в которых работают люди, научившиеся у него тому, что сложная практическая задача и глубокая математическая задача часто являются одним и тем же объектом, увиденным с двух сторон.