Ising-Machine-Assisted Large Neighborhood Search with Flexibly Tunable Subproblem Size

तकनीकी सारांश: लचीले ढंग से ट्यून करने योग्य उप-समस्या आकार के साथ आइसिंग-मशीन-सहायता प्राप्त लार्ज नेबरहुड सर्च

समस्या विवरण
आइसिंग मशीनें आइसिंग या क्वाड्रेटिक अनकन्स्ट्रेंड बाइनरी ऑप्टिमाइज़ेशन (QUBO) मॉडल के निम्न-ऊर्जा अवस्थाओं (low-energy states) की खोज करके कॉम्बिनेटोरियल ऑप्टिमाइज़ेशन के लिए ह्यूरिस्टिक सॉल्वर के रूप में कार्य करती हैं। हालाँकि, बड़े पैमाने की बाधित समस्याओं (constrained problems) पर उन्हें सीधे लागू करना (जिसे "नेइव मेथड" कहा जाता है) दो प्राथमिक कठिनाइयों का सामना करता है:

1. स्केलेबिलिटी (Scalability): QUBO फॉर्मूलेशन में बाइनरी वेरिएबल्स की संख्या वर्तमान आइसिंग मशीनों की हार्डवेयर क्षमता से अधिक हो जाती है।
2. व्यवहार्यता (Feasibility): बाधाओं (constraints) को पेनल्टी टर्म्स के रूप में शामिल किया जाता है। फलस्वरूप, खोज स्थान (search space) में अव्यवहार्य समाधान शामिल होते हैं, और निम्न-ऊर्जा अवस्थाएं आवश्यक रूप से मूल समस्या के उच्च-गुणवत्ता वाले व्यवहार्य समाधानों के अनुरूप नहीं होती हैं।

मौजूदा दृष्टिकोण जैसे कि वेरिएबल फिक्सिंग या डिवाइड-एंड-कॉन्कर (divide-and-conquer) उप-समस्या के आकार और मूल समस्या के लिए व्यवहार्य समाधानों को पुनर्गठित करने की क्षमता के बीच संतुलन बनाने में संघर्ष करते हैं। लार्ज नेबरहुड सर्च (LNS) एक ऐसा ढांचा प्रदान करता है जहाँ एक व्यवहार्य वर्तमान समाधान को एक उप-समस्या (एक "नेबरहुड") को पुन: अनुकूलित करके पुनरावृत्ति (iteratively) के माध्यम से सुधारा जाता है। जबकि LNS व्यवहार्यता बनाए रखता है यदि उप-समस्या जनरेशन विधि को सही ढंग से डिज़ाइन किया गया हो, आइसिंग-मशीन-सहायता प्राप्त LNS का प्रदर्शन उप-समस्या के आकार के प्रति अत्यधिक संवेदनशील होता है। यदि उप-समस्या बहुत छोटी है, तो प्रति इटरेशन सुधार की क्षमता सीमित हो जाती है; यदि बहुत बड़ी है, तो विस्तारित खोज स्थान के कारण आइसिंग मशीन की समाधान गुणवत्ता घट जाती है।

कार्यप्रणाली (Methodology)
यह शोध पत्र दो समस्याओं पर ध्यान केंद्रित करता है: व्हीकल रूटिंग प्रॉब्लम (VRP) और क्वाड्रेटिक मल्टीपल नैपसैक प्रॉब्लम (QMKP)।

• मौजूदा विधि (LNS-V): VRP के लिए, लेखक एक पिछली विधि (LNS-V) का विश्लेषण करते हैं जो वाहनों के एक उपसमुच्चय (subset) का चयन करती है और उनके पूरे मार्गों को पुन: अनुकूलित करती है। जबकि यह व्यवहार्यता बनाए रखता है, उप-समस्या का आकार केवल चयनित वाहनों की संख्या ($V'$) द्वारा नियंत्रित होता है। क्योंकि चयनित प्रत्येक वाहन के पूरे मार्ग को पुन: अनुकूलित किया जाता है, इसलिए वेरिएबल्स की संख्या $(V')^2(T-2)^2$ के रूप में स्केल करती है (जहाँ $T$ कुल चरण हैं)। इसके परिणामस्वरूप 'कोर्स ग्रैनुलैरिटी' (coarse granularity) आती है; $V'$ को एक से बदलने पर भी वेरिएबल्स की संख्या में भारी उछाल आ सकता है, जिससे आइसिंग मशीन के लिए इष्टतम रेंज तक उप-समस्या के आकार को ट्यून करना कठिन हो जाता है।

• प्रस्तावित विधि (LTS-VT): ग्रैनुलैरिटी की समस्या को हल करने के लिए, लेखक LNS-VT प्रस्तावित करते हैं। $V'$ वाहनों के चयन के अलावा, LNS-VT एक नया पैरामीटर पेश करता है: प्रत्येक चयनित वाहन के लिए पुन: अनुकूलित किए जाने वाले निरंतर चरणों (consecutive steps) की संख्या ($T'$)।

  • तंत्र (Mechanism): प्रत्येक चयनित वाहन के लिए, रूट के एक निरंतर खंड (लंबाई $T_{seg} = \min(T', \text{वास्तविक वैध चरण})$ के साथ) को निकाला जाता है। उप-समस्या इन विशिष्ट खंडों के भीतर साइटों के असाइनमेंट और क्रम को पुन: अनुकूलित करती है, जबकि शेष रूट को स्थिर रखती है।
  • व्यवहार्यता (Feasibility): निष्कर्षण अंतराल (extraction intervals) के बाहर की साइटों को स्थिर रखकर और यह सुनिश्चित करके कि निकाले गए खंड केवल गैर-डिपोट साइटों को शामिल करते हैं, यह विधि गारंटी देती है कि उप-समस्या के किसी भी व्यवहार्य समाधान को पुन: सम्मिलित करने से मूल VRP के लिए एक व्यवहार्य समाधान प्राप्त होगा।
  • वेरिएबल नियंत्रण (Variable Control): LNS-VT में मुक्त वेरिएबल्स की संख्या लगभग $(V'T')^2$ होती है। यह कुल समस्या चरणों $T$ से स्वतंत्र रूप से उप-समस्या के आकार पर सूक्ष्म नियंत्रण (fine-grained control) की अनुमति देता है।

• QMKP में विस्तार: लेखक QMKP के लिए उसी डिज़ाइन सिद्धांत को लागू करते हैं। वे एक उप-समस्या जनरेशन विधि का निर्माण करते है जो नैपसैक के एक उपसमुच्चय ($K'$) और वस्तुओं के एक उपसमुच्चय ($N'$) का चयन करती है जिसे पुन: अनुकूलित किया जाना है। यह विधि चयनित सेट में न होने वाली वस्तुओं को स्थिर करके और चयनित नैपसक्स की अवशिष्ट क्षमता (residual capacity) के लिए क्षमता बाधाओं को समायोजित करके व्यवहार्यता बनाए रखती है।

प्रमुख परिणाम
संख्यात्मक प्रयोग एक 300-साइट, 5-व्हीकल VRP और एक 200-आइटम, 5-नैपसैक QMKP के लिए, Fixstars Amplify AE आइसिंग मशीन का उपयोग करके किए गए थे।

• VRP प्रदर्शन:

  • LNS-VT ने नेइव मेथड और मौजूदा LNS-V दोनों को पीछे छोड़ दिया।
  • सर्वश्रेष्ठ LNS-VT सेटिंग (विशेष रूप से $V'=2, T'=40$) ने 100 इटरेशन के बाद LNS-V के सापेक्ष ऑब्जेक्टिव वैल्यू को लगभग 10% कम कर दिया।
  • LNS-VT ने LNS-V की अंतिम समाधान गुणवत्ता केवल लगभग 30% इटरेशन का उपयोग करके प्राप्त कर ली।
  • वेरिएबल संवेदनशीलता (Variable Sensitivity): पाया गया कि इष्टतम उप-समस्या आकार (गैर-डिपोट साइट-असाइनमेंट वेरिएबल्स के संदर्भ में) 6,000 और 10,000 के बीच था। मौजूदा LNS-V $V' \ge 2$ के साथ इस रेंज को प्राप्त नहीं कर सका (इसका न्यूनतम ~14,400 वेरिएबल्स था), जो इसके निम्न प्रदर्शन की व्याख्या करता है।
  • डायनेमिक आवश्यकताएं: खोज प्रक्रिया के दौरान उपयुक्त उप-समस्या का आकार बदलता रहा। शुरुआती इटरेशन (बड़े ऑब्जेक्टिव मान) में बड़े उप-समस्या आकार अधिक प्रभावी थे, जबकि बाद के इटरेशन (उच्च-गुणवत्ता वाले समाधानों को रिफाइन करने) में छोटे उप-समस्या आकार अधिक प्रभावी थे।

• QMKP प्रदर्शन:

  • QMKP पर लागू LNS ने भी नेइव मेथड से बेहतर प्रदर्शन किया।
  • QMKP के लिए इष्टतम उप-समस्या आकार काफी छोटा, लगभग 100 से 150 वेरिएबल्स पाया गया।
  • VRP (6,000–10,000) की तुलना में यह भारी अंतर यह दर्शाता है कि इष्टतम उप-समस्या आकार विशिष्ट समस्या वर्ग और QUBO फॉर्मूलेशन पर निर्भर करता है, न कि केवल आइसिंग मशीन की क्षमताओं पर।

महत्व और दावे
शोध पत्र का दावा है कि बड़े पैमाने की बाधित समस्याओं के लिए आइसिंग-मशीन-सहायता प्राप्त LNS के प्रभावी होने के लिए, केवल व्यवहार्यता बनाए रखना पर्याप्त नहीं है। आइसिंग मशीन के प्रदर्शन के 'स्वीट स्पॉट' (sweet spot) से मेल खाने के लिए उप-समस्या के आकार को लचीले ढंग से ट्यून करने की क्षमता एक महत्वपूर्ण डिज़ाइन कारक है।

अध्ययन प्रदर्शित करता है कि:

1. एक अतिरिक्त नियंत्रण पैरामीटर (VRP के लिए निरंतर चरण, या QMKP के लिए आइटम/नैपसैक काउंट) पेश करने से उप-समस्या के आकार का सूक्ष्म समायोजन संभव होता है, जो केवल चयनित संस्थाओं की संख्या को बदलने वाले तरीकों के साथ असंभव है।
2. वेरिएबल्स की एक इष्टतम रेंज मौजूद है जो समाधान की गुणवत्ता को अधिकतम करती है, और यह रेंज विभिन्न समस्या वर्गों (VRP बनाम QMKP) के बीच काफी भिन्न होती है।
3. इष्टतम उप-समस्या आकार वर्तमान समाधान की गुणवत्ता पर भी निर्भर हो सकता है, जो यह सुझाव देता है कि पूरी खोज प्रक्रिया के दौरान स्थिर (static) पैरामीटर सेटिंग्स इष्टतम नहीं हो सकती हैं।

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