A Group-Based Resource Allocation Model for the Fractional Knapsack Problem

तकनीकी सारांश: भिन्नात्मक (Fractional) नैपसैक समस्या के लिए एक समूह-आधारित संसाधन आवंटन मॉडल

समस्या विवरण
यह शोध पत्र बाउंडेड भिन्नात्मक (bounded fractional) नैपसैक समस्या को संबोधित करता है, जो $n$ वस्तुओं के एक सेट द्वारा परिभाषित है, जिनमें से प्रत्येक का मान $v_i$, लागत $w_i$, और क्षमता सीमा $u_i \in [0, 1]$ है, जो एक कुल बजट $C$ के अधीन है। इसका उद्देश्य $\sum w_i z_i \le C$ और $0 \le z_i \le u_i$ के अधीन कुल मान $\sum v_i z_i$ को अधिकतम करना है।

मानक समाधान, डैंट्ज़िग (Dantzig) का ग्रीडी नियम, वस्तुओं को उनके दक्षता अनुपात $\rho_i = v_i/w_i$ के आधार पर क्रमबद्ध करता है और बजट को अवरोही क्रम में आवंटित करता है। हालांकि यह इष्टतम (optimal) है, लेकिन यह दृष्टिकोण दो गंभीर समस्याओं से ग्रस्त है:

1. असततता (Discontinuity): इष्टतम समाधान मैपिंग लिप्सचिट्ज़ निरंतर (Lipschitz continuous) नहीं है। लागत डेटा में एक अत्यंत सूक्ष्म परिवर्तन भी आवंटन को सुलभ सेट के चरम शीर्षों (extreme vertices) के बीच उछालने के लिए मजबूर कर सकता है यदि बजट दो लगभग समान अनुपातों वाले मदों के बीच समाप्त हो जाता है।
2. मिथ्या रैंकिंग (Spurious Ranking): समाधान अनुपातों के सूक्ष्म अंतरों के प्रति अत्यधिक संवेदनशील है जो माप संबंधी शोर (measurement noise) से अलग पहचानना कठिन हो सकता है, जिससे अस्थिर आवंटन होता है जो वास्तविक डेटा विविधताओं को प्रतिबिंबित नहीं करते।

कार्यप्रणाली
इन अस्थिरताओं को कम करने के लिए, लेखक एक दो-चरणीय समूह-आधारित आवंटन एल्गोरिदम का प्रस्ताव करता है:

1. मैट्रिक ग्रुपिंग (Metric Grouping): वस्तुओं को एक विशेषता स्थान $(A, d)$ के आधार पर समूहों में विभाजित किया जाता है। यदि दो मदों $i$ और $j$ के बीच विशेषता दूरी $d(a_i, a_j)$, सहनशीलता त्रिज्या (tolerance radius) $\delta$ के भीतर है, तो उन्हें एक समूह में रखा जाता है। प्रत्येक समूह $G_k$ के भीतर, मद एक प्रतिनिधि विशेषता $b_{a_k}$ साझा करते हैं, जिससे प्रतिनिधि मान $b_{v_k}$, लागत $b_{w_k}$, और अनुपात $b_{\rho_k}$ प्राप्त होता है।
2. चरण 1 (अंतर-समूह आवंटन): समूहों को उनके प्रतिनिधि अनुपातों $b_{\rho_k}$ के आधार पर अवरोही क्रम में रैंक किया जाता है। बजट का हिस्सा समूहों को क्रमिक रूप से तब तक आवंटित किया जाता है जब तक कि बजट समाप्त न हो जाए। जिस समूह में बजट समाप्त होता है, उसे "सीमा समूह" ($\Gamma$) घोषित किया जाता है। इससे पहले के सभी समूहों को पूर्ण वित्त पोषण मिलता है; उसके बाद के सभी समूहों को शून्य प्राप्त होता है।
3. चरण 2 (अंतः-समूह आवंटन): सीमा समूह $\Gamma$ के लिए, आवंटित बजट हिस्से को बिना किसी और रैंकिंग के इसके सदस्यों के बीच वितरित किया जाता है। यह वितरण "अंतः-समूह नियमों" (व्यवहार्यता, बजट निकासी, और समान संरक्षण) का पालन करता है, जो गणितीय रूप से एक "वॉटर-फिलिंग" (water-filling) तंत्र के समान है। विशेष रूप से, एक आवंटन स्तर $\zeta$ खोजा जाता है ऐसा कि $\sum_{i \in \Gamma} w_i \min(u_i, \zeta) = c^*$, जहाँ $c^*$ शेष बजट है। $\Gamma$ के सभी मदों को $\min(u_i, \zeta)$ प्राप्त होता है।

प्रमुख योगदान और सैद्धांतिक गारंटी

• स्थिरता (लिप्सचिट्ज़ निरंतरता): सटीक ग्रीडी समाधान के विपरीत, समूहित आवंटन लागत परिवर्तनों के संबंध में लिप्सचिट्ज़ निरंतर है, बशर्ते कि परिवर्तन आसन्न समूहों के बीच पृथक्करण मार्जिन के भीतर रहे। इसकी निरंतरता का मापांक (modulus of continuity) $K/w_{\min}$ द्वारा सीमित है, जहाँ $K$ अधिकतम समूह आकार है। यह सुनिश्चित करता है कि आवंटन शोर के कारण नाटकीय रूप से नहीं बदलता है।
• हानि सीमाएँ (Loss Bounds):
  • अंतः-समूह हानि: एक समूह के भीतर हानि समूह की क्षमता $U_G$ और सापेक्ष लागत भिन्नता $(w_+ - w_-)/(w_+ + w_-)$ के अनुपात में एक पद, साथ ही मान भिन्नता के लिए एक पद द्वारा सीमित है। यह दर्शाया गया है कि यह सीमा सटीक (tight) है।
  • वैश्विक हानि: यदि ग्रुपिंग "क्रम-संगत" (order-compatible) है (समूहों के अनुपात अंतराल विसंयुक्त और सख्ती से घटते क्रम में हैं), तो कुल हानि $E(C)$ पूरी तरह से सीमा समूह $\Gamma$ के भीतर सीमित है। सापेक्ष हानि $O(K/n)$ के रूप में स्केल करती है, जिसका अर्थ है कि यदि समूह का आकार $K$ सीमित रहता है, तो वस्तुओं की संख्या $n$ बढ़ने के साथ त्रुटि कम होती जाती है।
  • गैर-क्रम-संगत मामला: यदि समूह अनुपात अंतराल $\omega$ की अधिकतम मात्रा तक ओवरलैप करते हैं, तो त्रुटि सीमा में एक योगात्मक पद $\omega C$ जोड़ा जाता है।
• जटिलता (Complexity): एल्गोरिदम $O(n + m \log m + |\Gamma| \log |\Gamma|)$ समय में आवंटन की गणना करता है, जहाँ $m$ समूहों की संख्या है। यदि सीमा समूह को लीनियर-टाइम सिलेक्शन के माध्यम से पहचाना जाता है, तो जटिलता $O(n + m \log m)$ हो जाती है। यदि प्रतिनिधि अनुपात पूर्व-क्रमबद्ध (pre-sorted) हैं, तो यह $O(n)$ प्राप्त करता है।

प्रायोगिक परिणाम
लेखक यादृच्छिक रूप से उत्पन्न उदाहरणों पर डैंट्ज़िग के ग्रीडी नियम के विरुद्ध विधि का मूल्यांकन करता है:

• साइज ($n$) के विरुद्ध हानि: एक निश्चित सहनशीलता $\delta$ के लिए, बहुत छोटे $n$ के लिए सापेक्ष हानि शून्य है (जहाँ समूह एकल सदस्य हैं)। जैसे-जैसे $n$ बढ़ता है, हानि बढ़ती है और फिर एक स्थिर पठार (लगभग 6%) पर स्थिर हो जाती है। यह इस सैद्धांतिक भविष्यवाणी की पुष्टि करता है कि हानि $\delta$ पर निर्भर करती है लेकिन बड़े उदाहरणों के लिए $n$ से स्वतंत्र है।
• सहनशीलता ($\delta$) के विरुद्ध हानि: हानि $\delta$ के साथ बहुपद (polynomially) रूप से बढ़ती है। बहुत छोटे $\delta$ के लिए, हानि नगण्य है, जो प्रभावी रूप से सटीक इष्टतम से मेल खाती है। जैसे-जैसे $\delta$ बढ़ता है, हानि बढ़ती है जब तक कि ग्रुपिंग एक एकल समूह में सिमट नहीं जाती, जिस बिंदु पर हानि संतृप्त (saturate) हो जाती है।
• रनटाइम: समूहित विधि डैंट्ज़िग के नियम के समान प्रायोगिक विकास दर प्रदर्शित करती है। छोटे उदाहरणों पर, यह ग्रुपिंग और सॉर्टिंग के कारण एक स्थिर ओवरहेड लेती है, लेकिन $10^6$ तक के बड़े $n$ के लिए, रनटाइम लगभग अविभाज्य है, जिसमें समूहित विधि अधिकतम दो गुना धीमी है।

महत्व और दावे
यह शोध पत्र दावा करता है कि समूहित आवंटन मॉडल इष्टतमता और स्थिरता के बीच एक व्यावहारिक समझौता प्रदान करता है। एक विशेषता अंतर दहलीज $\delta$ से नीचे के मदों को रैंक करने से इनकार करके, यह विधि सटीक समाधान की माप संबंधी शोर के प्रति मिथ्या संवेदनशीलता को समाप्त करती है। लेखक का तर्क है कि यह दृष्टिकोण:

1. व्यवहार्य क्षेत्र और उद्देश्य फलन (objective function) को सुरक्षित रखता है, केवल समूहों के भीतर आंतरिक आवंटन नियम को प्रतिबंधित करता है।
2. एक बाधित विचलन भागफल (लिप्सचिट्ज़ स्थिरांक) प्रदान करता है जहाँ सटीक समाधान के पास कोई नहीं है।
3. मानक ग्रीडी दृष्टिकोण के तुल्य कम्प्यूटेशनल दक्षता बनाए रखता है, जिससे यह सीमित डेटा सटीकता वाले बड़े पैमाने के अनुप्रयोगों के लिए व्यवहार्य बनता है।

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