तकनीकी सारांश: मैक्सिमली डाइवर्स ग्रुपिंग प्रॉब्लम के लिए (मिश्रित-) पूर्णांक रैखिक प्रोग्रामिंग सूत्रीकरणों का एक विश्लेषण

समस्या की परिभाषा

मैक्सिमली डाइवर्स ग्रुपिंग प्रॉब्लम (MDGP) एक शास्त्रीय NP-hard कॉम्बिनेटरियल ऑप्टिमाइज़ेशन समस्या है। वस्तुओं के एक सेट $I$ और समूहों के एक सेट $G$ को देखते हुए, इसका उद्देश्य प्रत्येक वस्तु को ठीक एक समूह में इस प्रकार आवंटित करना है कि समूहों के भीतर कुल विविधता (diversity) अधिकतम हो। एक जोड़ी $(i, j)$ की विविधता को एक पैरामीटर $d_{ij} \geq 0$ द्वारा परिभाषित किया जाता है। कुल विविधता एक ही समूह में आवंटित वस्तुओं के लिए सभी युग्मवार विविधताओं का योग है। समस्या प्रत्येक समूह $g \in G$ के लिए निचली सीमा $l_g$ और ऊपरी सीमा $u_g$ द्वारा परिभाषित वस्तुओं की संख्या के प्रति संवेदनशील है।

MDGP के अनुप्रयोगों में छात्रों को समूहों या पाठ्यक्रमों में आवंटित करना, प्रोजेक्ट टीमें बनाना, समीक्षक समूह बनाना और अंतिम परीक्षाओं का शेड्यूलिंग करना शामिल हैं। साहित्य में अनुमानी (heuristic) दृष्टिकोण आम हैं, जबकि सटीक समाधान विधियाँ ऐतिहासिक रूप से छोटे समस्या उदाहरणों तक ही सीमित रही हैं।

कार्यप्रणाली और मॉडल सूत्रीकरण

यह शोध पत्र चार अलग-अलग (मिश्रित-) पूर्णांक रैखिक प्रोग्रामिंग (MILP) सूत्रीकरणों का विश्लेषण और तुलना करता है:

1. मानक सूत्रीकरण (वीत्ज़ और लक्ष्मिनारायणन, 1998):

   • चर (Variables): बाइनरी चर $x_{ig}$ यह दर्शाते हैं कि वस्तु $i$ को समूह $g$ में आवंटित किया गया है या नहीं। सहायक बाइनरी चर $y_{ijg}$ यह दर्शाते हैं कि क्या वस्तुएं $i$ और $j$ दोनों समूह $g$ में हैं।
   • तंत्र (Mechanism): उद्देश्य को बाधाओं $y_{ijg} \leq x_{ig}$ और $y_{ijg} \leq x_{jg}$ का उपयोग करके रैखिकीकृत (linearized) किया जाता है।
   • कमजोरी: लीनियर प्रोग्रामिंग (LP) रिलैक्सेशन कमजोर है। रिलैक्सेशन में, वस्तुओं को सभी समूहों में आंशिक रूप से आवंटित किया जा सकता है ($x_{ig} = 1/|G|$), जिससे उद्देश्य का मान सभी संभावित $d_{ij}$ जोड़ों का योग हो जाता है, जो व्यवहार्य पूर्णांक समाधानों के लिए एक अप्राप्य ऊपरी सीमा है।

2. पापेनबर्ग और क्लाउ सूत्रीकरण (2021):

   • चर: बाइनरी चर $z_{ij}$ यह दर्शाते हैं कि वस्तुएं $i$ और $j$ एक ही समूह में हैं, बिना यह निर्दिष्ट किए कि कौन सा समूह।
   • तंत्र: निरंतरता (transitivity) सुनिश्चित करने के लिए ट्रांसिटिविटी बाधाओं (जैसे, $-z_{ij} + z_{ik} + z_{jk} \leq 1$) का उपयोग करता है और एक बाधा जो यह सुनिश्चित करती है कि प्रत्येक वस्तु $|I|/|G| - 1$ अन्य वस्तुओं के साथ समूहबद्ध है।
   • शक्ति: ब्रांचिंग आइटम-आइटम असाइनमेंट ($z_{ij}$) पर होती है, जो सीधे उद्देश्य फलन (objective function) को प्रभावित करती है। LP रिलैक्सेशन काफी मजबूत है क्योंकि बाधाएं प्रति आइटम जोड़ों की संख्या को समूह के आकार तक सीमित करती हैं।
   • सीमा: मूल रूप से केवल समान-आकार के समूहों के लिए डिज़ाइन किया गया था।

3. संयुक्त सूत्रीकरण:

   • तंत्र: $z_{ij} = \sum_{g \in G} y_{ijg}$ को जोड़कर मानक सूत्रीकरण और पापेनबर्ग और क्लाउ दृष्टिकोण को मिलाता है।
   • योगदान: मानक मॉडल में ट्रांसिटिविटी बाधाओं को जोड़ता है और विविध आकारों के लिए समूह आकार बाधाओं को अनुकूलित करता है। यह शोध पत्र सिद्ध करता है कि समान-आकार के समूहों के लिए, इस सूत्रीकरण का LP रिलैक्सेशन पापेनबर्ग और क्लाउ के सूत्रीकरण के कम से कम उतना ही मजबूत है।

4. अनुकूलित पापेनबर्ग और क्लाउ सूत्रीकरण (परिवर्तनीय समूह आकार के लिए):

   • तंत्र: विविध समूह आकारों ($l_g \neq u_g$) को संभालने के लिए पापेनबर्ग और क्लाउ मॉडल का विस्तार करता है, जिसमें प्रत्येक समूह के लिए एक "डमी आइटम" पेश किया जाता है।
   • चर: वस्तुओं को डमी आइटम्स (जो समूहों का प्रतिनिधित्व करते हैं) को डमी आइटम्स के माध्यम से सौंपा जाता है $z_{i, \text{dummy}}$।
   • बाधाएं: ट्रांसिटिविटी बाधाएं सभी वस्तुओं सहित डमी पर लागू होती हैं। बाधाएं सुनिश्चित करती है कि प्रत्येक वास्तविक वस्तु को ठीक एक डमी समूह को सौंपा गया है, और प्रत्येक डमी के आसपास का आकार $l_g$ और $u_g$ का पालन करता है।

मुख्य योगदान

• तुलनात्मक विश्लेषण: शोध पत्र मानक आइटम-समूह असाइनमेंट सूत्रीकरण बनाम आइटम-आइटम असाइनमेंट का सैद्धांतिक और अनुभवजन्य तुलना प्रदान करता है।
• सैद्धांतिक अंतर्दृष्टि: यह प्रदर्शित करता है कि आइटम-समूह असाइनमेंट चरों ($x_{ig}$) के बजाय आइटम-आइटम असाइनमेंट चरों ($z_{ij}$) पर ब्रांचिंग करना बेहतर है क्योंकि पूर्व सीधे उद्देश्य फलन के मान को प्रतिबंधित करता है और एक सख्त (tighter) LP रिलैक्सेशन प्रदान करता है।
• नए सूत्रीकरण: विविध समूह आकारों के सामान्य मामले को संभालने के लिए दो नए सूत्रीकरण प्रस्तुत किए गए हैं, जो मजबूत आइटम-आइटम असाइनमेंट तर्क की प्रयोज्यता का विस्तार करते हैं।
• सिमेट्री ब्रेकिंग (Symmetry Breaking): शोध पत्र मानक सूत्रीकरण के लिए सिमेट्री-ब्रेकिंग बाधाओं पर चर्चा करता है और उन्हें सामान्य मामले में स्थानांतरित करता है।

कम्प्यूटेशनल परिणाम

10 से 30 वस्तुओं और 2 से 10 समूहों वाले उदाहरणों का उपयोग करके CPLEX 12.9 पर एक व्यापक कम्प्यूटेशनल अध्ययन किया गया। समान-आकार और परिवर्तनशील-आकार दोनों समूह परिदृश्यों का परीक्षण किया गया।

• LP रिलैक्सेशन की गुणवत्ता: पापेनबर्ग और क्लाउ सूत्रीकरण और इसके अनुकूलन ने मानक सूत्रीकरण की तुलना में लगातार काफी सख्त ऊपरी सीमाएं (छोटे गैप) उत्पन्न कीं। मानक सूत्रीकरण के LP रिलैक्सेशन गैप अक्सर 100% से अधिक थे, जबकि आइटम-आइटम सूत्रीकरण बहुत कम रहे।
• समाधान प्रदर्शन:
  • समान-आकार के समूह: पापेनबर्ग और क्लाउ सूत्रीकरण ने लगभग सभी उदाहरणों को मानक सूत्रीकरण की तुलना में तेजी से इष्टतम (optimality) तक हल किया।
  • परिवर्तनीय समूह आकार: अनुकूलित पापेनबर्ग और क्लाउ सूत्रीकरण (अनुभाग 3.4) सबसे अच्छा प्रदर्शन करता है, जिसने 1800 सेकंड की समय सीमा के भीतर 30 वस्तुओं तक के उदाहरणों को इष्टतम रूप से या छोटे गैप के साथ हल किया।
  • मानक सूत्रीकरण: काफी संघर्ष करता रहा, अक्सर समय सीमा के भीतर 15 से अधिक वस्तुओं वाले उदाहरणों के गैप को बंद करने या हल करने में विफल रहा।
  • संयुक्त सूत्रीकरण: हालांकि सैद्धांतिक रूप से मजबूत है, संयुक्त सूत्रीकरण ने $x_{ig}$ चरों पर ब्रांचिंग करने पर मानक सूत्रीकरण की तुलना में कोई महत्वपूर्ण प्रदर्शन सुधार नहीं दिखाया, जिससे पता चलता है कि केवल ट्रांसिटिविटी बाधाएं $x_{ig}$ ब्रांचिंग रणनीति की कमजोरी को दूर करने के लिए पर्याप्त नहीं हैं।

महत्व और दावे

शोध पत्र का दावा है कि नए सूत्रीकरण के बेहतर प्रदर्शन का प्राथमिक चालक ब्रांचिंग रणनीति है। आइटम-समूह असाइनमेंट के बजाय आइटम-आइटम असाइनमेंट पर ब्रांचिंग करके, सॉल्वर ट्रांसिटिविटी बाधाओं द्वारा प्रदान किए गए मजबूत LP रिलैक्सेशन के कारण खोज स्थान (search space) को अधिक प्रभावी ढंग से काट (prune) सकता है।

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