शाखा और मूल्य: Difference between revisions
From Vigyanwiki
No edit summary |
No edit summary |
||
| Line 1: | Line 1: | ||
अनुप्रयुक्त गणित में '''शाखा और मूल्य''' कई चरों (वैरियेबल्स) के साथ [[पूर्णांक रैखिक प्रोग्रामिंग]] (ILP) और [[मिश्रित पूर्णांक रैखिक प्रोग्रामिंग]] (MILP) समस्याओं को हल करने के लिए संयोजी अनुकूलन | अनुप्रयुक्त गणित में '''शाखा और मूल्य''' कई चरों (वैरियेबल्स) के साथ [[पूर्णांक रैखिक प्रोग्रामिंग]] (ILP) और [[मिश्रित पूर्णांक रैखिक प्रोग्रामिंग]] (MILP) समस्याओं को हल करने के लिए संयोजी अनुकूलन की विधि है। यह विधि मुख्यतः शाखा, बाध्य और कॉलम्स के निर्माण विधियों का संकरण है। | ||
== एल्गोरिथम का विवरण == | == एल्गोरिथम का विवरण == | ||
ब्रांच | ब्रांच, प्राइस ब्रांच और बाउंड ऐसा मेथड है जिसमें सर्च ट्री के प्रत्येक नोड पर [[ रैखिक प्रोग्रामिंग छूट |रैखिक प्रोग्रामिंग छूट]] (LP रिलैक्सेशन) में कॉलम जोड़े जा सकते हैं। इस प्रकार किसी एल्गोरिथ्म के प्रारंभ में कम्प्यूटेरीकृत और मेमोरी की आवश्यकताओं को कम करने के लिए कॉलम के सेट को एलपी छूट से पृथक कर देते हैं और फिर कॉलम को एलपी छूट में आवश्यकतानुसार जोड़ा जाता है। यह दृष्टिकोण इस अवलोकन पर आधारित है कि बड़ी समस्याओं के लिए अधिकांश कॉलम मौलिक नहीं होंगे और किसी भी इष्टतम समाधान में उनके संबंधित वैरियेबल का मान शून्य के बराबर उपयोग करेंगे। इस प्रकार बड़ी संख्याओं में कॉलम समस्या को हल करने के लिए अप्रासंगिक रूप से इसका उपयोग किया जाता हैं। | ||
[[File:branch and price diagram.png|400px|thumb|शाखा और मूल्य एल्गोरिदम की रूपरेखा से अनुकूलित <ref name=lectureSlides />]]एल्गोरिथम सामान्यतः इसे सही करने के लिए उपयोग करने के आशय से प्रारंभ की गई है, जैसे कि डेंटज़िग-वोल्फ अपघटन, जिसे मास्टर समस्याओं के रूप में जाना जाता है। इस प्रकार अपघटन समस्या सूत्रीकरण प्राप्त करने के लिए किया जाता है जो मूल सूत्रीकरण की छूट की तुलना में छूट के हल होने पर उत्तम सीमा देता है। अपितु इस अपघटन में सामान्यतः कई चर होते हैं और इसलिए संशोधित संस्करण, जिसे प्रतिबंधित मास्टर समस्या कहा जाता है, उन्हें केवल काॅलम्स के सबसेट पर विचार करने के लिए उपयोग किया जाता है।<ref name=tutorial>{{cite journal|last=Feillet|first=Dominique|title=वाहन रूटिंग समस्याओं के लिए कॉलम जनरेशन और ब्रांच-एंड-प्राइस पर एक ट्यूटोरियल|journal=4OR|year=2010|volume=8|issue=4|pages=407–424|doi=10.1007/s10288-010-0130-z}}</ref> इसके पश्चात इष्टतमत प्रारूप की जांच करने के लिए मूल्य निर्धारण समस्या नामक उप-समस्या को कॉलम सर्चिंग के रूप में उपयोग करने के लिए हल किया जाता है जो इसके आधार में प्रवेश कर सकता है और जिसका उद्देश्य फ़ंक्शन को न्यूनतम समस्या के लिए कम कर सकता है। इसमें ऋणात्मक रूप से [[कम लागत]] वाले कॉलम को सर्च करना सम्मिलित है। यहाँ पर ध्यान दें कि मूल्य निर्धारण की समस्या को हल करना कठिन हो सकता है, अपितु सबसे ऋणात्मक कम लागत वाले कॉलम को सर्च करना आवश्यक नहीं है, इसलिए इसके अनुमानी और स्थानीय सर्च विधियों का उपयोग किया जा सकता है।<ref name=multicoloring>{{cite book|last=Mehrota|first=Anuj|author2=M.A. Trick|author2-link=Michael Trick|title=ग्राफ़ बहु-रंग के लिए एक शाखा-और-मूल्य दृष्टिकोण|journal=Extending the Horizons: Advances in Computing, Optimization, and Decision Technologies|volume=37|year=2007|pages=[https://archive.org/details/extendinghorizon0000info/page/15 15–29]|doi=10.1007/978-0-387-48793-9_2|citeseerx=10.1.1.163.6870|series=Operations Research/Computer Science Interfaces Series|isbn=978-0-387-48790-8|url=https://archive.org/details/extendinghorizon0000info/page/15}}</ref> इस उप-समस्या को केवल पूरा करने के लिए हल किया जाना चाहिए जिससे कि यह प्रमाणित हो सके कि प्रतिबंधित मास्टर समस्या का इष्टतम समाधान भी मास्टर समस्या का इष्टतम समाधान है। इस प्रकार प्रत्येक क्रम में ऋणात्मक कम लागत वाले कॉलम को उपयोग किया जाता हैं, इसे प्रतिबंधित मास्टर समस्या में जोड़ा जाता है और छूट को फिर से अनुकूलित किया जाता है। यदि कोई कॉलम आधार में प्रवेश नहीं कर सकता है और छूट का समाधान पूर्णांक नहीं है, तो ब्रांचिंग सफलता पूर्वक होती है।<ref name=lectureSlides>{{cite web|last=Akella|first=M.|author2=S. Gupta|author3=A. Sarkar|title=Branch and Price: Column Generation for Solving Huge Integer Programs|url=http://www.acsu.buffalo.edu/~nagi/courses/684/price.pdf|access-date=2012-12-19|archive-url=https://web.archive.org/web/20100821132913/http://www.acsu.buffalo.edu/~nagi/courses/684/price.pdf|archive-date=2010-08-21|url-status=dead}}</ref> | |||
इस प्रकार अधिकांशतः शाखा और मूल्य एल्गोरिदम समस्या विशिष्ट हैं क्योंकि समस्या को इस प्रकार से तैयार किया जाना चाहिए जिससे कि प्रभावी शाखाओं के नियम तैयार किए जा सकें और मूल्य निर्धारण की समस्या को हल करना अपेक्षाकृत सरल होता हैं।<ref>{{cite web|last=Gamrath|first=G.|title=सामान्य शाखा-कट-एंड-प्राइस|url=http://www.zib.de/gamrath/publications/gamrath2010_genericBCP.pdf}}</ref> यदि उपयोग ना किए जाने वाले इस समतल का उपयोग शाखा और मूल्य एल्गोरिदम के भीतर एलपी छूट को उपयोग करने के लिए किया जाता है, तो विधि को शाखा मूल्य और इसमें की जाने वाली कटौती के रूप में जाना जाता है।<ref name=branchPriceAndCut>{{cite journal|last=Desrosiers|first=J.|author2=M.E. Lubbecke|title=शाखा-मूल्य-और-कट एल्गोरिदम|journal=Wiley Encyclopedia of Operations Research and Management Science|year=2010}}</ref> | |||
== शाखा और मूल्य के अनुप्रयोग == | == शाखा और मूल्य के अनुप्रयोग == | ||
विभिन्न प्रकार के अनुप्रयोग क्षेत्रों में समस्याओं को हल करने के लिए शाखा और मूल्य पद्धति का उपयोग किया जा सकता है, जिनमें निम्न | विभिन्न प्रकार के अनुप्रयोग क्षेत्रों में समस्याओं को हल करने के लिए शाखा और मूल्य पद्धति का उपयोग किया जा सकता है, जिनमें निम्न बिंदुओं को सम्मिलित किया गया हैं: | ||
* ग्राफ़ | * मल्टी कलरिंग ग्राफ़-<ref name=multicoloring /> यह [[ग्राफ रंग|ग्राफ रंगों]] की समस्या का सामान्यीकरण करने में उपयोगी है, जिसमें ग्राफ़ में प्रत्येक नोड को विभिन्न रंगों की पूर्व निर्धारित संख्या निर्दिष्ट की जानी चाहिए और किनारे साझा करने वाले किसी भी नोड में सरल रंग नहीं हो सकता है। इसका उद्देश्य उस समय वैध रंगों के लिए आवश्यक रंगों की न्यूनतम संख्या का पता लगाने के लिए किया जाता है। मल्टी-कलरिंग समस्या का उपयोग जॉब शेड्यूलिंग और टेलीकम्युनिकेशन चैनल असाइनमेंट सहित विभिन्न प्रकार के अनुप्रयोगों को प्रारूपित करने के लिए किया जाता है। | ||
* वाहन रूटिंग | * वाहन रूटिंग समस्या<ref name=tutorial /> | ||
*[[सामान्यीकृत असाइनमेंट समस्या]]<ref>{{cite journal|last=Savelsbergh|first=M.|title=सामान्यीकृत असाइनमेंट समस्या के लिए एक शाखा और मूल्य एल्गोरिथम|journal=Operations Research|volume=45|issue=6|pages=831–841|year=1997|series=831-841|doi=10.1287/opre.45.6.831 }}</ref> | |||
== यह भी देखें == | == यह भी देखें == | ||
* [[शाखा और कट]] | * [[शाखा और कट]] | ||
*शाखा और बंधन | *शाखा और बंधन | ||
* [[विलंबित स्तंभ निर्माण]] | * [[विलंबित स्तंभ निर्माण|विलंबित स्तंभ या काॅलम का निर्माण]] | ||
== बाहरी संदर्भ == | == बाहरी संदर्भ == | ||
Revision as of 22:14, 15 May 2023
अनुप्रयुक्त गणित में शाखा और मूल्य कई चरों (वैरियेबल्स) के साथ पूर्णांक रैखिक प्रोग्रामिंग (ILP) और मिश्रित पूर्णांक रैखिक प्रोग्रामिंग (MILP) समस्याओं को हल करने के लिए संयोजी अनुकूलन की विधि है। यह विधि मुख्यतः शाखा, बाध्य और कॉलम्स के निर्माण विधियों का संकरण है।
एल्गोरिथम का विवरण
ब्रांच, प्राइस ब्रांच और बाउंड ऐसा मेथड है जिसमें सर्च ट्री के प्रत्येक नोड पर रैखिक प्रोग्रामिंग छूट (LP रिलैक्सेशन) में कॉलम जोड़े जा सकते हैं। इस प्रकार किसी एल्गोरिथ्म के प्रारंभ में कम्प्यूटेरीकृत और मेमोरी की आवश्यकताओं को कम करने के लिए कॉलम के सेट को एलपी छूट से पृथक कर देते हैं और फिर कॉलम को एलपी छूट में आवश्यकतानुसार जोड़ा जाता है। यह दृष्टिकोण इस अवलोकन पर आधारित है कि बड़ी समस्याओं के लिए अधिकांश कॉलम मौलिक नहीं होंगे और किसी भी इष्टतम समाधान में उनके संबंधित वैरियेबल का मान शून्य के बराबर उपयोग करेंगे। इस प्रकार बड़ी संख्याओं में कॉलम समस्या को हल करने के लिए अप्रासंगिक रूप से इसका उपयोग किया जाता हैं।
शाखा और मूल्य एल्गोरिदम की रूपरेखा से अनुकूलित [1]
एल्गोरिथम सामान्यतः इसे सही करने के लिए उपयोग करने के आशय से प्रारंभ की गई है, जैसे कि डेंटज़िग-वोल्फ अपघटन, जिसे मास्टर समस्याओं के रूप में जाना जाता है। इस प्रकार अपघटन समस्या सूत्रीकरण प्राप्त करने के लिए किया जाता है जो मूल सूत्रीकरण की छूट की तुलना में छूट के हल होने पर उत्तम सीमा देता है। अपितु इस अपघटन में सामान्यतः कई चर होते हैं और इसलिए संशोधित संस्करण, जिसे प्रतिबंधित मास्टर समस्या कहा जाता है, उन्हें केवल काॅलम्स के सबसेट पर विचार करने के लिए उपयोग किया जाता है।[2] इसके पश्चात इष्टतमत प्रारूप की जांच करने के लिए मूल्य निर्धारण समस्या नामक उप-समस्या को कॉलम सर्चिंग के रूप में उपयोग करने के लिए हल किया जाता है जो इसके आधार में प्रवेश कर सकता है और जिसका उद्देश्य फ़ंक्शन को न्यूनतम समस्या के लिए कम कर सकता है। इसमें ऋणात्मक रूप से कम लागत वाले कॉलम को सर्च करना सम्मिलित है। यहाँ पर ध्यान दें कि मूल्य निर्धारण की समस्या को हल करना कठिन हो सकता है, अपितु सबसे ऋणात्मक कम लागत वाले कॉलम को सर्च करना आवश्यक नहीं है, इसलिए इसके अनुमानी और स्थानीय सर्च विधियों का उपयोग किया जा सकता है।[3] इस उप-समस्या को केवल पूरा करने के लिए हल किया जाना चाहिए जिससे कि यह प्रमाणित हो सके कि प्रतिबंधित मास्टर समस्या का इष्टतम समाधान भी मास्टर समस्या का इष्टतम समाधान है। इस प्रकार प्रत्येक क्रम में ऋणात्मक कम लागत वाले कॉलम को उपयोग किया जाता हैं, इसे प्रतिबंधित मास्टर समस्या में जोड़ा जाता है और छूट को फिर से अनुकूलित किया जाता है। यदि कोई कॉलम आधार में प्रवेश नहीं कर सकता है और छूट का समाधान पूर्णांक नहीं है, तो ब्रांचिंग सफलता पूर्वक होती है।[1]
इस प्रकार अधिकांशतः शाखा और मूल्य एल्गोरिदम समस्या विशिष्ट हैं क्योंकि समस्या को इस प्रकार से तैयार किया जाना चाहिए जिससे कि प्रभावी शाखाओं के नियम तैयार किए जा सकें और मूल्य निर्धारण की समस्या को हल करना अपेक्षाकृत सरल होता हैं।[4] यदि उपयोग ना किए जाने वाले इस समतल का उपयोग शाखा और मूल्य एल्गोरिदम के भीतर एलपी छूट को उपयोग करने के लिए किया जाता है, तो विधि को शाखा मूल्य और इसमें की जाने वाली कटौती के रूप में जाना जाता है।[5]
शाखा और मूल्य के अनुप्रयोग
विभिन्न प्रकार के अनुप्रयोग क्षेत्रों में समस्याओं को हल करने के लिए शाखा और मूल्य पद्धति का उपयोग किया जा सकता है, जिनमें निम्न बिंदुओं को सम्मिलित किया गया हैं:
- मल्टी कलरिंग ग्राफ़-[3] यह ग्राफ रंगों की समस्या का सामान्यीकरण करने में उपयोगी है, जिसमें ग्राफ़ में प्रत्येक नोड को विभिन्न रंगों की पूर्व निर्धारित संख्या निर्दिष्ट की जानी चाहिए और किनारे साझा करने वाले किसी भी नोड में सरल रंग नहीं हो सकता है। इसका उद्देश्य उस समय वैध रंगों के लिए आवश्यक रंगों की न्यूनतम संख्या का पता लगाने के लिए किया जाता है। मल्टी-कलरिंग समस्या का उपयोग जॉब शेड्यूलिंग और टेलीकम्युनिकेशन चैनल असाइनमेंट सहित विभिन्न प्रकार के अनुप्रयोगों को प्रारूपित करने के लिए किया जाता है।
- वाहन रूटिंग समस्या[2]
- सामान्यीकृत असाइनमेंट समस्या[6]
यह भी देखें
- शाखा और कट
- शाखा और बंधन
- विलंबित स्तंभ या काॅलम का निर्माण
बाहरी संदर्भ
- शाखा और मूल्य पर व्याख्यान स्लाइड
- प्रोटोटाइप कोड सामान्य शाखा और मूल्य एल्गोरिथ्म के लिए
- BranchAndCut.org अक्सर पूछे जाने वाले प्रश्न
- SCIP ब्रांच-कट-एंड-प्राइस के लिए ओपन सोर्स फ्रेमवर्क और मिश्रित पूर्णांक प्रोग्रामिंग सॉल्वर
- ABACUS - ब्रांच-एंड-क्यूट सिस्टम - ओपन सोर्स सॉफ्टवेयर
संदर्भ
- ↑ 1.0 1.1 Akella, M.; S. Gupta; A. Sarkar. "Branch and Price: Column Generation for Solving Huge Integer Programs" (PDF). Archived from the original (PDF) on 2010-08-21. Retrieved 2012-12-19.
- ↑ 2.0 2.1 Feillet, Dominique (2010). "वाहन रूटिंग समस्याओं के लिए कॉलम जनरेशन और ब्रांच-एंड-प्राइस पर एक ट्यूटोरियल". 4OR. 8 (4): 407–424. doi:10.1007/s10288-010-0130-z.
- ↑ 3.0 3.1 Mehrota, Anuj; M.A. Trick (2007). ग्राफ़ बहु-रंग के लिए एक शाखा-और-मूल्य दृष्टिकोण. pp. 15–29. CiteSeerX 10.1.1.163.6870. doi:10.1007/978-0-387-48793-9_2. ISBN 978-0-387-48790-8.
{{cite book}}:|journal=ignored (help) - ↑ Gamrath, G. "सामान्य शाखा-कट-एंड-प्राइस" (PDF).
- ↑ Desrosiers, J.; M.E. Lubbecke (2010). "शाखा-मूल्य-और-कट एल्गोरिदम". Wiley Encyclopedia of Operations Research and Management Science.
- ↑ Savelsbergh, M. (1997). "सामान्यीकृत असाइनमेंट समस्या के लिए एक शाखा और मूल्य एल्गोरिथम". Operations Research. 831-841. 45 (6): 831–841. doi:10.1287/opre.45.6.831.
- Barnhart, Cynthia; Johnson, Ellis L.; Nemhauser, George L.; Savelsbergh, Martin W. P.; Vance, Pamela H. (1998), "Branch-and-price: column generation for solving huge integer programs", Operations Research, 46 (3): 316–329, CiteSeerX 10.1.1.197.7390, doi:10.1287/opre.46.3.316, JSTOR 222825
|  | |||||||||||||||||
| ||||||||||||||||||
| ||||||||||||||||||
| group5 = Metaheuristics | abbr5 = heuristic | list5 =
| below =
}} | group5 =Metaheuuristic |abbr5 = heuristic | list5 =*विकासवादी एल्गोरिथ्म
| below =* सॉफ्टवेयर
}}
