mathematical optimization - बेस्ट ओपन सोर्स मिश्रित पूर्णांक अनुकूलन सॉल्वर




mathematical-optimization linear-programming (9)

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

मैं बड़े ऑप्टिमाइज़ेशन मॉडल (100k से अधिक चर) को सुलझाने के लिए सीपीएलएक्स का उपयोग कर रहा हूं, अब मैं देखना चाहता हूं कि क्या मुझे एक ओपन सोर्स विकल्प मिल सकता है, मैं मिश्रित पूर्णांक समस्याएं हल करता हूं (एमआईएलपी) और सीपीएलएक्स महान काम करता है, लेकिन यह बहुत महंगा है अगर हम स्केल करना चाहते हैं, इसलिए मुझे वास्तव में एक वैकल्पिक खोजना होगा या हमारे अपने विज्ञापन-एचओसी ऑप्टिमाइज़ेशन लाइब्रेरी लिखना शुरू करना होगा (जो कि दर्दनाक होगा)

कोई सुझाव / अंतर्दृष्टि बहुत सराहना की जाएगी


मैं COIN परियोजना की जांच करने की सलाह देता हूं सीओआईएन या

यहां कई अच्छे सॉलर्स शामिल हैं, जिनमें आईपीओपीटी गैर-रेखीय समस्याओं के लिए और कुछ मिश्रित पूर्णांक समाधान भी शामिल हैं।


COIN-OR के लिए एक और सुझाव। हमने पाया कि रैखिक अनुकूलक घटक (सीएलपी) बहुत मजबूत था, और कुछ विश्लेषण के साथ मिश्रित पूर्णांक घटक (सीबीसी) काफी अच्छी तरह से ट्यून किया जा सकता है। हमने एलपी-समाधान और जीएलपीके के साथ तुलना की।

वास्तव में कठिन समस्याओं के लिए, एक वाणिज्यिक सॉल्वर जाने का रास्ता है।



ओपन सोर्स नहीं, लेकिन अगर आपके पास माइक्रोसॉफ्ट अकादमी एलायंस लाइसेंस है, तो माइक्रोसॉफ्ट सॉल्वर फाउंडेशन (एमएसएफ) एंटरप्राइज संस्करण शामिल है। गुरुबी शैक्षिक उद्देश्यों के लिए भी मुफ़्त है, मैंने अपने शोध अनुसंधान में इसका इस्तेमाल किया है।


यद्यपि यह शायद नहीं है जो आप सुनना चाहते हैं, लेकिन एक ओर वाणिज्यिक हलकों CPLEX और Gurobi और दूसरी तरफ ओपन सोर्स solvers के बीच प्रकाश वर्ष हैं।

फिर भी आप भाग्यशाली हो सकते हैं और आपका मॉडल जीएलपीके, सिक्का या पसंद के साथ ठीक काम करता है, लेकिन सामान्य तौर पर खुला स्रोत समाधान वाणिज्यिक समाधानों के पीछे हैं अगर यह अलग था, कोई भी एक Gurobi लाइसेंस के लिए 12.000 $ का भुगतान नहीं करेगा और एक CPLEX लाइसेंस के लिए और भी अधिक।

पिछले वर्षों में मैंने बहुत सारे, कई मॉडल देखे हैं जो ओपन सोर्स सॉल्वर के लिए मुश्किल थे। मुझ पर विश्वास करो...

यह आकार का प्रश्न नहीं है, बल्कि संख्यात्मक कठिनाई का है।


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

अगर आप को हल करने वाला पूर्णांक प्रोग्राम बहुत बड़ा है, तो मैं सी ++ पर अजगर का सुझाव दूंगा, क्योंकि आप कोड क्लीनर देखेंगे और 99% समय सॉल्वर में खर्च किया जाएगा।

यदि, इसके विपरीत, समस्याएं छोटी हैं, तो अजगर की स्मृति से सॉल्वर (पीछे और पीछे) की समस्याओं की नकल करने का समय अब ​​और उपेक्षा नहीं किया जा सकता है: उस मामले में आप एक संकलित भाषा का उपयोग करके कुछ ध्यान देने योग्य प्रदर्शन सुधारों का प्रयोग कर सकते हैं ।

लेकिन अगर समस्याएं बहुत भारी हैं, तो संकलित भाषाएं फिर से जीतने जा रही हैं, क्योंकि स्मृति पदचिह्न को मोटे तौर पर 2 से विभाजित किया जाएगा (अजगर में समस्या की कोई प्रति)।


मैं पहले से ही उत्कृष्ट उत्तर के लिए निम्नलिखित जोड़ देंगे

हालांकि, जैसा कि अन्य ने बताया है, वाणिज्यिक समाधान बहुत आसान और नि: शुल्क विकल्पों की तुलना में अधिक सक्षम हैं, यह समझना महत्वपूर्ण है कि आप कितने ऑप्टिमाटिबल अंतर को स्वीकार कर सकते हैं। कई इंटिजर वेरिएबल के साथ बड़ी समस्याओं के लिए यदि आप 1% या इससे भी अधिक अनुकूलतम अंतर (चूक के करीब 0.01% या उससे कम हो) स्वीकार कर सकते हैं, तो आप बहुत तेज़ समाधान प्राप्त कर सकते हैं।

बेशक अगर आप एक समस्या हल कर रहे हैं जहां 1% करोड़ों डॉलर में अनुवाद किया जाता है तो यह स्वीकार्य नहीं है - इसलिए शीर्ष पायदान solvers के लिए बाजार। ( यहां से मुक्त solvers के लिए Gurobi की कुछ तुलना)

मैं अन्य लोगों से सहमत हूं कि सॉल्वर-स्वतंत्र समस्या फ़ाइलों (जैसे * .mps, * .lp फाइलें) उत्पन्न करने वाली एक प्लेटफॉर्म का उपयोग करना उपयुक्त है क्योंकि आप फिर से अन्य सॉल्वरों को आज़मा सकते हैं मैं पीयूएलपी का उपयोग कर रहा हूं और इसे ढूंढ रहा हूं, और मुक्त COIN_CBC सॉल्वर, उत्कृष्ट। हालांकि कई पूर्णांक चर के साथ समस्याओं के लिए सीमित है


मुझे आश्चर्य है कि किसी ने भी एमआईपीसीएल ( http://www.mipcl-cpp.appspot.com/index.html ) का उल्लेख नहीं किया है। यह एलजीपीएल लाइसेंस (स्रोत: http://www.mipcl-cpp.appspot.com/licence.html ) के तहत खुला स्रोत है, इस प्रकार गैर-ओपन सोर्स अनुप्रयोगों में भी उपयोग करने के लिए उपयुक्त है।

हाल ही में (10 सितंबर 2017) हंस मित्तलमान ने मिश्रित पूर्णांक रैखिक प्रोग्रामिंग बेंचमार्क: http://plato.asu.edu/ftp/milpc.html (आप भी ओवरव्यू पेज http: //plato.asu पर ध्यान देने में दिलचस्पी रख सकते हैं .edu / bench.html या उनके भाषण की स्लाइड्स: http://plato.asu.edu/talks/informs2017.pdf )।

मिश्रित पूर्णांक रैखिक प्रोग्रामिंग बेंचमार्क में 12 धागे के साथ और 2 घंटे की समय सीमा एमआईपीसीएल ने 79 मामलों को हल करने में कामयाब रहा। केवल वाणिज्यिक समाधान CPLEX, गुरुबी और एक्सप्रेस ने दिए गए बाधाओं (क्रमशः 86 या 87 उदाहरणों) के तहत अधिक हल करने में कामयाब रहे।

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