マルティン・グレーチェル：難問の幾何学

1982年、離散数学における最も権威ある栄誉であり、アメリカ数学会と数理最適化学会が共同で授与するファルカーソン賞が、楕円体法に関する研究に授与された。マルティン・グレーチェル（Martin Grötschel）がラースロー・ロヴァース（László Lovász）およびアレクサンダー・シュライバー（Alexander Schrijver）と共に発展させたその成果は、組合せ最適化に対する理論家の考え方を決定づけるものとなった。すなわち、非常に広範なクラスの問題において、「分離（separation）」が可能であること——ある点が集合の内部にあるかを判定し、そうでない場合はそれを証明する超平面を生成すること——は、その集合上で「最適化（optimization）」を行うことと計算量的に等価であるということである。最適化と分離は、異なる衣をまとった同一の難問なのである。

シュヴェルムからボンへ

グレーチェルは1948年9月10日、ノルトライン＝ヴェストファーレン州の工業の小さな町シュヴェルムで生まれた。1969年からボーフム大学で数学（副専攻は経済学）を学び、1973年にディプロムを取得した。その後、ボンのボン大学へ研究助手として移り、9年間在籍した。1977年、ドイツの離散最適化の創始者の一人であるベルンハルト・コルテ（Bernhard Korte）の下で博士号を取得し、1981年にはボンでオペレーションズ・リサーチの教授資格（ハビリタシオン）を得た。

博士論文の研究は、この分野で最も有名な未解決の難問に直接切り込むものだった。グレーチェルは、巡回セールスマン問題に対するカット平面法を発展させた。これは、困難な組合せ問題を連続的な問題に緩和し、易しいバージョンを解き、緩和によって生じた分数解を切り落とす不等式を追加し、解が整数になるまで繰り返すというアプローチである。この手法は、どの不等式を追加すべきかを知ることに全てがかかっており、その探求である多面体組合せ論は彼のキャリアの中心となった。問題の実行可能解の凸包の幾何学を理解すること、それが難しさの真の所在だからである。

楕円体

楕円体法は、線形計画問題が多項式時間で解けることを示す最初の証明として1979年に西側に到来した。それは理論的には支配的であったが、実際には単体法よりもはるかに遅く、実用上の価値はなかった。グレーチェル、ロヴァース、シュライバーが認識したのは、その真の力はアルゴリズムとしてではなく、証明装置としてにあるということだった。

楕円体法は明示的な制約リストではなく分離オラクルのみを必要とするため、制約に違反しているか効率的に認識できれば、指数関数的に多くの面を持つ多面体上でも最適化が可能である。この観察は、一連の未解決問題を一挙に解決済みのものへと変えた。組合せ問題の全ファミリーが、直接的なアルゴリズムを誰も構成することなく、多項式時間で解けることが示されたのである。その枠組みは、後にこの分野の標準的な参考文献となったモノグラフ『Geometric Algorithms and Combinatorial Optimization』において詳細に記述された。1982年のファルカーソン賞はこの研究を評価したものであり、1991年にはジョージ・B・ダンツィグ賞が続いた。

ベルリン

グレーチェルは1982年から1991年までアウクスブルク大学で応用数学の教授を務め、その後ベルリンへ移り、残りの職業人生をそこで過ごした。1991年にベルリン工科大学（Technische Universität Berlin）の情報技術の正教授となり、同年、ツゼ研究所ベルリン（ZIB）の副所長に就任、2012年にはZIBの所長となり2015年まで務めた。2015年から2020年までベルリン・ブランデンブルク科学アカデミーの会長を務め、2011年からはミュンヘン工科大学の卓越客員教授も務めている。

ベルリンでの数十年、彼は理論を捨て去ることなく、応用へと重点をシフトした。彼はDFG研究センター「マテオン（Matheon）」を共同設立し会長を務めた。この機関は、産業やインフラの問題は単に古い数学を消費するだけでなく、真に新しい数学を生み出すという前提に基づいて構築された。彼の応用研究は、生産計画、公共交通のスケジュール、エネルギーシステム、物流にまで及ぶ。これらは、組合せスケジュールにおいて数パーセントの改善が多額の金銭と測定可能な量の炭素削減に値する領域である。

彼はまた、異例なほど活動的な機関建設者でもあった。1993年から94年にかけてドイツ数学会会長、2007年から2014年まで国際数学連合の事務総長、2011年から2015年までベルリンのアインシュタイン財団会長を務めた。『Handbook of Combinatorics』の共同編集も行った。受賞歴も多い。1990年のカール・ハインツ・ベックルツ賞、1995年のドイツで最も価値のある研究賞であるゴットフリート・ヴィルヘルム・ライプニッツ賞、2004年のEUROゴールドメダル、2006年のジョン・フォン・ノイマン理論賞、2009年から10年頃のSIAMフェローシップおよびSIAM殊勲奉仕賞などである。彼は4つの大学から名誉博士号を授与されており、全米工学アカデミー、レオポルディーナ、acatech、アカデミア・エウロパエア、中国科学院を含む7つの学会の会員である。

なぜマルティンは天才と呼ばれるのか

この言葉は彼の分野において彼を評する際に使われるものではない。誠実な評価はより異なり、より有用である。グレーチェルは第一級の数学者であり、その卓越性は外部からの評価によって極めてよく文書化されている。最適化における3つの最高賞であるファルカーソン賞、ダンツィグ賞、フォン・ノイマン賞に加え、ライプニッツ賞の受賞、そしてアメリカ、ドイツ、中国の各国家アカデミーへの所属は、現役の数学者が積み重ねるものとしては極めて稀な、持続的な技術的卓越性の証跡である。

その特定の資質は、華やかというよりも建築的である。楕円体法の洞察が最も明快な例である。その功績は新しいアルゴリズムを発明したことではなく、既存の実用性のないアルゴリズムが一般的な等価性をエンコードしていることを認識し、その等価性から主題全体にわたる問題を解決する装置を抽出した点にある。それは特異な精神である。ツールを見て定理を見るような精神である。同じ本能が多面体プログラムにも見られ、離散的な探索を凸体の形状に関する問題へと変換する。また「マテオン」でも、産業スケジュール問題を数学の応用ではなく、数学の源泉として扱うという動きに見られる。

反論は単純明快である。グレーチェルの中心的な成果は、主にロヴァースやシュライバーといった共同研究者との共有であり、分離と最適化の等価性を彼のみに帰することは記録を歪めることになる。彼の名声は専門分野に限られており、組合せ最適化やオペレーションズ・リサーチの外では本質的に無名であり、彼の名を冠した結果は一般的な数学語彙には存在しない。彼のキャリアの後期の大部分は、証明よりも運営、資金調達機関、学会の会長職に費やされた。記録が示すのは称賛されるべき天才ではなく、より正確に価値のあるもの、すなわち一流の成果の積み重ね、現在もこの分野で日常的に使われている枠組み、そして個別の定理を超えて残るベルリンでの制度的な遺産である。

遺産

分離と最適化の等価性は今や標準的な知識となり、この分野の大学院生全員に教えられ、新しい緩和のクラスが提案されるたびに引用される。彼が確立に貢献した多面体アプローチは、航空機の航路決定、列車のスケジュール、電力網の計画を行う商用の整数計画ソルバーの基盤となっている。そしてZIB、マテオン、ベルリンの最適化スクールは現場における制度的事実であり、困難な実際的問題と深遠な数学的問題は、二つの側面から見た同じ対象であるということを彼から学んだ人々によって運営されている。