PARTITION $N$ में आइटम $K$ मूल मदों में समूहों को बनाए रखते हुए समान रूप से विभाजन
मान लीजिए कि वहाँ हैं $N$ जो आइटम आते हैं $M$समूह। लश्कर$c_i \in \{1, ..., M\}$ के लिये $i=1, ..., N$ आइटम के लिए समूह सदस्यता का प्रतिनिधित्व करते हैं $i$। मैं वस्तुओं के एक मोटे विभाजन का पता लगाना चाहूंगा$K$ नए समूह, जहां $K < M$, दो बाधाओं के साथ:
- एक ही समूह में आइटम एक ही विभाजन को सौंपा जाना चाहिए, और
- नए समूह का आकार यथासंभव समीप होना चाहिए।
मेरा प्रारंभिक विचार यह है कि इसे गैर-रेखीय पूर्णांक प्रोग्राम के रूप में तैयार किया जाए, जहां $y_{ij} = 1$ अगर आइटम $i$ विभाजन को सौंपा गया है $j$और अन्यथा शून्य है। तो मैं बाधाओं का एक सेट होगा:
- $\sum_{j=1}^K y_{ij} = 1$ के लिये $i=1,..., N$ (प्रत्येक आइटम को ठीक एक विभाजन को सौंपा जाना चाहिए)
- $y_{ij} = y_{\ell j}$ सभी के लिए $j=1, ..., K$ अगर $c_i = c_\ell$ (एक ही समूह में आइटम एक ही विभाजन को सौंपा जाना चाहिए)
और तब मैं परिभाषित कर सकता था $N_j = \sum_{i=1}^N y_{ij}$ और कम से कम
$$\sum_{j=1}^K \left(N_j - \frac NK \right)^2.$$
हालांकि, विशेष उद्देश्य वास्तव में यहाँ मायने नहीं रखता है। जब तक$N_j$ के पास है $N/K$ सभी के लिए $j$, मुझे परवाह नहीं है अगर यह एक में है $\ell_2$ या $\ell_1$ भावना या कुछ और उन पंक्तियों के साथ अस्पष्ट।
मेरे सवाल:
- क्या विशेष रूप से आसान समाधान के साथ इस समस्या का एक बेहतर सूत्रीकरण है?
- क्या एल्गोरिदम इस समस्या को बिल्कुल हल करेगा? क्या तेजी से लालची अनुमानित समाधान प्राप्त करने के तरीके हैं?
- मुझे लगता है कि मुझे अपना समाधान पाने के लिए कुछ मौजूदा अनुकूलन सॉफ्टवेयर का लाभ उठाने की आवश्यकता है। क्या पायथन / जूलिया / आर उपयोगकर्ता के लिए यहां कोई मानक विकल्प हैं? (कोड नमूने बहुत सराहना की!)
कुछ अतिरिक्त पृष्ठभूमि: मैं अनिवार्य रूप से छुट्टी-समूह-आउट क्रॉस सत्यापन के लिए एक अधिक (कम्प्यूटेशनल) कुशल दृष्टिकोण की तलाश कर रहा हूं। वर्तमान मानक एक बार में एक एकल समूह को छोड़ देता है, जैसे कि आप फिट होते हैं$M$ मॉडल, कहाँ $M$काफी अधिक हो सकता है। व्यवहार में, कुछ इस तरह$K=5$ या $K=10$सांख्यिकीय उद्देश्य के लिए पर्याप्त है, और क्रॉस सत्यापन में वे गुण होंगे जो हम लंबे समय तक चाहते हैं क्योंकि एक ही समूह में हर कोई एक ही गुना में जाता है और सिलवटों का आकार लगभग एक जैसा होता है। इतनी फिटिंग$M >> 10$ मॉडल जब कई समूह होते हैं तो अक्सर अक्षम और अनावश्यक होते हैं।
जवाब
एक दृष्टिकोण यह है कि समूहों को नौकरियों के रूप में सोचना है, प्रत्येक नौकरी की अवधि के साथ अपने समूह में मदों की संख्या के बराबर है। अब इन नौकरियों को शेड्यूल करें$K$ समान मशीनें, मेकपैन को छोटा करती हैं, अर्थात कम से कम $\max_j N_j$। एलपीटी अनुमानी तेज है और पैदावार ए$(2-1/K)$-परिवर्तन।
पहला प्रश्न: आईपी मॉडल में आपको आइटम और विभाजन के प्रत्येक संयोजन के लिए एक बाइनरी चर की आवश्यकता नहीं है। आपकी आवश्यकता को देखते हुए कि समूहों को एक साथ रखा जाए, आपको बस समूह और विभाजन के प्रत्येक संयोजन के लिए एक बाइनरी की आवश्यकता होती है। तुम्हारी$y_{ij}=y_{\ell j}$बाधाएं सॉल्वर के प्रिजर्व फंक्शन को इस आकार के नीचे मॉडल को सिकोड़ देती हैं, लेकिन आप छोटे फॉर्मूलेशन के साथ ही शुरू कर सकते हैं। इसके अलावा, समस्या को द्विघात बनाने के बजाय, मैं शायद सबसे छोटे और सबसे बड़े विभाजन आकार के बीच अंतर को कम कर दूंगा, जो रैखिक है। यह आवश्यक रूप से मॉडल को हल करने के लिए "विशेष रूप से आसान" का उत्पादन नहीं करता है, लेकिन आपकी समस्या के आयाम और आपके आईपी सॉल्वर (और आपके धैर्य) के आधार पर, यह काफी आसान हो सकता है।
दूसरा प्रश्न: आप आईपी मॉडल और एक आईपी सॉल्वर का उपयोग करके समस्या को हल कर सकते हैं। एक तेजी से विधर्मी जो काफी अच्छी तरह से कर सकता है, उसके साथ शुरू करना है$K$ खाली विभाजन, समूहों को अवरोही आकार क्रम में क्रमबद्ध करते हैं, फिर प्रत्येक समूह को वर्तमान में सबसे छोटे विभाजन में असाइन करते हैं।
तीसरा प्रश्न: मैं जूलिया या पाइथन के लिए नहीं बोल सकता (हालाँकि मुझे पायथन के लिए कुछ आईपी सॉल्वरों का पता है), लेकिन मॉडल लिखने के लिए आरआई के साथ ओएमपीआर पैकेज (एलपी / आईपी के लिए एक डीएसएल) का उपयोग करने की इच्छा होगी। OMPR बदले में मॉडल को हल करने के लिए ROI पर निर्भर करेगा, और OMPR और ROI दोनों के लिए आपको एक सॉल्वर-विशिष्ट प्लग-इन लोड करना होगा (और, निश्चित रूप से, इसी सॉल्वर को स्थापित करने के लिए)।
मैंने उनके संबंधित CPLEX प्लग-इन के साथ OMPR और ROI का उपयोग करके एक R नोटबुक को हैक किया। के साथ एक यादृच्छिक परीक्षण समस्या पर$N=5700$, $M=130$ तथा $K=10$, मेरे द्वारा बताए गए अनुमान को आम तौर पर 5 के विभाजन का आकार मिला (567 से 572 तक का आकार), और आईपी मॉडल को 570 (प्रसार = 0) के दस विभाजन मिले। विधर्मी ने एक दूसरे का एक छोटा (छोटा) अंश लिया। IP मॉडल का निर्माण और CPLEX के साथ इसे हल करने में लगभग नौ सेकंड लगे।
हमेशा की तरह, आपका माइलेज अलग-अलग होगा।
ADDENDUM: मुझे संदेह है (सही ढंग से) कि समस्या के आयामों के लिए गोल संख्याओं का उपयोग करने से चीजें अच्छी हो सकती हैं, इसलिए मैंने कोशिश की $N=5723$, $M=137$ तथा $K=10$(जो यह सुनिश्चित करता है कि किसी भी समाधान में सभी विभाजन आकार समान नहीं हैं)। आईपी समाधान 1 के प्रसार को प्रबंधित करता है (कुछ विभाजन में 572 आइटम थे, कुछ में 573 था, जो अभी भी मेरे विचार से बेहतर है जो आमतौर पर प्राप्त करने योग्य है)। हेयुरिस्टिक समाधान में 30 का फैलाव था (विभाजन का आकार 552 से 582 तक था)।
ADDENDUM 2: रोबर्ट को एलपीटी कहने वाले रोबर्ट के बाद मैंने जोड़ीदार इंटरचेंज हेयुरिस्टिक जोड़ा। के साथ उदाहरण में$N=5723$आदि, जोड़ीदार स्वैप हेयुरिस्टिक ने 30 से 2 तक प्रसार को कम कर दिया, काफी इष्टतम नहीं (इष्टतम 1) लेकिन बहुत करीब। एलपीटी की तरह, स्वैपिंग हेयुरिस्टिक ने इस उदाहरण पर एक सेकंड के तहत अच्छी तरह से लिया।