शाखा और मूल्य

अनुप्रयुक्त गणित में शाखा और मूल्य कई चरों (वैरियेबल्स) के साथ पूर्णांक रैखिक प्रोग्रामिंग (ILP) और मिश्रित पूर्णांक रैखिक प्रोग्रामिंग (MILP) समस्याओं को हल करने के लिए संयोजी अनुकूलन की विधि है। यह विधि मुख्यतः शाखा, बाध्य और कॉलम्स के निर्माण विधियों का संकरण है।

एल्गोरिथम का विवरण

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

शाखा और मूल्य एल्गोरिदम की रूपरेखा से अनुकूलित ^[1]

एल्गोरिथम सामान्यतः इसे सही करने के लिए उपयोग करने के आशय से प्रारंभ की गई है, जैसे कि डेंटज़िग-वोल्फ अपघटन, जिसे मास्टर समस्याओं के रूप में जाना जाता है। इस प्रकार अपघटन समस्या सूत्रीकरण प्राप्त करने के लिए किया जाता है जो मूल सूत्रीकरण की छूट की तुलना में छूट के हल होने पर उत्तम सीमा देता है। अपितु इस अपघटन में सामान्यतः कई चर होते हैं और इसलिए संशोधित संस्करण, जिसे प्रतिबंधित मास्टर समस्या कहा जाता है, उन्हें केवल काॅलम्स के सबसेट पर विचार करने के लिए उपयोग किया जाता है।^[2] इसके पश्चात इष्टतमत प्रारूप की जांच करने के लिए मूल्य निर्धारण समस्या नामक उप-समस्या को कॉलम सर्चिंग के रूप में उपयोग करने के लिए हल किया जाता है जो इसके आधार में प्रवेश कर सकता है और जिसका उद्देश्य फ़ंक्शन को न्यूनतम समस्या के लिए कम कर सकता है। इसमें ऋणात्मक रूप से कम लागत वाले कॉलम को सर्च करना सम्मिलित है। यहाँ पर ध्यान दें कि मूल्य निर्धारण की समस्या को हल करना कठिन हो सकता है, अपितु सबसे ऋणात्मक कम लागत वाले कॉलम को सर्च करना आवश्यक नहीं है, इसलिए इसके अनुमानी और स्थानीय सर्च विधियों का उपयोग किया जा सकता है।^[3] इस उप-समस्या को केवल पूरा करने के लिए हल किया जाना चाहिए जिससे कि यह प्रमाणित हो सके कि प्रतिबंधित मास्टर समस्या का इष्टतम समाधान भी मास्टर समस्या का इष्टतम समाधान है। इस प्रकार प्रत्येक क्रम में ऋणात्मक कम लागत वाले कॉलम को उपयोग किया जाता हैं, इसे प्रतिबंधित मास्टर समस्या में जोड़ा जाता है और छूट को फिर से अनुकूलित किया जाता है। यदि कोई कॉलम आधार में प्रवेश नहीं कर सकता है और छूट का समाधान पूर्णांक नहीं है, तो ब्रांचिंग सफलता पूर्वक होती है।^[1]

इस प्रकार अधिकांशतः शाखा और मूल्य एल्गोरिदम समस्या विशिष्ट हैं क्योंकि समस्या को इस प्रकार से तैयार किया जाना चाहिए जिससे कि प्रभावी शाखाओं के नियम तैयार किए जा सकें और मूल्य निर्धारण की समस्या को हल करना अपेक्षाकृत सरल होता हैं।^[4] यदि उपयोग ना किए जाने वाले इस समतल का उपयोग शाखा और मूल्य एल्गोरिदम के भीतर एलपी छूट को उपयोग करने के लिए किया जाता है, तो विधि को शाखा मूल्य और इसमें की जाने वाली कटौती के रूप में जाना जाता है।^[5]