Martin Grötschel: Zor Problemlerin Geometrisi

1982 yılında, Amerikan Matematik Topluluğu ve Matematiksel Optimizasyon Topluluğu tarafından ortaklaşa verilen, ayrık matematiğin en zorlu onuru olan Fulkerson Ödülü (Fulkerson Prize), elipsoid yöntemi (ellipsoid method) üzerine yapılan çalışmalara verildi. Martin Grötschel (Martin Grötschel) tarafından László Lovász ve Alexander Schrijver ile birlikte geliştirilen bu sonuç, kuramcıların kombinatoryal optimizasyon hakkında düşünme biçimini hala belirleyen bir ilkeyi ortaya koydu: çok geniş bir problem sınıfı için ayırma yapabilmek — yani bir noktanın küme içinde olup olmadığını yanıtlamak ve değilse bunu kanıtlayan bir hiperdüzlem üretmek — hesaplama açısından o küme üzerinde optimizasyon yapabilmekle eşdeğerdir. Optimizasyon ve ayırma, farklı kıyafetler giymiş aynı zorluktur.

Schwelm'den Bonn'a

Grötschel, 10 Eylül 1948'de Kuzey Ren-Vestfalya'nın küçük bir sanayi kasabası olan Schwelm'de doğdu. 1969'dan itibaren Bochum Üniversitesi'nde (University of Bochum) ekonomi yandalı ile matematik okudu, 1973'te diplomasını aldı ve ardından dokuz yıl kalacağı Bonn Üniversitesi'ne (University of Bonn) araştırma görevlisi olarak geçti. Doktorasını 1977'de Alman ayrık optimizasyonunun kurucularından Bernhard Korte'nin (Bernhard Korte) danışmanlığında tamamladı; 1981'de Bonn'da yöneylem araştırması alanında doçentlik (habilitation) derecesini aldı.

Doktora çalışması, disiplinin en meşhur sevimsiz problemiyle doğrudan ilgilendi. Grötschel, Gezgin Satıcı Problemi (Traveling Salesman Problem) için kesen düzlem yöntemini (cutting-plane method) ilerletti; bu, zor bir kombinatoryal problemin sürekli bir probleme gevşetildiği, kolay versiyonun çözüldüğü ve ardından gevşetmenin ürettiği kesirli yanıtları kesip atan eşitsizliklerin eklendiği, çözüm tamsayı olana kadar döngüsel olarak devam eden bir yaklaşımdı. Teknik, hangi eşitsizliklerin ekleneceğini bilmeye dayanıyordu ve bunların aranması yani çokyüzlü kombinatorik (polyhedral combinatorics), kariyerinin merkezi haline geldi: problemin uygun çözümlerinin oluşturduğu dışbükey gövdenin (convex hull) geometrisini anlamak, çünkü zorluk aslında o geometride yatıyordu.

Elipsoidler

Elipsoid yöntemi, lineer programlamanın polinom sürede çözülebilir olduğunun ilk kanıtı olarak 1979'da Batı'ya ulaştı. Uygulamada umutsuzdu ve hala öyledir; teorik olarak baskın olduğu simpleks yönteminden çok daha yavaştı. Grötschel, Lovász ve Schrijver'ın gördüğü şey, bunun gerçek gücünün bir algoritma olarak değil, bir kanıt aracı olarak olduğuydu.

Elipsoid yöntemi, açık bir kısıt listesi yerine sadece bir ayırma kâhini (separation oracle) gerektirdiğinden, ihlal edilen bir kısıtı verimli bir şekilde tanıyabildiğiniz sürece, üssel olarak çok sayıda yüze sahip çokyüzlüler üzerinde optimizasyon yapabilir. Bu gözlem, bir yığın açık soruyu bir çırpıda çözülmüş sorunlara dönüştürdü: tüm kombinatoryal problem ailelerinin, onlar için doğrudan bir algoritma oluşturmadan polinom sürede çözülebilir olduğu gösterildi. Çerçeve, alanın standart referanslarından biri haline gelen Geometric Algorithms and Combinatorial Optimization adlı monografide tam olarak ortaya kondu. 1982'deki Fulkerson Ödülü bu çalışmayı tanıdı; 1991'de George B. Dantzig Ödülü (George B. Dantzig Prize) izledi.

Berlin

Grötschel, 1982'den 1991'e kadar Augsburg Üniversitesi'nde (University of Augsburg) uygulamalı matematik kürsüsünde bulundu, ardından çalışma hayatının geri kalanını geçireceği Berlin'e taşındı. 1991'de Berlin Teknik Üniversitesi'nde (Technische Universität Berlin) bilgi teknolojisi profesörü oldu ve aynı yıl Berlin Zuse Enstitüsü'nün (Zuse Institute Berlin, ZIB) başkan yardımcılığına getirildi, 2012'de başkanlığı devraldı ve 2015'e kadar sürdürdü. 2015-2020 yılları arasında Berlin-Brandenburg Bilim ve Beşeri Bilimler Akademisi'nin (Berlin-Brandenburg Academy of Sciences and Humanities) başkanlığını yürüttü ve 2011'den beri Münih Teknik Üniversitesi'nde (Technical University of Munich) Seçkin Bağlı Profesör (Distinguished Affiliated Professor) olarak görev yapmaktadır.

Berlin'deki onlarca yıl, teoriden vazgeçmeden vurgusunu uygulamalara kaydırdı. Endüstriyel ve altyapı sorunlarının sadece eski matematiği tüketmek yerine gerçekten yeni matematik ürettiği öncülüne dayanan DFG Matheon Araştırma Merkezi'ni ortaklaşa kurdu ve başkanlığını yaptı. Uygulamalı çalışmaları; üretim planlama, toplu taşıma zamanlama, enerji sistemleri ve lojistiğe kadar uzanıyor; yani kombinatoryal bir programdaki yüzde birkaçlık bir iyileştirmenin çok fazla para ve ölçülebilir miktarda karbon tasarrufu anlamına geldiği alanlar.

Aynı zamanda alışılmadık derecede aktif bir kurum kurucusuydu. 1993-94'te Alman Matematik Topluluğu'nun (German Mathematical Society) başkanlığını, 2007'den 2014'e kadar Uluslararası Matematik Birliği'nin (International Mathematical Union) genel sekreterliğini ve 2011'den 2015'e kadar Einstein Vakfı Berlin'in başkanlığını yaptı. Handbook of Combinatorics'in editörlüğünü yaptı. Ödüller birikti: 1990'da Karl Heinz Beckurts Ödülü, 1995'te Almanya'nın en değerli araştırma ödülü olan Gottfried Wilhelm Leibniz Ödülü, 2004'te EURO Altın Madalyası, 2006'da John von Neumann Teori Ödülü, 2009-10 civarında SIAM Üyeliği ve SIAM Seçkin Hizmet Ödülü. Dört üniversiteden fahri doktora sahibidir ve ABD Ulusal Mühendislik Akademisi, Leopoldina, acatech, Academia Europaea ve Çin Bilimler Akademisi dahil olmak üzere yedi akademiye üyedir.

Martin Neden Dahi Olarak Adlandırılıyor

Bu kelime, alanının onun hakkında kullandığı bir kelime değildir ve dürüst tanım farklı ve daha yararlıdır: Grötschel, seçkinliği dış değerlendirmelerle alışılmadık derecede iyi belgelenmiş birinci sınıf bir matematikçidir. Optimizasyondaki en yüksek üç ödül - Fulkerson, Dantzig, von Neumann - artı Leibniz Ödülü ve Amerikan, Alman ve Çin ulusal akademilerine üyelik, çok az çalışan matematikçinin bir araya getirebildiği sürekli bir teknik mükemmellik kanıtıdır.

Özgül kalite gösterişli olmaktan ziyade mimaridir. Elipsoid yöntemi içgörüsü en net örnektir: başarı yeni bir algoritma icat etmek değil, mevcut, pratikte yararsız bir algoritmanın genel bir denklik kodladığını ve bu denklikten tüm bir konu genelinde soruları çözmek için bir makine çıkardığını fark etmekti. Bu özel bir zihin türüdür; bir araca bakıp bir teorem gören bir zihin. Aynı içgüdü, adımın ayrık bir aramayı dışbükey bir cismin şekli hakkında bir soruya dönüştürmek olduğu çokyüzlü programında ve Matheon'da yine adımın endüstriyel bir zamanlama problemini bir matematik uygulaması yerine bir matematik kaynağı olarak ele almak olduğu durumda kendini gösterir.

Karşı argüman basittir ve belirtilmeye değerdir. Grötschel'in merkezi sonuçları, başta Lovász ve Schrijver olmak üzere işbirlikçilerle paylaşılmaktadır ve ayırma-optimizasyon denkliğini sadece ona atfetmek kaydı yanlış yansıtmaktır. Şöhreti uzmanlığıyla sınırlıdır; kombinatoryal optimizasyon ve yöneylem araştırmasının dışında esasen bilinmemektedir ve genel matematiksel sözlükte onun adını taşıyan hiçbir sonuç yoktur. Sonraki kariyerinin önemli bir kısmı kanıtlardan ziyade idari işlere, finansman kuruluşlarına ve toplum başkanlıklarına gitti. Kaydın desteklediği şey alkışlanan bir deha değil, daha hassas bir şekilde değerli bir şeydir: birinci sınıf sonuçlarla dolu bir kariyer, alanın hala günlük olarak kullandığı bir çerçeve ve Berlin'de herhangi bir bireysel teoremden daha uzun süren kurumsal bir miras.

Miras

Ayırma-optimizasyon denkliği artık standart bir ekipmandır, alandaki her lisansüstü öğrenciye öğretilir ve yeni bir gevşetme sınıfı önerildiğinde çağrılır. Kurulmasına yardımcı olduğu çokyüzlü yaklaşım, uçakları yönlendiren, trenleri zamanlayan ve elektrik şebekelerini planlayan ticari tamsayı programlama çözücülerinin temelini oluşturur. Ve ZIB, Matheon ve Berlin optimizasyon okulu, zor bir pratik problem ile derin bir matematiksel problemin genellikle iki taraftan bakılan aynı nesne olduğunu ondan öğrenen insanlar tarafından çalıştırılan kurumsal gerçeklerdir.