💻 computer science

Random-Key Optimizer and Linearization for the Quadratic Multiple Constraints Variable-Sized Bin Packing Problem

यह शोध पत्र एक रैखिकीकृत (linearized) गणितीय मॉडल को पेश करके 'क्वाड्रेटिक मल्टीपल कंस्ट्रेंट्स वेरिएबल-साइज़्ड बिन पैकिंग समस्या' को संबोधित करता है जो सुदृढ़ निचली सीमाएँ (lower bounds) उत्पन्न करता है, और एक नवीन RKO-ACO एल्गोरिदम को प्रस्तुत करता है जिसमें एडेप्टिव Q-लर्निंग शामिल है जो बड़े पैमाने के उदाहरणों के लिए नए सर्वश्रेष्ठ-ज्ञात समाधान स्थापित करता है।

मूल लेखक: Natalia A. Santos, Marlon Jeske, Antonio A. Chaves

प्रकाशित 2026-03-27

📖 6 मिनट में पढ़ें🧠 गहराई से पढ़ें

CC BY 4.0

मूल लेखक: Natalia A. Santos, Marlon Jeske, Antonio A. Chaves

मूल पेपर CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/) के तहत लाइसेंस किया गया है। ✨ नीचे दिए गए पेपर की यह व्याख्या AI से तैयार की गई है। इसे लेखकों ने न तो लिखा है, न इसका समर्थन किया है। तकनीकी सटीकता के लिए मूल पेपर देखें। पूरा डिस्क्लेमर पढ़ें

कल्पना कीजिए कि आप एक विशाल, अराजक गोदाम (warehouse) के मैनेजर हैं। आपका काम हजारों अलग-अलग वस्तुओं को शिपिंग कंटेनरों (बिनों) में पैक करना है ताकि उन्हें बाहर भेजा जा सके। लेकिन यह कोई सामान्य गोदाम नहीं है; यह तीन पेचीदा नियमों वाला एक अति-जटिल गोदाम है:

बहु-आयामी वजन (Multi-Dimensional Weight): वस्तुएं केवल भारी ही नहीं होतीं; वे एक साथ तीन अलग-अलग तरीकों से जगह घेरती हैं (जैसे क्लाउड सर्वर में CPU पावर, RAM मेमोरी और स्टोरेज स्पेस की तरह)। एक कंटेनर के लिए तीनों आयामों (dimensions) की सीमाएं होती हैं।
अलग-अलग कंटेनर: आपके पास कई प्रकार के कंटेनर हैं। कुछ सस्ते लेकिन छोटे हैं; कुछ महंगे लेकिन बहुत बड़े हैं। आप जितने चाहें उतने उपयोग कर सकते हैं, लेकिन आप कम से कम खर्च करना चाहते हैं।
"बेस्ट फ्रेंड्स" का नियम: कुछ वस्तुएं "बेस्ट फ्रेंड्स" हैं और अलग होने से नफरत करती हैं। यदि आप उन्हें अलग-अलग कंटेनरों में रखते हैं, तो वे एक "पेनल्टी" (जैसे संचार में देरी या शुल्क) का कारण बनती हैं। यदि आप उन्हें एक साथ रखते हैं, तो आप पैसे बचाते हैं।

यह क्वाड्रेटिक मल्टीपल कंस्ट्रेंट्स वेरिएबल-साइज्ड बिन पैकिंग प्रॉब्लम (QMC-VSBPP) है। यह एक गणितीय दुःस्वप्न है क्योंकि वस्तुओं को व्यवस्थित करने के कितने तरीके हैं, यह इतना विशाल है कि दुनिया के सबसे तेज़ सुपरकंप्यूटर भी सटीक व्यवस्था खोजने के लिए संघर्ष करते हैं।

यह शोध पत्र इस पहेली को हल करने के दो चतुर तरीके प्रस्तुत करता है: एक गणितीय शॉर्टकट और एक स्मार्ट रोबोट झुंड (Robot Swarm)।

1. गणितीय शॉर्टकट: "वक्रों को सीधा करना" (Straightening the Curves)

समस्या:
इस समस्या का मूल गणितीय मॉडल लूप्स और घुमावों (quadratic terms) वाले रोलरकोस्टर जैसा है। मानक गणितीय सॉल्वर (जैसे Gurobi, जो एक सुपर-स्मार्ट कैलकुलेटर की तरह है) के लिए इन लूप्स के बीच से रास्ता खोजकर सबसे अच्छा उत्तर ढूंढना बहुत कठिन है। वे या तो फंस जाते हैं या बहुत अधिक समय लेते हैं।

समाधान:
लेखकों ने एक लिनियराइज्ड मॉडल (Linearized Model) बनाया है। इसे इस तरह सोचें कि आप उस रोलरकोस्टर को एक सीधे, सुगम हाईवे में बदल रहे हैं।

यह कैसे काम करता है: उन्होंने जटिल "घुमावदार" गणितीय नियमों को सरल, सीधी रेखा वाले नियमों से बदल दिया।
परिणाम: अब सुपर-स्मार्ट कैलकुलेटर (Gurobi) इस हाईवे पर तेजी से दौड़ सकता है। यह हमेशा सबसे बड़े गोदामों के लिए परफेक्ट उत्तर तो नहीं ढूंढ पाता, लेकिन यह अब एक बहुत मजबूत "फ्लोर" (एक निचली सीमा/lower bound) ढूंढ सकता है।
उपमा (Analogy): कल्पना कीजिए कि आप किसी पहाड़ की ऊंचाई का अनुमान लगाने की कोशिश कर रहे हैं। पुराने तरीके में आपको हर रास्ते पर चढ़ना पड़ता था। नए तरीके में, आप एक सैटेलाइट मैप देखते हैं जो आपको तुरंत एक बहुत सटीक "न्यूनतम ऊंचाई" बता देता है। इससे शोधकर्ताओं को यह जानने में मदद मिलती है कि वे आदर्श समाधान के कितने करीब हैं।

2. स्मार्ट रोबोट झुंड: "RKO-ACO"

चूंकि गणितीय शॉर्टकट सबसे बड़े गोदामों को पूरी तरह से हल नहीं कर सकता, इसलिए लेखकों ने तेजी से सबसे अच्छा संभव समाधान खोजने के लिए एक स्मार्ट रोबमान टीम बनाई है। वे इसे RKO-ACO कहते हैं।

यहाँ यह रोबोट टीम कैसे काम करती है, इसके सरल भाग दिए गए हैं:

A. "मैजिक डिकोडर रिंग" (Random-Key Optimizer)

आमतौर पर, रोबोट इसलिए संघर्ष करते हैं क्योंकि गोदाम विशिष्ट स्लॉट्स (discrete) का एक ग्रिड होता है। लेकिन यह टीम एक अलग भाषा बोलती है: कंटीन्यूअस नंबर्स (Continuous Numbers)।

चाल (The Trick): रोबोट को यह बताने के बजाय कि "वस्तु A को बिन 1 में रखें," वे रोबोट को यादृच्छिक नंबरों (जैसे एक गुप्त कोड) की एक सूची देते हैं।
डिकोडर: एक विशेष "डिकोडर" इन नंबरों को पढ़ता है और उन्हें एक वास्तविक पैकिंग योजना में अनुवादित करता है। यदि वस्तु A के लिए नंबर 0.2 है और वस्तु B के लिए 0.8 है, तो डिकोडर जानता है कि A को B से पहले पैक करना है।
यह क्यों शानदार है: यह रोबोट को क्लंकी और झटकेदार कदमों के बजाय, समाधानों को खोजने के लिए सुचारू, बहते हुए आंदोलनों (पानी की तरह) का उपयोग करने की अनुमति देता है।

B. चींटियों का झुंड (Ant Colony - ACO)

ये रोबोट चींटियों से प्रेरित हैं।

चींटियाँ कैसे काम करती हैं: असली चींटियाँ गंध का निशान (फेरोमोन्स) छोड़ती हैं ताकि अन्य चींटियों को अच्छे भोजन का रास्ता दिखा सकें।
रोबोट कैसे काम करते हैं: "चींटियाँ" (रोबोट) विभिन्न पैकिंग योजनाओं की खोज करती हैं। जब उन्हें एक अच्छी योजना मिलती है, तो वे एक डिजिटल "गंध" (उनके आर्काइव में एक स्मृति) छोड़ देती हैं। अगली पीढ़ी के रोबोट सफल चींटियों द्वारा बनाए गए रास्तों का अनुसरण करने की अधिक संभावना रखते हैं।
ट्विस्ट: उन्होंने इसमें Q-Learning (एक प्रकार की AI लर्निंग) जोड़ा है। कल्पना कीजिए कि चींटियों के पास एक स्मार्ट कोच है। यदि चींटियाँ एक रणनीति आजमाती हैं और विफल हो जाती हैं, तो कोच कहता है, "ऐसा फिर से मत करना।" यदि यह काम करता है, तो कोच कहता है, "ऐसा और करो!" यह टीम को तुरंत अनुकूलित होने में मदद करता है।

C. "सफाई करने वाली" टीम (Local Search)

एक बार जब चींटियाँ एक अच्छी पैकिंग योजना ढूंढ लेती हैं, तो एक "सफाई करने वाली" (Tidy-Up) टीम आती है। वे बिनों को देखते हैं और पूछते हैं:

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

उन्होंने क्या हासिल किया?

लेखकों ने अपने तरीकों का परीक्षण 96 अलग-अलग "गोदाम" परिदृश्यों पर किया, जो छोटे (25 आइटम) से लेकर विशाल (200 आइटम) तक थे।

गणितीय शॉर्टकट की जीत हुई: नए "सीधे हाईवे" वाले मॉडल ने पुराने "रोलरकोस्टर" मॉडल की तुलना में सबसे अच्छी संभावित कीमत का बहुत बेहतर अनुमान दिया। इसने सबसे छोटे गोदामों के लिए परफेक्ट उत्तर खोजा।
रोबोट झुंड ने सबको पछाड़ दिया:
- पुराने तरीके (जैसे अन्य शोधकर्ताओं द्वारा उपयोग किया जाने वाला "Variable Neighborhood Search") एक धीमे, भ्रमित कछुए की तरह थे।
- नया RKO-ACO एक चीता था।
- इसने 96 में से 95 टेस्ट केस के लिए सबसे अच्छा ज्ञात समाधान खोजा।
- सबसे बड़े गोदामों के लिए, इसने ऐसे समाधान खोजे जो वैज्ञानिक साहित्य में पहले से दर्ज किसी भी चीज़ से बेहतर थे।

बड़ी तस्वीर (The Big Picture)

इस शोध पत्र को एक बहुत कठिन ताले की "मास्टर की" (Master Key) के रूप में देखें।

गणितज्ञों के लिए: उन्होंने समस्या की सीमाओं को समझने के लिए एक बेहतर मानचित्र (लीनियराइज्ड मॉडल) प्रदान किया।
इंजीनियरों के लिए: उन्होंने एक स्मार्ट, तेज़ रोबोट (RKO-ACO) बनाया जो इन जटिल गोदामों को पहले के मुकाबले कहीं बेहतर तरीके से पैक कर सकता है।

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

यहाँ "Random-Key Optimizer and Linearization for the Quadratic Multiple Constraints Variable-Sized Bin Packing Problem" शोध पत्र का विस्तृत तकनीकी सारांश दिया गया है।

1. समस्या की परिभाषा: QMC-VSBPP

यह शोध पत्र क्वाड्रेटिक मल्टीपल कंस्ट्रेंट्स वेरिएबल-साइज़्ड बिन पैकिंग प्रॉब्लम (QMC-VSBPP) को संबोधित करता है, जो एक जटिल कॉम्बिनेटरियल ऑप्टिमाइज़ेशन समस्या है और क्लासिकल बिन पैकिंग प्रॉब्लम (BPP) का विस्तार है।

मुख्य विशेषताएँ:
- वेरिएबल-साइज़्ड बिन्स: मानक BPP के विपरीत, वस्तुओं को विभिन्न प्रकार के बिन्स में पैक किया जा सकता है, जिनमें से प्रत्येक की अलग क्षमता और निश्चित लागत (fixed cost) होती है।
- मल्टीपल डाइमेंशन्स: वस्तुओं और बिन्स के पास $d$ -डायमेंशनल वेट और कैपेसिटी वेक्टर्स (जैसे CPU, RAM, स्टोरेज) होते हैं, न कि केवल एक एकल स्केलर साइज।
- क्वाड्रेटिक इंटरेक्शन कॉस्ट: यह समस्या एक दंड लागत (penalty cost) $c_{is}$ पेश करती है जब विशिष्ट आइटम जोड़ों $(i, s)$ को अलग-अलग बिन्स में रखा जाता है। यह परस्पर निर्भर संसाधनों (जैसे क्लाउड कंप्यूटिंग में) के बीच संचार विलंबता (communication latency) या इंटरेक्शन लागत को मॉडल करता है।
उद्देश्य: कुल लागत को कम करना, जो उपयोग किए गए बिन्स की निश्चित लागत और अलग किए गए आइटम जोड़ों के लिए क्वाड्रेटिक दंड लागत का योग है।
जटिलता: इस समस्या को NP-hard के रूप में वर्गीकृत किया गया है।

2. कार्यप्रणाली (Methodology)

लेखक एक दोहरी-दृष्टिकोण रणनीति प्रस्तावित करते हैं जो सटीक गणितीय प्रोग्रामिंग (exact mathematical programming) और एक मेटाह्यूरिस्टिक फ्रेमवर्क को जोड़ती है।

A. गणितीय लीनियराइजेशन (Mathematical Linearization)

क्वाड्रेटिक मॉडल पर सटीक सॉल्वर (जैसे Gurobi) के उपयोग को सक्षम करने के लिए, लेखकों ने एक लीनियराइज्ड मैथमेटिकल मॉडल पेश किया है।

तकनीक: ऑब्जेक्टिव फंक्शन में क्वाड्रेटिक टर्म $x_{ij}(1 - x_{sj})$ (जो यह दर्शाता है कि आइटम $i$ और $s$ अलग-अलग बिन्स में हैं) को नए बाइनरी वेरिएबल्स $z_{ijs}$ के सेट द्वारा प्रतिस्थापित किया गया है।
प्रतिबंध (Constraints): अतिरिक्त प्रतिबंध (11–13) यह सुनिश्चित करते हैं कि $z_{ijs} = 1$ तभी हो जब आइटम $i$ , बिन $j$ में हो और आइटम $s$ उसमें न हो।
लक्ष्य: यह रूपांतरण वाणिज्यिक सॉल्वरों को टighter लोअर बाउंड्स (lower bounds) की गणना करने और छोटे इंस्टेंस के लिए प्रमाणित इष्टतम समाधान खोजने में सक्षम बनाता है, जो पहले नॉन-लीनियर फॉर्मूलेशन के साथ कठिन था।

B. RKO-ACO मेटाह्यूरिस्टिक

मुख्य योगदान RKO-ACO का विकास है, जो रैंडम-की ऑप्टिमाइज़र (RKO) फ्रेमवर्क को निरंतर डोमेन (continuous domains) के लिए एंट कॉलोनी ऑप्टिमाइज़ेशन (ACO) के साथ जोड़ता है।

RKO फ्रेमवर्क:
- यह समस्या-विशिष्ट बाधाओं से सर्च इंजन को अलग करता है और निरंतर डोमेन में कार्य करता है।
- समाधानों को $[0, 1)$ में रीयल नंबर वेक्टर्स (रैंडम कीज़) के रूप में एनकोड किया जाता है।
- एक डिकोडर इन निरंतर वेक्टर्स को व्यवहार्य (feasible) डिस्क्रीट समाधानों (बिन असाइनमेंट) में मैप करता है।
कंटीन्यूअस ACO (ACOR):
- डिस्क्रीट फेरोमोन ट्रेल्स के बजाय, एल्गोरिदम निरंतर स्थान में एक एलिट सॉल्यूशंस का आर्काइव बनाए रखता है।
- नए समाधान उच्च-गुणवत्ता वाले आर्काइव सदस्यों पर केंद्रित गाऊसी वितरण (Gaussian distributions) से नमूने लेकर उत्पन्न किए जाते हैं।
सुधार (Enhancements):
- Q-Learning: एक ऑनलाइन पैरामीटर ट्यूनिंग मैकेनिज्म ACO मापदंडों (आर्काइव आकार, चयन दबाव, एक्सप्लोरेशन स्केलिंग) को समाधान सुधार के आधार पर गतिशील रूप से समायोजित करता है।
- लोकल सर्च: निरंतर स्थान में स्थानीय अनुकूलन के लिए नेल्डर-मीड (Nelder-Mead) एल्गोरिदम और डिस्क्रीट स्पेस में एक समस्या-विशिष्ट आइटम रिलोकेशन ह्यूरिस्टिक को एकीकृत करता है।
- पोस्ट-प्रोसेसिंग: लागत कम करने के लिए बिन प्रकार प्रतिस्थापन (सस्ते व्यवहार्य बिन्स में डाउनग्रेड करना) और बिन मर्जिंग शामिल है।
- कैशिंग: एक क्यू-आधारित कैशिंग सिस्टम समान डिकोड किए गए समाधानों के पुनर्मूल्यांकन से बचाता है।

3. मुख्य योगदान

प्रथम लोअर बाउंड्स: यह शोध पत्र प्रस्तावित लीनियर मॉडल द्वारा हल किए गए Gurobi का उपयोग करके QMC-VSBPP के लिए पहली बार लोअर बाउंड्स रिपोर्ट करता है।
नए बेस्ट-नोनन सॉल्यूशंस (BKS): RKO-ACO एल्गोरिदम लगातार पिछले साहित्य के सभी ज्ञात समाधानों के बराबर या उनसे बेहतर समाधान प्रदान करता है, जिससे बड़े पैमाने के इंस्टेंस के लिए नए अपर बाउंड्स स्थापित होते हैं।
फ्रेमवर्क अनुकूलन: इसने अत्यधिक प्रतिबंधित, क्वाड्रेटिक, मल्टी-डायमेंशनल पैकिंग समस्या को हल करने के लिए निरंतर ACO और Q-learning के साथ RKO फ्रेमवर्क को सफलतापूर्वक अनुकूलित किया।
बेंचमार्किंग: 96 बेंचमार्क इंस्टेंस पर एक व्यापक मूल्यांकन प्रदान किया, जिसमें सटीक सॉल्वर, पिछले साहित्य के मूल VNS (Variable Neighborhood Search) और प्रस्तावित RKO-ACO की तुलना की गई।

4. प्रयोगात्मक परिणाम

अध्ययन 96 बेंचमार्क इंस्टेंस पर किया गया, जो आइटम संख्या ( $n=25, 50, 100, 200$ ), बिन प्रकार और लागत कार्यों में भिन्न होते हैं।

सटीक सॉल्वर प्रदर्शन (Gurobi):
- लीनियराइज्ड मॉडल ने मूल क्वाड्रेटिक मॉडल की तुलना में काफी अधिक टाइट लोअर बाउंड्स दिए।
- इसने $n=25$ के लिए 4 प्रमाणित इष्टतम समाधान खोजे।
- हालांकि, बड़े इंस्टेंस ( $n \ge 50$ ) के लिए, सटीक सॉल्वर संघर्ष करते रहे, जहाँ 1 घंटे की गणना के बाद भी ऑप्टिमैलिटी गैप 80-90% से अधिक था।
RKO-ACO का प्रदर्शन:
- सफलता दर: 96 में से 96 इंस्टेंस में बेस्ट नोन सॉल्यूशन (BKS) प्राप्त किया।
- तुलना: इसने समाधान की गुणवत्ता और निरंतरता के मामले में VNS एल्गोरिदम (Meng et al., 2022) और Gurobi सॉल्वर को पछाड़ दिया।
- दक्षता: इसने सटीक सॉल्वर की तुलना में बहुत कम समय में उच्च-गुणवत्ता वाले समाधान खोजे (उदाहरण के लिए, Gurovi के प्रति इंस्टेंस 3600 सेकंड के औसत के मुकाबले सभी इंस्टेंस के लिए औसतन 92 सेकंड)।
- स्थिरता: एवरेज रिलेटिव परसेंटेज डेविएशन (ARPD) $\le 0$ था, जो दर्शाता है कि एल्गोरिदम लगातार BKS के समान या उससे बेहतर समाधान खोजने में सक्षम रहा।
एब्लेशन स्टडी (Ablation Study):
- नेल्डर-मीड लोकल सर्च को हटाने से प्रदर्शन में ~1.15% की गिरावट आई।
- Q-learning को हटाने से प्रदर्शन में ~0.5% की गिरावट आई।
- स्टैंडअलोन Continuous ACO (RKO फ्रेमवर्क के बिना) का उपयोग करने से ~2.3% की गिरावट आई, जो हाइब्रिड फ्रेमवर्क के महत्व को रेखांकित करता है।

5. महत्व और निष्कर्ष

यह कार्य QMC-VSBPP के लिए अत्याधुनिक स्थिति (state-of-the-art) को महत्वपूर्ण रूप से आगे बढ़ाता है, जिसकी क्लाउड कंप्यूटिंग संसाधन आवंटन और लॉजिस्टिक्स में महत्वपूर्ण अनुप्रयोग हैं।

सैद्धांतिक प्रभाव: यह प्रदर्शित करता है कि जटिल क्वाड्रेटिक इंटरेक्शन लागतों को लीनियर करने से मूल्यवान लोअर बाउंड्स प्राप्त किए जा सकते हैं, भले ही बड़े इंस्टेंस के लिए पूर्ण इष्टतमता सिद्ध करना कठिन हो।
व्यावहारिक प्रभाव: RKO-ACO एक मजबूत, स्केलेबल टूल प्रदान करता है जो जटिल, मल्टी-डायमेंशनल पैकिंग समस्याओं को हल करने के लिए उपयोगी है जहाँ पारंपरिक ह्यूरिस्टिक्स विफल हो जाते हैं।
भविवी दिशाएँ: लेखक और अधिक स्केलेबिलिटी के लिए हाइब्रिड सटीक-ह्यूरिस्टिक विधियों का पता लगाने और GPU आर्किटेक्चर का लाभ उठाने का सुझाव देते हैं।

संक्षेप में, यह शोध पत्र सटीक गणितीय मॉडलिंग और उन्नत मेटाह्यूरिस्टिक्स के बीच के अंतर को सफलतापूर्वक पाटता है, जो एक चुनौतीपूर्ण NP-hard समस्या के लिए नए सैद्धांतिक बाउंड्स और श्रेष्ठ व्यावहारिक समाधान दोनों प्रदान करता है।