• पूर्णांक ऑप्टिमाइज़ेशन

लीनियर ऑप्टिमाइज़ेशन के ऐसे सवाल जिनके कुछ वैरिएबल का पूर्णांक होना ज़रूरी है, उन्हें मिक्स्ड इंटीजर प्रोग्राम (एमआईपी) कहा जाता है.

ये वैरिएबल कई तरह से बन सकते हैं:

  • इंटीजर वैरिएबल में कार या टेलीविज़न सेट जैसे आइटम की संख्या दिखाई जाती है. इनमें सबसे बड़ी समस्या यह तय करना है कि ज़्यादा से ज़्यादा मुनाफ़ा पाने के लिए हर आइटम को कितने में बनाया जाना है.
    आम तौर पर, इस तरह के सवालों को स्टैंडर्ड लीनियर ऑप्टिमाइज़ेशन समस्याओं के तौर पर सेट अप किया जा सकता है. इसके लिए, वैरिएबल के पूर्णांक होना ज़रूरी है. अगले सेक्शन में इस तरह की समस्या का एक उदाहरण दिया गया है.

  • बूलियन वैरिएबल जो 0-1 वैल्यू वाले फ़ैसले दिखाते हैं.
    उदाहरण के लिए, एक ऐसी समस्या पर ध्यान दें जिसमें वर्कर को टास्क असाइन करना शामिल है ( असाइनमेंट देखें). इस तरह की समस्या को सेट अप करने के लिए, बूलियन वैरिएबल xi,j बनाए जा सकते हैं. अगर वर्कर i को टास्क j को असाइन किया गया है, तो यह 1 के बराबर होता है, नहीं तो 0 होता है.

पूर्णांक ऑप्टिमाइज़ेशन के बारे में अच्छी जानकारी पाने के लिए, हम Mosek मॉडलिंग कुकबुक का इस्तेमाल करने का सुझाव देते हैं.

टूल

Google, एमआईपी समस्याओं को हल करने के कुछ तरीके उपलब्ध कराता है:

  • MPSolver: तीसरे पक्ष के कई MIP सॉल्वर के लिए एक रैपर, जो स्टैंडर्ड ब्रांच ऐंड बाउंड तकनीकों का इस्तेमाल करता है.
  • सीपी-एसएटी सॉल्वर: यह एक कंस्ट्रेंट प्रोग्रामिंग सॉल्वर है, जो एसएटी (संतोषजनकता) के तरीकों का इस्तेमाल करता है.
  • ओरिजनल सीपी सॉल्वर: कंस्ट्रेंट प्रोग्रामिंग सॉल्वर.

मुझे किस सॉल्वर का इस्तेमाल करना चाहिए?

एमआईपी सॉल्वर का इस्तेमाल करना है या CP-SAT सॉल्वर का. मोटे तौर पर गाइड के तौर पर:

  • एमआईपी सॉल्वर उन समस्याओं के लिए बेहतर विकल्प होते हैं जिन्हें स्टैंडर्ड एलपी के तौर पर सेट अप किया जा सकता है. हालांकि, आर्बिट्रेरी पूर्णांक वैरिएबल के साथ इनका इस्तेमाल करना बेहतर होता है, जैसा कि ऊपर दिए गए उदाहरण में बताया गया है.
  • जैसा कि ऊपर दिए गए दूसरे उदाहरण में बताया गया है, CP-SAT सॉल्वर ऐसे सवालों के लिए बेहतर विकल्प है जिनमें ज़्यादातर वैरिएबल बूलियन होते हैं.

पूर्णांक और बूलियन, दोनों तरह के वैरिएबल वाले एमआईपी के लिए, अक्सर दो सॉल्वर की स्पीड में कोई अंतर नहीं होता. इसलिए, आपकी पसंद को प्राथमिकता दी जा सकती है.

MIP और CP-SAT सॉल्वर का इस्तेमाल करने वाले उदाहरणों के लिए, असाइनमेंट से जुड़ी समस्या हल करना और असाइनमेंट वाले अन्य सेक्शन देखें.

इंटीजर प्रोग्रामिंग से जुड़ी समस्याओं को हल करने का एक और तरीका है, नेटवर्क फ़्लो सॉल्वर का इस्तेमाल करना.
उदाहरण के लिए, कम से कम लागत के फ़्लो से जुड़ी समस्या के तौर पर असाइनमेंट देखें.
नेटवर्क फ़्लो के तौर पर सेट अप की जा सकने वाली समस्या के लिए, कम से कम लागत वाले फ़्लो सॉल्वर को, एमआईपी या सीपी-एसएटी सॉल्वर के मुकाबले तेज़ी से इस्तेमाल किया जा सकता है. हालांकि, सभी MIPs को इस तरह सेट अप नहीं किया जा सकता.