מרטין גרצ'ל: הגיאומטריה של בעיות קשות
בשנת 1982 הוענק פרס פולקרסון — הכבוד התובעני ביותר במתמטיקה בדידה, המוענק במשותף על ידי האגודה האמריקאית למתמטיקה והאגודה לאופטימיזציה מתמטית — על עבודה בנושא שיטת האליפסואיד. התוצאה שמאחוריו, שפותחה על ידי מרטין גרצ'ל (Martin Grötschel) יחד עם לאסלו לובאס (László Lovász) ואלכסנדר שרייבר (Alexander Schrijver), ביססה עובדה שעדיין מנחה את האופן שבו תיאורטיקנים חושבים על אופטימיזציה קומבינטורית: שעבור מחלקה רחבה מאוד של בעיות, היכולת לבצע הפרדה — לענות אם נקודה נמצאת בתוך קבוצה, ואם לאו להפיק על-מישור שמוכיח זאת — שקולה מבחינה חישובית ליכולת לבצע אופטימיזציה על אותה קבוצה. אופטימיזציה והפרדה הן אותה רמת קושי הלובשת צורות שונות.
משוולם לבון
גרצ'ל נולד ב-10 בספטמבר 1948 בשוולם (Schwelm), עיר תעשייתית קטנה בנורדריין-וסטפאליה. הוא למד מתמטיקה עם מקצוע משני בכלכלה באוניברסיטת בוכום (University of Bochum) החל משנת 1969, סיים את לימודיו (Diplom) ב-1973, ולאחר מכן עבר לאוניברסיטת בון כעוזר מחקר, שם נשאר במשך תשע שנים. את הדוקטורט שלו קיבל ב-1977 בהנחיית ברנהרד קורטה (Bernhard Korte), ממייסדי האופטימיזציה הבדידה הגרמנית; ההביליטציה שלו, בחקר ביצועים, באה בעקבותיה בבון ב-1981.
עבודת הדוקטורט ניגשה ישירות לבעיה הלא-ידידותית המפורסמת ביותר של התחום. גרצ'ל קידם את שיטת מישורי החיתוך עבור בעיית הסוכן הנוסע — הגישה שבה מרפים בעיה קומבינטורית קשה לבעיה רציפה, פותרים את הגרסה הקלה, ואז מוסיפים אי-שוויונות שחותכים את התשובות השבריריות שהרפיה מייצרת, תוך חזרה על הפעולה עד שהפתרון הוא שלם. הטכניקה חיה או מתה על הידיעה אילו אי-שוויונות להוסיף, והחיפוש אחריהם, קומבינטוריקה פוליהדרלית, הפך למרכז הקריירה שלו: הבנת הגיאומטריה של הקמור של פתרונות אפשריים של בעיה, כיוון שגיאומטריה זו היא המקום שבו טמון הקושי האמיתי.
אליפסואידים
שיטת האליפסואיד הגיעה למערב ב-1979 כהוכחה הראשונה לכך שתכנון ליניארי ניתן לפתרון בזמן פולינומי. היא הייתה, ונותרה, חסרת תועלת בפועל — איטית בהרבה משיטת הסימפלקס שתיאורטית היא עלתה עליה. מה שגרצ'ל, לובאס ושרייבר ראו היה שהכוח האמיתי שלה לא היה כאלגוריתם, אלא ככלי להוכחה.
מכיוון ששיטת האליפסואיד זקוקה רק לאורקל הפרדה ולא לרשימה מפורשת של אילוצים, היא יכולה לבצע אופטימיזציה על פוליהדרונים עם מספר מעריכי של פאות, בתנאי שניתן לזהות אילוץ מופר ביעילות. תצפית זו הפכה ערימה של שאלות פתוחות לפתורות במחי יד: משפחות שלמות של בעיות קומבינטוריות הוכחו כניתנות לפתרון בזמן פולינומי מבלי שאיש יבנה עבורן אלגוריתם ישיר. המסגרת הוצגה במלואה במונוגרפיה אלגוריתמים גיאומטריים ואופטימיזציה קומבינטורית (Geometric Algorithms and Combinatorial Optimization), שהפכה לאחד מספרי העיון הסטנדרטיים של התחום. פרס פולקרסון ב-1982 הכיר בעבודה; פרס ג'ורג' דנציג (George B. Dantzig Prize) הגיע ב-1991.
Twenty questions, eight minutes on the clock, and a percentile measured against everyone who has taken it. No sign-up.
Take the IQ test →ברלין
גרצ'ל החזיק בקתדרה למתמטיקה שימושית באוניברסיטת אאוגסבורג (University of Augsburg) מ-1982 עד 1991, אז עבר לברלין, שם בילה את שארית חייו המקצועיים. הוא הפך לפרופסור מן המניין לטכנולוגיית מידע באוניברסיטה הטכנית של ברלין (Technische Universität Berlin) ב-1991 וסגן נשיא מכון צוסה ברלין (Zuse Institute Berlin) באותה שנה, לקח על עצמו את נשיאות המכון ב-2012 והחזיק בה עד 2015. הוא כיהן כנשיא האקדמיה הברלינאית-ברנדנבורגית למדעים (Berlin-Brandenburg Academy of Sciences and Humanities) מ-2015 עד 2020, והוא פרופסור אורח מכובד באוניברסיטה הטכנית של מינכן (Technical University of Munich) מאז 2011.
העשורים בברלין העבירו את הדגש שלו לעבר יישומים, מבלי לנטוש את התיאוריה. הוא היה ממייסדי ויו"ר מרכז המחקר DFG Matheon, מוסד שנבנה על ההנחה שבעיות תעשייתיות ותשתיתיות מייצרות מתמטיקה חדשה באמת ולא רק צורכות מתמטיקה ישנה. עבודתו היישומית מגיעה לתכנון ייצור, תזמון תחבורה ציבורית, מערכות אנרגיה ולוגיסטיקה — תחומים שבהם כמה אחוזי שיפור בלוח זמנים קומבינטורי שווים הרבה כסף וכמות מדידה של פחמן.
הוא היה גם בונה מוסדות פעיל בצורה יוצאת דופן. הוא כיהן כנשיא האגודה המתמטית הגרמנית בשנים 1993–1994, כמזכיר כללי של האיגוד המתמטי הבינלאומי (International Mathematical Union) מ-2007 עד 2014, וכיו"ר קרן איינשטיין ברלין מ-2011 עד 2015. הוא ערך במשותף את ה-Handbook of Combinatorics. הפרסים נערמו: פרס קרל היינץ בקורץ (Karl Heinz Beckurts Prize) ב-1990, פרס גוטפריד וילהלם לייבניץ (Gottfried Wilhelm Leibniz Prize) — פרס המחקר היוקרתי ביותר בגרמניה — ב-1995, מדליית הזהב של EURO ב-2004, פרס ג'ון פון נוימן לתיאוריה ב-2006, עמית SIAM ופרס השירות המכובד של SIAM סביב 2009–10. הוא מחזיק בתארי דוקטור לשם כבוד מארבע אוניברסיטאות ושייך לשבע אקדמיות, כולל האקדמיה הלאומית להנדסה של ארה"ב, לאופולדינה (Leopoldina), אקאטק (acatech), האקדמיה אירופיאה (Academia Europaea) והאקדמיה הסינית למדעים.
מדוע מרטין מכונה גאון
המילה אינה כזו שתחומו משתמש לגביו, והתיאור הכנה שונה ושימושי יותר: גרצ'ל הוא מתמטיקאי מהשורה הראשונה שהצטיינותו מתועדת היטב בצורה יוצאת דופן על ידי פסיקה חיצונית. שלושה מהפרסים הגבוהים ביותר באופטימיזציה — פולקרסון, דנציג, פון נוימן — בתוספת פרס לייבניץ וחברות באקדמיות הלאומיות האמריקאית, הגרמנית והסינית מהווים עקבות של מצוינות טכנית מתמשכת שמעט מאוד מתמטיקאים פעילים צוברים.
האיכות הספציפית היא ארכיטקטונית ולא ראוותנית. התובנה לגבי שיטת האליפסואיד היא הדוגמה הברורה ביותר: ההישג לא היה המצאת אלגוריתם חדש אלא זיהוי שאלגוריתם קיים, חסר תועלת מעשית, קידד שקילות כללית, ואז חילוץ מאותה שקילות מכונה ליישוב שאלות בכל התחום. זהו סוג מסוים של מוח — כזה שמסתכל על כלי ורואה משפט. אותו אינסטינקט מופיע בתוכנית הפוליהדרלית, שבה המהלך הוא להפוך חיפוש בדיד לשאלה על הצורה של גוף קמור, ושוב ב-Matheon, שבה המהלך הוא להתייחס לבעיית תזמון תעשייתית כמקור למתמטיקה ולא כיישום שלה.
מקרה הנגד הוא פשוט וראוי לציון. התוצאות המרכזיות של גרצ'ל משותפות עם שותפים, בעיקר לובאס ושרייבר, וזה יהיה מצג שווא לייחס את שקילות ההפרדה-אופטימיזציה לו לבדו. פרסומו מוגבל להתמחותו; מחוץ לאופטימיזציה קומבינטורית וחקר ביצועים הוא אינו ידוע, ואף תוצאה אינה נושאת את שמו לאוצר המילים המתמטי הכללי. חלק ניכר מהקריירה המאוחרת שלו הושקע במינהל, גופי מימון ונשיאות חברות ולא בהוכחות. מה שהתיעוד תומך בו אינו גאונות מהוללת אלא משהו בעל ערך מדויק יותר: קריירה של תוצאות מהשורה הראשונה, מסגרת שהתחום עדיין משתמש בה מדי יום, ומורשת מוסדית בברלין שמחזיקה מעמד זמן רב יותר מכל משפט אינדיבידואלי.
מורשת
שקילות ההפרדה-אופטימיזציה היא כיום ציוד סטנדרטי, הנלמד לכל סטודנט לתואר מתקדם בתחום ומופעל בכל פעם שמוצעת מחלקה חדשה של הרפיות. הגישה הפוליהדרלית שהוא עזר לבסס עומדת בבסיס פותרי התכנות השלם המסחריים שמנתבים מטוסים, מתזמנים רכבות ומתכננים רשתות חשמל. ו-ZIB, Matheon ובית הספר לאופטימיזציה של ברלין הם עובדות מוסדיות בשטח, המאוישים על ידי אנשים שלמדו ממנו שבעיה מעשית קשה ובעיה מתמטית עמוקה הן לעתים קרובות אותו אובייקט שנראה משני צדדים.