टूल से पहले BoolVar की अधिकतम संख्या का उपयोग करना संभव नहीं है

Aug 18 2020

OR-Tools के लिए एक उदाहरण के रूप में उपयोग की जाने वाली मानक नर्स शेड्यूलिंग समस्या (उदाहरण के लिए देखें) https://developers.google.com/optimization/scheduling/employee_scheduling) कोड की निम्नलिखित पंक्ति में बूलियन चर को बूलियन मान निर्दिष्ट करने का प्रयास:

shifts[(n, d, s)] = model.NewBoolVar('shift_n%id%is%i' % (n, d, s))

इस खिलौना समस्या के लिए, OR-Tools ठीक चलता है, लेकिन केवल 105 बूलियन चर बनाए जाते हैं (5 नर्स, 7 दिन, 3 पारियां $\Rightarrow 3\times 5\times7=105$ बूलियन यह निर्दिष्ट करने के लिए कि क्या किसी दिए गए नर्स को एक शिफ्ट काम करता है)।

मैं एक अधिक यथार्थवादी वास्तविक दुनिया समयबद्धन समस्या को हल करने के लिए OR-Tools के उपयोग की खोज कर रहा हूं। मैं जिस वास्तविक दुनिया की समस्या से जूझ रहा हूं, उसके लिए 15 मिनट की वेतनवृद्धि में फेरबदल किया जाता है और इसमें अधिक श्रमिक और अधिक भूमिकाएँ शामिल होती हैं। अंत में, मुझे 11,064 बूलियनों को सौंपा जाना चाहिए।

क्या यह बहुत-से वास्तविक रूप से काम करने के लिए OR-Tools की अपेक्षा करता है? मुझे लगता है कि यह जल्दी (एक बहुत अच्छा नहीं) शेड्यूल तैयार करता है, लेकिन फिर भी अगर मैं इसे एक घंटे तक चलने देता हूं तो यह शुरुआती शेड्यूल में बिल्कुल भी सुधार नहीं करता है कि यह पहले कुछ सेकंड में आया था।

क्या OR-Tools के लिए यह विशिष्ट व्यवहार है? कोई विचार?

जवाब

4 LaurentPerron Aug 18 2020 at 19:33

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

OR-Tools एक अच्छा CP सॉल्वर है (इसने पिछले 2 मिनीज़क चुनौतियों के सभी 4 स्वर्ण पदक जीते)। यह एक सभ्य एमआईपी सॉल्वर भी है (इसने 5 खुले एमआईपीएलआईबी 2017 उदाहरणों को बंद कर दिया और कुछ और पर सीमाएं बेहतर कर दीं)।