مارتن غروتيتشل: هندسة المسائل المعقدة

في عام 1982، ذهبت جائزة فولكرسون (Fulkerson Prize) - وهي أرفع تكريم في الرياضيات المتقطعة، وتمنح بالاشتراك بين جمعية الرياضيات الأمريكية وجمعية التحسين الرياضي - إلى عمل حول طريقة القطع الناقص (ellipsoid method). النتائج الكامنة وراء ذلك، والتي طورها مارتن غروتيتشل (Martin Grötschel) مع لازلو لوفاس (László Lovász) وألكسندر شريفر (Alexander Schrijver)، أسست لشيء لا يزال يحكم كيفية تفكير المنظرين في التحسين التوافقي: أنه بالنسبة لفئة واسعة جداً من المسائل، فإن القدرة على الفصل - أي الإجابة عما إذا كانت النقطة تقع داخل مجموعة، وإذا لم تكن كذلك، تقديم مستوٍ فائق يثبت ذلك - مكافئة حسابياً للقدرة على التحسين عبر تلك المجموعة. التحسين والفصل هما نفس الصعوبة بملابس مختلفة.

من شفيلم إلى بون

ولد غروتيتشل في 10 سبتمبر 1948 في شفيلم (Schwelm)، وهي بلدة صناعية صغيرة في شمال الراين-وستفاليا. درس الرياضيات مع تخصص فرعي في الاقتصاد في جامعة بوخوم (University of Bochum) منذ عام 1969، وحصل على دبلومه في عام 1973، ثم انتقل إلى جامعة بون (University of Bonn) كباحث مساعد، حيث مكث لمدة تسع سنوات. حصل على الدكتوراه في عام 1977 تحت إشراف برنهارد كورتي (Bernhard Korte)، أحد مؤسسي التحسين المتقطع الألماني؛ وتبع ذلك تأهيله للأستاذية في بحوث العمليات في بون عام 1981.

انتقلت أطروحة الدكتوراه مباشرة إلى المسألة غير الودية الأكثر شهرة في هذا التخصص. طور غروتيتشل طريقة مستوي القطع لمسألة البائع المتجول (Traveling Salesman Problem) - وهو النهج الذي يتم فيه تخفيف مسألة توافقية صعبة إلى مسألة مستمرة، وحل النسخة السهلة، ثم إضافة متباينات تقطع الإجابات الكسرية التي ينتجها التخفيف، مع التكرار حتى يصبح الحل صحيحاً. تعتمد التقنية في نجاحها أو فشلها على معرفة المتباينات التي يجب إضافتها، وأصبح البحث عنها، وهو التوافقية متعددة الأوجه، مركز مسيرته المهنية: فهم هندسة الغلاف المحدب للحلول الممكنة للمسألة، لأن تلك الهندسة هي المكان الذي تكمن فيه الصعوبة بالفعل.

القطع الناقص

وصلت طريقة القطع الناقص إلى الغرب في عام 1979 كأول إثبات على أن البرمجة الخطية قابلة للحل في زمن متعدد الحدود. كانت، ولا تزال، ميؤوساً منها في الممارسة العملية - أبطأ بكثير من طريقة السمبلكس التي تفوقت عليها نظرياً. ما رآه غروتيتشل ولوفاس وشريفر هو أن قوتها الحقيقية لم تكن كخوارزمية بل كأداة إثبات.

لأن طريقة القطع الناقص تحتاج فقط إلى أوراكل فصل بدلاً من قائمة صريحة من القيود، يمكنها التحسين عبر متعددات الأوجه ذات عدد هائل من الأوجه، بشرط أن تتمكن من التعرف على قيد منتهك بكفاءة. حوّل هذا الملاحظة كومة من الأسئلة المفتوحة إلى أسئلة محسومة بضربة واحدة: ثبت أن عائلات كاملة من المسائل التوافقية قابلة للحل في زمن متعدد الحدود دون أن يقوم أي شخص ببناء خوارزمية مباشرة لها. تم وضع الإطار بالكامل في الكتاب المرجعي Geometric Algorithms and Combinatorial Optimization، الذي أصبح أحد المراجع القياسية في هذا المجال. اعترفت جائزة فولكرسون في عام 1982 بهذا العمل؛ وتلتها جائزة جورج ب. دانتزيغ (George B. Dantzig Prize) في عام 1991.

برلين

شغل غروتيتشل كرسي الرياضيات التطبيقية في جامعة أوغسبورغ (University of Augsburg) من 1982 إلى 1991، ثم انتقل إلى برلين، حيث قضى بقية حياته العملية. أصبح أستاذاً متفرغاً لتكنولوجيا المعلومات في جامعة برلين التقنية (Technische Universität Berlin) في 1991 ونائباً لرئيس معهد زوزه في برلين (Zuse Institute Berlin, ZIB) في نفس العام، وتولى رئاسة المعهد في عام 2012 وبقي فيها حتى 2015. شغل منصب رئيس أكاديمية برلين-براندنبورغ للعلوم والإنسانيات (Berlin-Brandenburg Academy of Sciences and Humanities) من 2015 إلى 2020، وكان أستاذاً منتسباً متميزاً في الجامعة التقنية في ميونيخ (Technical University of Munich) منذ عام 2011.

نقلت عقود برلين تركيزه نحو التطبيقات، دون التخلي عن النظرية. شارك في تأسيس ورئاسة مركز أبحاث ماتيون (Matheon)، وهو مؤسسة بنيت على فرضية أن المشاكل الصناعية والبنية التحتية تولد رياضيات جديدة حقاً بدلاً من مجرد استهلاك الرياضيات القديمة. يمتد عمله التطبيقي إلى تخطيط الإنتاج، وجدولة النقل العام، وأنظمة الطاقة والخدمات اللوجستية - المجالات التي تساوي فيها نسبة قليلة من التحسين في الجدول التوافقي الكثير من المال وكمية قابلة للقياس من الكربون.

كان أيضاً مؤسساً مؤسسياً نشطاً بشكل غير عادي. شغل منصب رئيس الجمعية الرياضية الألمانية (German Mathematical Society) في 1993-94، وكأمين عام للاتحاد الرياضي الدولي (International Mathematical Union) من 2007 إلى 2014، ورئيساً لمؤسسة أينشتاين في برلين (Einstein Foundation Berlin) من 2011 إلى 2015. شارك في تحرير Handbook of Combinatorics. تراكمت الجوائز: جائزة كارل هاينز بيكورتس في عام 1990، جائزة غوتفريد فيلهلم لايبنتز في عام 1995 - وهي أثمن جائزة بحثية في ألمانيا، والميدالية الذهبية لليورو في عام 2004، وجائزة جون فون نيومان للنظرية في عام 2006، وزمالة SIAM وجائزة الخدمة المتميزة من SIAM حوالي 2009-10. يحمل شهادات دكتوراه فخرية من أربع جامعات وينتمي إلى سبع أكاديميات، بما في ذلك الأكاديمية الوطنية للهندسة الأمريكية، وليوبولدينا، وأكاتيش، والأكاديمية الأوروبية، والأكاديمية الصينية للعلوم.

لماذا يسمى مارتن عبقرياً

الكلمة ليست واحدة مما يستخدمه مجاله عنه، والوصف الصادق مختلف وأكثر فائدة: غروتيتشل عالم رياضيات من الدرجة الأولى يتم توثيق تميزه بشكل جيد بشكل غير عادي من خلال الحكم الخارجي. ثلاث من أعلى الجوائز في التحسين - فولكرسون، دانتزيغ، فون نيومان - بالإضافة إلى جائزة لايبنتز وعضوية الأكاديميات الوطنية الأمريكية والألمانية والصينية تشكل أثراً ورقياً للتميز التقني المستمر الذي لا يحققه سوى عدد قليل جداً من علماء الرياضيات العاملين.

الجودة المحددة هي معمارية وليست براقة. رؤية طريقة القطع الناقص هي المثال الأوضح: الإنجاز لم يكن اختراع خوارزمية جديدة بل إدراك أن خوارزمية موجودة وغير مجدية عملياً ترميز تكافؤ عام، ثم استخلاص من ذلك التكافؤ آلة لتسوية الأسئلة عبر موضوع كامل. هذا نوع خاص من العقل - العقل الذي ينظر إلى أداة ويرى نظرية. تظهر نفس الغريزة في برنامج متعدد الأوجه، حيث تكون الخطوة هي تحويل بحث متقطع إلى سؤال حول شكل جسم محدب، ومرة أخرى في ماتيون، حيث تكون الخطوة هي التعامل مع مسألة جدولة صناعية كمصدر للرياضيات بدلاً من تطبيق لها.

القضية المضادة واضحة وتستحق الذكر. النتائج المركزية لغروتيتشل مشتركة مع متعاونين، أبرزهم لوفاس وشريفر، وسيكون من غير الدقيق تمثيل السجل إذا عُزي تكافؤ الفصل والتحسين إليه وحده. شهرته محصورة في تخصصه؛ خارج التحسين التوافقي وبحوث العمليات هو غير معروف بشكل أساسي، ولا توجد نتيجة تحمل اسمه في المفردات الرياضية العامة. ذهب جزء كبير من مسيرته اللاحقة في الإدارة وهيئات التمويل ورئاسة الجمعيات بدلاً من البراهين. ما يدعمه السجل ليس عبقرية مشهورة بل شيء أكثر قيمة بدقة: مسيرة مهنية من نتائج من الدرجة الأولى، وإطار لا يزال المجال يستخدمه يومياً، وإرث مؤسسي في برلين يدوم أطول من أي نظرية فردية.

الإرث

يعد تكافؤ الفصل والتحسين الآن معدات قياسية، تُدرس لكل طالب دراسات عليا في المنطقة ويُستشهد بها كلما تم اقتراح فئة جديدة من التخفيفات. النهج متعدد الأوجه الذي ساعد في تأسيسه هو الأساس لحلالات البرمجة الصحيحة التجارية التي توجه الطائرات، وتجدول القطارات، وتخطط لشبكات الطاقة. ومعهد زوزه في برلين، وماتيون، ومدرسة التحسين في برلين هي حقائق مؤسسية على الأرض، يعمل بها أشخاص تعلموا منه أن مسألة عملية صعبة ومسألة رياضية عميقة هما غالباً نفس الشيء يُنظر إليه من جانبين.