शोधकर्ताओं ने सेमिनल समस्या के लिए नई गति सीमा का रुख किया

प्लेटो द्वारा पुनर्प्रकाशित

अनुयायियों: 0

यात्रा विक्रेता समस्या सबसे पुराने ज्ञात कम्प्यूटेशनल प्रश्नों में से एक है। यह माइलेज को कम करते हुए शहरों की एक निश्चित सूची के माध्यम से आदर्श मार्ग के बारे में पूछता है। सरल दिखने के बावजूद यह समस्या अत्यंत कठिन है। हालाँकि जब तक आपको सबसे छोटा रास्ता नहीं मिल जाता तब तक आप सभी संभावित मार्गों की जांच करने के लिए बल का प्रयोग कर सकते हैं, लेकिन कुछ ही शहरों के बाद ऐसी रणनीति अस्थिर हो जाती है। इसके बजाय, आप रैखिक प्रोग्रामिंग नामक एक कठोर गणितीय मॉडल लागू कर सकते हैं, जो मोटे तौर पर समीकरणों के एक सेट के रूप में समस्या का अनुमान लगाता है और सर्वोत्तम समाधान खोजने के लिए संभावित संयोजनों की विधिपूर्वक जांच करता है।

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

चूँकि उन्होंने सबसे पहले ILP तैयार किया था 60 साल पहले, शोधकर्ताओं ने विभिन्न एल्गोरिदम की खोज की है जो आईएलपी समस्याओं को हल करते हैं, लेकिन वे सभी आवश्यक चरणों की संख्या के मामले में अपेक्षाकृत धीमे रहे हैं। सबसे अच्छा संस्करण जो वे लेकर आ सकते हैं - एक प्रकार की गति सीमा - उस तुच्छ मामले से आता है जहां समस्या के चर (जैसे कि कोई सेल्समैन किसी शहर का दौरा करता है या नहीं) केवल बाइनरी मान (शून्य या 1) मान सकता है। इस मामले में, ILP में एक रनटाइम होता है जो चरों की संख्या के साथ तेजी से बढ़ता है, जिसे आयाम भी कहा जाता है। (यदि केवल एक चर है, तो हर संभावित संयोजन का परीक्षण करने और समस्या को हल करने में केवल दो चरण लगते हैं; दो चर का अर्थ है चार चरण, तीन का अर्थ है आठ चरण, और इसी तरह।)

दुर्भाग्यवश, एक बार जब वेरिएबल केवल शून्य और 1 से अधिक मान लेते हैं, तो एल्गोरिदम का रनटाइम बहुत लंबा हो जाता है। शोधकर्ताओं ने लंबे समय से सोचा है कि क्या वे तुच्छ आदर्श के करीब पहुंच सकते हैं। प्रगति धीमी रही है, के साथ रिकॉर्ड 1980 के दशक में स्थापित और केवल वृद्धिशील सुधार तब से बनाया गया.

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

"यह नया एल्गोरिदम बेहद रोमांचक है," ने कहा नूह स्टीफ़ेंस-डेविडोवित्ज़कॉर्नेल विश्वविद्यालय में गणितज्ञ और कंप्यूटर वैज्ञानिक। "यह लगभग 40 वर्षों में आईएलपी सॉल्वरों में पहले [प्रमुख] सुधार का प्रतिनिधित्व करता है।"

ILP किसी दी गई समस्या को रैखिक समीकरणों के एक सेट में परिवर्तित करके काम करता है जिसे कुछ असमानताओं को पूरा करना होगा। विशिष्ट समीकरण मूल समस्या के विवरण पर आधारित हैं। लेकिन हालांकि ये विवरण भिन्न हो सकते हैं, आईएलपी समस्याओं का मूल स्वरूप वही रहता है, जिससे शोधकर्ताओं को कई समस्याओं पर हमला करने का एक ही तरीका मिल जाता है।

इसका मतलब यह नहीं है कि यह आसान काम है। यह 1983 तक गणितज्ञ नहीं था हेंड्रिक लेनस्ट्रा साबित सामान्य समस्या भी हल करने योग्य थी, पहला एल्गोरिदम प्रदान किया गया जो यह कर सकता था। लेनस्ट्रा ने ILP के बारे में ज्यामितीय रूप से सोचा। सबसे पहले, उन्होंने ILP के केंद्र में मौजूद असमानताओं को किसी नियमित बहुभुज की तरह उत्तल आकार में बदल दिया। यह आकृति उस व्यक्तिगत समस्या की बाधाओं का प्रतिनिधित्व करती है जिसे आप हल कर रहे हैं, चाहे वह सोफ़ा उत्पादन हो या एयरलाइन शेड्यूलिंग, इसलिए आकृति का आंतरिक भाग उन सभी संभावित मूल्यों से मेल खाता है जो असमानताओं और इस प्रकार समस्या को हल कर सकते हैं। लेनस्ट्रा ने इस आकृति को उत्तल पिंड कहा है। समस्या का आयाम इस आकृति के आयाम को प्रभावित करता है: दो चर के साथ यह एक सपाट बहुभुज का रूप लेता है; तीन आयामों में यह एक है प्लेटोनिक ठोस, और इतने पर.

इसके बाद लेनस्ट्रा ने सभी पूर्णांकों की कल्पना ग्रिड बिंदुओं के एक अनंत सेट के रूप में की, जिसे गणित में एक जाली के रूप में जाना जाता है। एक द्वि-आयामी संस्करण बिंदुओं के समुद्र जैसा दिखता है, और तीन आयामों में यह उन बिंदुओं जैसा दिखता है जहां एक इमारत में स्टील बीम जुड़ते हैं। जाली का आयाम किसी दी गई समस्या के आयाम पर भी निर्भर करता है।

किसी दी गई ILP समस्या को हल करने के लिए, लेनस्ट्रा ने दिखाया कि आप बस यह देखें कि संभावित समाधान पूर्णांकों के सेट से कहाँ मिलते हैं: उत्तल शरीर और जाली के चौराहे पर। और वह एक एल्गोरिदम के साथ आए जो इस स्थान को विस्तृत रूप से खोज सकता था - लेकिन प्रभावी होने के लिए, इसे कभी-कभी समस्या को छोटे आयामों के टुकड़ों में तोड़ना पड़ता था, जिससे रनटाइम में कई चरण जुड़ते थे।

अगले वर्षों में, कई शोधकर्ताओं ने पता लगाया कि इस एल्गोरिदम को तेजी से कैसे चलाया जाए। 1988 में, रवि कन्नन और लास्ज़लो लोवाज़ ने कवरिंग रेडियस नामक एक अवधारणा पेश की, उधार के अध्ययन से त्रुटि-सुधार कोड, उत्तल शरीर और जाली को अधिक कुशलता से प्रतिच्छेद करने में मदद करने के लिए। मोटे तौर पर, कवरिंग त्रिज्या यह सुनिश्चित करती है कि उत्तल शरीर में हमेशा कम से कम एक पूर्णांक बिंदु होता है, चाहे आप इसे जाली पर कहीं भी रखें। परिणामस्वरूप, कवरिंग त्रिज्या का आकार यह भी निर्धारित करता है कि आप ILP समस्या को कितनी कुशलता से हल कर सकते हैं।

तो यह सब आदर्श कवरिंग त्रिज्या के आकार को निर्धारित करने के लिए नीचे आ गया। दुर्भाग्य से, यह अपने आप में एक कठिन समस्या साबित हुई, और कन्नन और लोवेज़ जो सबसे अच्छा कर सकते थे, वह ऊपरी और निचली सीमा की खोज करके संभावित मूल्य को कम करना था। उन्होंने दिखाया कि ऊपरी सीमा - कवरिंग त्रिज्या का अधिकतम आकार - आयाम के साथ रैखिक रूप से बढ़ाया गया है. यह काफी तेज़ था, लेकिन ILP रनटाइम को तेज़ करने के लिए पर्याप्त नहीं था। अगले 30 वर्षों में, अन्य शोधकर्ता केवल थोड़ा ही बेहतर कर सके।

अंततः रीस और रोथवॉस को आगे बढ़ने में जिस चीज ने मदद की, वह एक असंबंधित गणितीय परिणाम था जो पूरी तरह से लैटिस पर केंद्रित था। 2016 में, ओडेड रेगेव और स्टीफेंस-डेविडोवित्ज़ पता चला, वास्तव में, कितने जाली बिंदु एक विशिष्ट आकार में फिट हो सकते हैं। रीस और रोथवॉस ने इसे अन्य आकृतियों पर लागू किया, जिससे उन्हें ILP कवरिंग त्रिज्या में निहित जाली बिंदुओं की संख्या का बेहतर अनुमान लगाने की अनुमति मिली, जिससे ऊपरी सीमा कम हो गई। रेगेव ने कहा, "नवीनतम सफलता इस एहसास के साथ आई कि आप वास्तव में अन्य प्रकार की आकृतियाँ बना सकते हैं।"

यह नई कड़ी ऊपरी सीमा एक बहुत बड़ा सुधार था, जिससे रीस और रोथवॉस को समग्र आईएलपी एल्गोरिथ्म में नाटकीय गति प्राप्त करने की अनुमति मिली। उनका काम रनटाइम को (लॉग) पर लाता है n)^O⁽ⁿ⁾, जहां n चरों की संख्या है और पर)इसका मतलब यह है कि यह रैखिक रूप से मापता है n. (यह अभिव्यक्ति बाइनरी समस्या के रन टाइम के समान "लगभग" मानी जाती है।)

"यह गणित, कंप्यूटर विज्ञान और ज्यामिति के चौराहे पर एक जीत है," ने कहा डेनियल दादुश नीदरलैंड में राष्ट्रीय अनुसंधान संस्थान सीडब्ल्यूआई के, जिन्होंने आईएलपी रनटाइम को मापने के लिए इस्तेमाल किए जाने वाले एल्गोरिदम रीस और रोथवॉस को आगे बढ़ाने में मदद की।

अभी के लिए, नए एल्गोरिदम का उपयोग वास्तव में किसी भी तार्किक समस्या को हल करने के लिए नहीं किया गया है, क्योंकि इसका उपयोग करने के लिए आज के कार्यक्रमों को अपडेट करने में बहुत अधिक काम करना होगा। लेकिन रोथवॉस के लिए, यह बात बिल्कुल अलग है। “यह एक समस्या की सैद्धांतिक समझ के बारे में है जिसके मौलिक अनुप्रयोग हैं,” उन्होंने कहा।

इस बात पर कि क्या आईएलपी की कम्प्यूटेशनल दक्षता में और सुधार किया जा सकता है, शोधकर्ताओं को अभी भी उम्मीद है कि वे आदर्श रनटाइम तक पहुंचते रहेंगे - लेकिन निकट भविष्य में नहीं। वेम्पला ने कहा, "इसके लिए मौलिक रूप से नए विचार की आवश्यकता होगी।"