शाखा और मूल्य

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

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

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

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

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

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