마르틴 그뢰첼: 난제의 기하학

1982년, 이산 수학 분야에서 가장 엄격한 권위를 자랑하며 미국 수학회와 수학 최적화 학회가 공동으로 수여하는 풀커슨 상(Fulkerson Prize)이 타원체 방법(ellipsoid method)에 관한 연구에 돌아갔습니다. 마르틴 그뢰첼(Martin Grötschel)이 로바스 라슬로(László Lovász), 알렉산더 스흐레이버(Alexander Schrijver)와 함께 개발한 이 결과는 오늘날 이론가들이 조합 최적화를 바라보는 방식을 정립했습니다. 즉, 매우 광범위한 문제 클래스에 대해 '분리(separation)'—한 점이 집합 내부에 있는지 판단하고, 그렇지 않다면 그것을 증명하는 초평면을 제시하는 것—가 계산적으로 해당 집합 위에서 '최적화(optimize)'하는 것과 동등하다는 것입니다. 최적화와 분리는 다른 옷을 입고 있지만 본질적으로 같은 난제입니다.

슈벨름에서 본까지

그뢰첼은 1948년 9월 10일 노르트라인베스트팔렌주의 작은 공업 도시 슈벨름(Schwelm)에서 태어났습니다. 1969년부터 보훔 대학교(University of Bochum)에서 수학을 전공하고 경제학을 부전공하여 1973년 디플롬(Diplom)을 취득했으며, 이후 본 대학교(University of Bonn)로 옮겨 9년간 연구 조교로 근무했습니다. 그는 1977년 독일 이산 최적화의 창시자 중 한 명인 베른하르트 코르테(Bernhard Korte) 밑에서 박사 학위를 받았고, 1981년 본에서 운용 연구(operations research) 분야의 교수 자격(habilitation)을 취득했습니다.

그의 박사 학위 논문은 이 학문 분야에서 가장 유명한 까다로운 문제에 정면으로 도전했습니다. 그뢰첼은 외판원 문제(Traveling Salesman Problem)를 위한 절단 평면법(cutting-plane method)을 발전시켰습니다. 이는 어려운 조합 문제를 연속적인 문제로 완화하고, 쉬운 버전을 해결한 뒤 완화 과정에서 생성된 분수 해를 제거하는 부등식을 추가하며 정수 해가 나올 때까지 반복하는 방식입니다. 이 기술은 어떤 부등식을 추가할지 아는 것에 성패가 달려 있으며, 그 부등식을 찾는 연구인 '다면체 조합론'이 그의 경력 중심이 되었습니다. 이는 문제의 실행 가능한 해들로 구성된 볼록 껍질(convex hull)의 기하학을 이해하는 것으로, 난제는 바로 그 기하학 안에 존재하기 때문입니다.

타원체

타원체 방법은 1979년 선형 계획법이 다항 시간 내에 풀릴 수 있다는 최초의 증명으로 서구에 소개되었습니다. 이 방법은 이론적으로는 지배적이었으나 실제로는 심플렉스 방법(simplex method)보다 훨씬 느려 실용성이 없었습니다. 그뢰첼, 로바스, 스흐레이버가 본 것은 이 방법의 진정한 힘이 알고리즘이 아닌 '증명 도구'로서의 가치에 있다는 점이었습니다.

타원체 방법은 명시적인 제약 조건 목록이 아닌 분리 오라클(separation oracle)만 있으면 되기 때문에, 위반된 제약 조건을 효율적으로 인식할 수만 있다면 지수적으로 많은 면(facet)을 가진 다면체 위에서도 최적화할 수 있습니다. 이 관찰은 한꺼번에 수많은 미해결 문제들을 해결된 문제로 바꾸어 놓았습니다. 즉, 직접적인 알고리즘을 구축하지 않고도 전체 조합 문제 계열들이 다항 시간 내에 풀릴 수 있음이 밝혀진 것입니다. 이 프레임워크는 전문 서적인 Geometric Algorithms and Combinatorial Optimization에 상세히 기술되었으며, 이는 해당 분야의 표준 참고 문헌이 되었습니다. 이 공로로 1982년 풀커슨 상을 받았고, 1991년 조지 B. 단치히 상(George B. Dantzig Prize)이 뒤따랐습니다.

베를린

그뢰첼은 1982년부터 1991년까지 아우크스부르크 대학교(University of Augsburg)에서 응용 수학 교수로 재직하다가 베를린으로 옮겨 남은 경력을 보냈습니다. 그는 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)의 석좌 교수(Distinguished Affiliated Professor)로 활동하고 있습니다.

베를린에서의 수십 년은 그가 이론을 저버리지 않으면서도 응용 분야에 집중하게 된 시기였습니다. 그는 산업 및 인프라 문제가 단순히 기존 수학을 소비하는 것이 아니라 진정으로 새로운 수학을 창출한다는 전제하에 설립된 DFG 연구 센터 마테온(Matheon)을 공동 설립하고 의장을 맡았습니다. 그의 응용 연구는 생산 계획, 대중교통 스케줄링, 에너지 시스템 및 물류에 걸쳐 있으며, 이러한 분야에서 조합 스케줄의 몇 퍼센트 개선은 막대한 금전적 가치와 측정 가능한 양의 탄소 절감 효과를 가져옵니다.

그는 또한 매우 활동적인 기관 건설자이기도 했습니다. 1993~94년 독일 수학회 회장, 2007~2014년 국제 수학 연맹(International Mathematical Union) 사무총장, 2011~2015년 아인슈타인 재단 베를린(Einstein Foundation Berlin) 의장을 역임했습니다. 그는 Handbook of Combinatorics를 공동 편집했습니다. 그는 1990년 칼 하인츠 베쿠르츠 상(Karl Heinz Beckurts Prize), 1995년 독일에서 가장 권위 있는 연구상인 고트프리트 빌헬름 라이프니츠 상(Gottfried Wilhelm Leibniz Prize), 2004년 EURO 골드 메달, 2006년 존 폰 노이만 이론상(John von Neumann Theory Prize), 2009-10년경 SIAM 펠로우 및 SIAM 공로상 등을 수상했습니다. 그는 4개 대학에서 명예 박사 학위를 받았으며, 미국 국립 공학 아카데미, 레오폴디나(Leopoldina), 아카테크(acatech), 유럽 아카데미(Academia Europaea), 중국 과학원을 포함한 7개 아카데미의 회원입니다.

마틴이 천재라 불리는 이유

천재라는 단어는 그가 속한 분야에서 그를 지칭할 때 사용하는 표현이 아닙니다. 더 솔직하고 유용한 묘사는 다음과 같습니다. 그뢰첼은 외부의 평가로 그 탁월함이 매우 잘 입증된 1급 수학자입니다. 최적화 분야 최고 권위의 3개 상(풀커슨, 단치히, 폰 노이만)과 라이프니츠 상 수상, 그리고 미국, 독일, 중국 국립 아카데미의 회원 자격은 매우 극소수의 수학자만이 달성할 수 있는 지속적인 기술적 탁월함의 증거입니다.

그의 특정 자질은 화려하기보다는 건축적인 것입니다. 타원체 방법의 통찰이 가장 명확한 예입니다. 그의 성취는 새로운 알고리즘을 발명한 것이 아니라, 기존의 실제로는 쓸모없던 알고리즘이 일반적인 동등성을 담보하고 있음을 인식하고, 그 동등성으로부터 전체 학문 분야의 문제를 해결하는 기계를 추출해낸 것입니다. 이것은 도구를 보면서 정리를 보는 특별한 종류의 지성입니다. 같은 본능이 다면체 프로그램에서도 나타나는데, 이는 이산적 탐색을 볼록체의 모양에 관한 문제로 전환하는 방식이며, 마테온에서도 산업적 스케줄링 문제를 수학의 응용처가 아닌 수학의 원천으로 다루는 방식으로 나타납니다.

반론 또한 명확하며 언급할 가치가 있습니다. 그뢰첼의 핵심 성과는 로바스와 스흐레이버를 비롯한 공동 연구자들과 공유되는 것이며, 분리-최적화 동등성을 그 혼자만의 공으로 돌리는 것은 기록을 왜곡하는 것입니다. 그의 명성은 자신의 전문 분야에 국한되어 있습니다. 조합 최적화와 운용 연구 외부에서는 사실상 알려지지 않았으며, 그의 이름이 붙은 결과가 일반 수학 용어 사전에 등재된 것도 없습니다. 그의 후기 경력 상당 부분은 증명보다는 행정, 자금 지원 기구 및 학회 회장직에 투입되었습니다. 기록이 뒷받침하는 것은 칭송받는 '천재'가 아니라 더 정확하게 가치 있는 무언가, 즉 1급 성과들로 이루어진 경력, 오늘날에도 매일 사용되는 프레임워크, 그리고 개별적인 정리보다 오래 지속되는 베를린의 제도적 유산입니다.

유산

분리-최적화 동등성은 이제 표준 장비가 되어 해당 분야의 모든 대학원생들에게 가르쳐지고, 새로운 완화 방식이 제안될 때마다 호출됩니다. 그가 정립을 도운 다면체 접근법은 항공기 노선을 짜고, 기차 운행을 조정하며, 전력망을 계획하는 상업용 정수 계획법 솔버의 기초가 됩니다. 그리고 ZIB, 마테온, 그리고 베를린 최적화 학파는 그에게서 어려운 실제 문제와 깊은 수학적 문제가 종종 양면에서 본 동일한 객체라는 점을 배운 사람들이 운영하는 제도적 사실들입니다.