मार्टिन ग्रोटशेल: कठिन समस्याओं की ज्यामिति

1982 में, फुलकर्सन प्राइज़ (Fulkerson Prize) - जो असतत गणित (discrete mathematics) का सबसे सटीक सम्मान है और जिसे अमेरिकन मैथमेटिकल सोसाइटी और मैथमेटिकल ऑप्टिमाइज़ेशन सोसाइटी द्वारा संयुक्त रूप से दिया जाता है - एलिप्सॉइड विधि (ellipsoid method) पर किए गए काम को मिला। इसके पीछे का परिणाम, जिसे मार्टिन ग्रोटशेल (Martin Grötschel) ने लास्ज़लो लोवाज़ (László Lovász) और अलेक्जेंडर श्रिज्वर (Alexander Schrijver) के साथ मिलकर विकसित किया, ने कुछ ऐसा स्थापित किया जो आज भी सिद्धांतकारों के कॉम्बिनेटरियल ऑप्टिमाइज़ेशन के बारे में सोचने के तरीके को नियंत्रित करता है: कि समस्याओं के एक बहुत व्यापक वर्ग के लिए, पृथक्करण (separate) करने में सक्षम होना - यानी यह उत्तर देना कि क्या कोई बिंदु किसी सेट के अंदर है, और यदि नहीं तो एक हाइपरप्लेन प्रस्तुत करना जो इसे साबित करे - गणनात्मक रूप से उस सेट पर अनुकूलित (optimize) करने में सक्षम होने के बराबर है। ऑप्टिमाइज़ेशन और पृथक्करण अलग-अलग कपड़े पहने एक ही कठिनाई हैं।

श्वेलम से बॉन तक

ग्रोटशेल का जन्म 10 सितंबर 1948 को नॉर्थ राइन-वेस्टफेलिया के एक छोटे से औद्योगिक शहर श्वेलम (Schwelm) में हुआ था। उन्होंने 1969 से बॉचुम विश्वविद्यालय (University of Bochum) में अर्थशास्त्र के साथ गणित का अध्ययन किया, 1973 में अपना डिप्लोमा प्राप्त किया, और फिर शोध सहायक के रूप में बॉन विश्वविद्यालय (University of Bonn) चले गए, जहाँ वे नौ वर्षों तक रहे। उनकी डॉक्टरेट 1977 में जर्मन असतत अनुकूलन के संस्थापकों में से एक, बर्नहार्ड कोर्टे (Bernhard Korte) के मार्गदर्शन में आई; इसके बाद 1981 में बॉन में ऑपरेशन्स रिसर्च में उनका हाइबिलिटेशन (अध्यापन योग्यता) हुआ।

डॉक्टरेट का काम सीधे अनुशासन की सबसे प्रसिद्ध अमित्र समस्या पर गया। ग्रोटशेल ने ट्रैवलिंग सेल्समैन प्रॉब्लम (Traveling Salesman Problem) के लिए कटिंग-प्लेन विधि को आगे बढ़ाया - वह दृष्टिकोण जिसमें कोई कठिन कॉम्बिनेटरियल समस्या को एक निरंतर समस्या में ढीला करता है, आसान संस्करण को हल करता है, और फिर ऐसे असमानताएँ जोड़ता है जो ढील द्वारा उत्पन्न आंशिक उत्तरों को काट देती हैं, जब तक कि समाधान पूर्णांक न हो जाए, तब तक दोहराता रहता है। तकनीक इस बात पर निर्भर करती है कि कौन सी असमानताएँ जोड़नी हैं, और उनकी खोज, पॉलीहेड्रल कॉम्बिनेटरिक्स, उनके करियर का केंद्र बन गई: समस्या के व्यवहार्य समाधानों के उत्तल पतवार (convex hull) की ज्यामिति को समझना, क्योंकि कठिनाई वास्तव में उसी ज्यामिति में निवास करती है।

एलिप्सॉइड्स

एलिप्सॉइड विधि 1979 में पश्चिम में इस पहले प्रमाण के रूप में आई कि लीनियर प्रोग्रामिंग को बहुपद समय (polynomial time) में हल किया जा सकता है। यह व्यवहार में निराशाजनक थी, और आज भी है - सिम्प्लेक्स विधि की तुलना में बहुत धीमी, जिस पर यह सैद्धांतिक रूप से हावी थी। ग्रोटशेल, लोवाज़ और श्रिज्वर ने जो देखा वह यह था कि इसकी वास्तविक शक्ति एक एल्गोरिदम के रूप में नहीं, बल्कि एक प्रमाण उपकरण के रूप में थी।

चूंकि एलिप्सॉइड विधि को बाधाओं की एक स्पष्ट सूची के बजाय केवल एक पृथक्करण ओरेकल (separation oracle) की आवश्यकता होती है, यह तेजी से कई पहलुओं वाले पॉलीहेड्रा पर अनुकूलित कर सकती है, बशर्ते आप उल्लंघन की गई बाधा को कुशलतापूर्वक पहचान सकें। उस अवलोकन ने एक झटके में खुली समस्याओं के ढेर को सुलझा हुआ बना दिया: कॉम्बिनेटरियल समस्याओं के पूरे परिवारों को बहुपद समय में हल करने योग्य दिखाया गया, बिना किसी ने उनके लिए प्रत्यक्ष एल्गोरिदम का निर्माण किया। ढांचे को पूरी तरह से मोनोग्राफ Geometric Algorithms and Combinatorial Optimization में निर्धारित किया गया था, जो क्षेत्र के मानक संदर्भों में से एक बन गया। 1982 में फुलकर्सन प्राइज़ ने इस काम को मान्यता दी; 1991 में जॉर्ज बी. डेंटज़िग प्राइज़ (George B. Dantzig Prize) मिला।

बर्लिन

ग्रोटशेल ने 1982 से 1991 तक ऑग्सबर्ग विश्वविद्यालय (University of Augsburg) में अनुप्रयुक्त गणित की कुर्सी संभाली, फिर बर्लिन चले गए, जहाँ उन्होंने अपने काम के जीवन का बाकी हिस्सा बिताया। वह 1991 में बर्लिन की टेक्निकल यूनिवर्सिटी (Technische Universität Berlin) में सूचना प्रौद्योगिकी के पूर्ण प्रोफेसर बने और उसी वर्ष ज़्यूज़ इंस्टीट्यूट बर्लिन (Zuse Institute Berlin, ZIB) के उपाध्यक्ष बने, 2012 में ZIB की अध्यक्षता संभाली और 2015 तक इसे संभाला। उन्होंने 2015 से 2020 तक बर्लिन-ब्रैंडनबर्ग एकेडमी ऑफ साइंसेज एंड ह्यूमैनिटीज (Berlin-Brandenburg Academy of Sciences and Humanities) के अध्यक्ष के रूप में कार्य किया, और 2011 से म्यूनिख की टेक्निकल यूनिवर्सिटी (Technical University of Munich) में एक प्रतिष्ठित संबद्ध प्रोफेसर (Distinguished Affiliated Professor) रहे हैं।

बर्लिन के दशकों ने सिद्धांत को छोड़े बिना उनके जोर को अनुप्रयोगों की ओर स्थानांतरित कर दिया। उन्होंने DFG रिसर्च सेंटर मैथियन (Matheon) की सह-स्थापना और अध्यक्षता की, एक संस्थान जो इस आधार पर बनाया गया था कि औद्योगिक और बुनियादी ढांचा समस्याएं केवल पुरानी गणित का उपभोग करने के बजाय वास्तव में नई गणित उत्पन्न करती हैं। उनका अनुप्रयुक्त कार्य उत्पादन योजना, सार्वजनिक परिवहन शेड्यूलिंग, ऊर्जा प्रणालियों और लॉजिस्टिक्स तक पहुंचता है - ऐसे डोमेन जहां एक कॉम्बिनेटरियल शेड्यूल में सुधार के कुछ प्रतिशत बहुत सारे पैसे और कार्बन की मापने योग्य मात्रा के लायक हैं।

वह एक असाधारण रूप से सक्रिय संस्थान-निर्माता भी थे। उन्होंने 1993-94 में जर्मन मैथमेटिकल सोसाइटी के अध्यक्ष के रूप में, 2007 से 2014 तक इंटरनेशनल मैथमेटिकल यूनियन के महासचिव के रूप में, और 2011 से 2015 तक आइंस्टीन फाउंडेशन बर्लिन के अध्यक्ष के रूप में कार्य किया। उन्होंने Handbook of Combinatorics का सह-संपादन किया। पुरस्कार जमा हुए: 1990 में कार्ल हेइन्ज़ बेकर्ट्स प्राइज़, 1995 में गॉटफ्राइड विल्हेम लीबनिज प्राइज़ - जर्मनी का सबसे मूल्यवान शोध पुरस्कार, 2004 में EURO गोल्ड मेडल, 2006 में जॉन वॉन न्यूमैन थ्योरी प्राइज़, 2009-10 के आसपास SIAM फेलोशिप और SIAM डिस्टिंग्विश्ड सर्विस प्राइज़। उनके पास चार विश्वविद्यालयों से मानद डॉक्टरेट है और वे सात अकादमियों के सदस्य हैं, जिनमें अमेरिकी नेशनल एकेडमी ऑफ इंजीनियरिंग, लियोपोल्डिना, अकाटेक (acatech), एकेडेमिया यूरोपा (Academia Europaea) और चीनी विज्ञान अकादमी शामिल हैं।

मार्टिन को प्रतिभाशाली क्यों कहा जाता है

यह शब्द वह नहीं है जो उनका क्षेत्र उनके बारे में उपयोग करता है, और ईमानदार विवरण अलग और अधिक उपयोगी है: ग्रोटशेल पहले दर्जे के गणितज्ञ हैं, जिनका भेद बाहरी फैसले द्वारा असामान्य रूप से अच्छी तरह से प्रलेखित है। ऑप्टिमाइज़ेशन में तीन सर्वोच्च पुरस्कार - फुलकर्सन, डेंटज़िग, वॉन न्यूमैन - और लीबनिज प्राइज़ और अमेरिकी, जर्मन और चीनी राष्ट्रीय अकादमियों की सदस्यता तकनीकी उत्कृष्टता का एक कागजी निशान बनाती है जिसे बहुत कम कामकाजी गणितज्ञ इकट्ठा कर पाते हैं।

विशिष्ट गुणवत्ता आकर्षक के बजाय वास्तुशिल्प है। एलिप्सॉइड-विधि अंतर्दृष्टि सबसे स्पष्ट उदाहरण है: उपलब्धि एक नया एल्गोरिदम का आविष्कार करना नहीं थी, बल्कि यह पहचानना था कि एक मौजूदा, व्यावहारिक रूप से बेकार एल्गोरिदम ने एक सामान्य समानता को एनकोड किया है, और फिर उस समानता से एक पूरे विषय के प्रश्नों को निपटाने के लिए एक मशीन निकाली। यह एक विशेष प्रकार का दिमाग है - जो एक उपकरण को देखता है और एक प्रमेय (theorem) को देखता है। वही प्रवृत्ति पॉलीहेड्रल कार्यक्रम में दिखाई देती है, जहां कदम एक असतत खोज को एक उत्तल शरीर के आकार के बारे में एक प्रश्न में बदलना है, और मैथियन में फिर से, जहां कदम एक औद्योगिक शेड्यूलिंग समस्या को गणित के अनुप्रयोग के बजाय गणित के स्रोत के रूप में मानना है।

प्रति-मामला सीधा है और बताने लायक है। ग्रोटशेल के केंद्रीय परिणाम सहयोगियों के साथ साझा किए जाते हैं, मुख्य रूप से लोवाज़ और श्रिज्वर, और अलगाव-अनुकूलन समानता को केवल उन्हें श्रेय देना रिकॉर्ड को गलत तरीके से प्रस्तुत करना होगा। उनकी प्रसिद्धि उनके विशेषज्ञता तक सीमित है; कॉम्बिनेटरियल ऑप्टिमाइज़ेशन और ऑपरेशन्स रिसर्च के बाहर वे अनिवार्य रूप से अज्ञात हैं, और कोई भी परिणाम उनका नाम सामान्य गणितीय शब्दावली में नहीं ले जाता है। उनके बाद के करियर का एक बड़ा हिस्सा सबूतों के बजाय प्रशासन, फंडिंग निकायों और समाज की अध्यक्षता में गया। रिकॉर्ड जो समर्थन करता है वह प्रशंसित प्रतिभा नहीं है बल्कि कुछ अधिक सटीक रूप से मूल्यवान है: प्रथम-दर परिणामों का एक करियर, एक ढांचा जो क्षेत्र अभी भी दैनिक उपयोग करता है, और बर्लिन में एक संस्थागत विरासत जो किसी भी व्यक्तिगत प्रमेय से अधिक समय तक चलती है।

विरासत

पृथक्करण-अनुकूलन समानता अब मानक उपकरण है, क्षेत्र में हर स्नातक छात्र को पढ़ाया जाता है और जब भी ढील का एक नया वर्ग प्रस्तावित किया जाता है तो इसे लागू किया जाता है। पॉलीहेड्रल दृष्टिकोण जिसे उन्होंने स्थापित करने में मदद की, वह वाणिज्यिक पूर्णांक-प्रोग्रामिंग सॉल्वर्स को रेखांकित करता है जो विमानों को रूट करते हैं, ट्रेनों को शेड्यूल करते हैं और बिजली ग्रिड की योजना बनाते हैं। और ZIB, मैथियन और बर्लिन ऑप्टिमाइज़ेशन स्कूल जमीन पर संस्थागत तथ्य हैं, जो ऐसे लोगों द्वारा कार्यरत हैं जिन्होंने उनसे सीखा कि एक कठिन व्यावहारिक समस्या और एक गहरी गणितीय समस्या अक्सर दो तरफ से देखी गई एक ही वस्तु होती है।