शाखा और मूल्य: Difference between revisions
From Vigyanwiki
(Created page with "अनुप्रयुक्त गणित में, शाखा और मूल्य कई चरों के साथ पूर्णांक रैखिक...") |
No edit summary |
||
| Line 1: | Line 1: | ||
अनुप्रयुक्त गणित में | अनुप्रयुक्त गणित में '''शाखा और मूल्य''' कई चरों (वैरियेबल्स) के साथ [[पूर्णांक रैखिक प्रोग्रामिंग]] (ILP) और [[मिश्रित पूर्णांक रैखिक प्रोग्रामिंग]] (MILP) समस्याओं को हल करने के लिए संयोजी अनुकूलन का तरीका है। विधि शाखा और बाध्य और स्तंभ निर्माण विधियों का संकर है। | ||
== एल्गोरिथम का विवरण == | == एल्गोरिथम का विवरण == | ||
ब्रांच और प्राइस | ब्रांच और प्राइस ब्रांच और बाउंड मेथड है जिसमें सर्च ट्री के प्रत्येक नोड पर [[ रैखिक प्रोग्रामिंग छूट |रैखिक प्रोग्रामिंग छूट]] (LP रिलैक्सेशन) में कॉलम जोड़े जा सकते हैं। एल्गोरिथ्म की शुरुआत में, कम्प्यूटेशनल और मेमोरी आवश्यकताओं को कम करने के लिए कॉलम के सेट को एलपी छूट से बाहर रखा गया है और फिर कॉलम को एलपी छूट में आवश्यकतानुसार जोड़ा जाता है। दृष्टिकोण इस अवलोकन पर आधारित है कि बड़ी समस्याओं के लिए अधिकांश कॉलम गैर-मूल होंगे और किसी भी इष्टतम समाधान में उनके संबंधित चर शून्य के बराबर होंगे। इस प्रकार, बड़ी संख्या में कॉलम समस्या को हल करने के लिए अप्रासंगिक हैं। | ||
[[File:branch and price diagram.png|400px|thumb|शाखा और मूल्य एल्गोरिदम की रूपरेखा। से अनुकूलित <ref name=lectureSlides />]]एल्गोरिथम आमतौर पर | [[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>{{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> | ||
| Line 12: | Line 12: | ||
विभिन्न प्रकार के अनुप्रयोग क्षेत्रों में समस्याओं को हल करने के लिए शाखा और मूल्य पद्धति का उपयोग किया जा सकता है, जिनमें निम्न शामिल हैं: | विभिन्न प्रकार के अनुप्रयोग क्षेत्रों में समस्याओं को हल करने के लिए शाखा और मूल्य पद्धति का उपयोग किया जा सकता है, जिनमें निम्न शामिल हैं: | ||
* ग्राफ़ बहु रंग।<ref name=multicoloring /> | * ग्राफ़ बहु रंग।<ref name=multicoloring /> यह [[ग्राफ रंग]] की समस्या का सामान्यीकरण है जिसमें ग्राफ़ में प्रत्येक नोड को रंगों की पूर्व निर्धारित संख्या निर्दिष्ट की जानी चाहिए और किनारे साझा करने वाले किसी भी नोड में आम रंग नहीं हो सकता है। उद्देश्य तब वैध रंग के लिए आवश्यक रंगों की न्यूनतम संख्या का पता लगाना है। मल्टी-कलरिंग समस्या का उपयोग जॉब शेड्यूलिंग और टेलीकम्युनिकेशन चैनल असाइनमेंट सहित विभिन्न प्रकार के अनुप्रयोगों को मॉडल करने के लिए किया जा सकता है। | ||
* वाहन रूटिंग समस्या।<ref name=tutorial /> | * वाहन रूटिंग समस्या।<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> | ||
| Line 23: | Line 23: | ||
== बाहरी संदर्भ == | == बाहरी संदर्भ == | ||
*[https://web.archive.org/web/20100821132913/http://www.acsu.buffalo.edu/~nagi/courses/684/price.pdf शाखा और मूल्य पर व्याख्यान स्लाइड] | *[https://web.archive.org/web/20100821132913/http://www.acsu.buffalo.edu/~nagi/courses/684/price.pdf शाखा और मूल्य पर व्याख्यान स्लाइड] | ||
*[https://wiki.bordeaux.inria.fr/realopt/pmwiki.php/Project/BaPCod प्रोटोटाइप कोड | *[https://wiki.bordeaux.inria.fr/realopt/pmwiki.php/Project/BaPCod प्रोटोटाइप कोड सामान्य शाखा और मूल्य एल्गोरिथ्म के लिए] | ||
*[http://branchandcut.org/faq.htm BranchAndCut.org अक्सर पूछे जाने वाले प्रश्न] | *[http://branchandcut.org/faq.htm BranchAndCut.org अक्सर पूछे जाने वाले प्रश्न] | ||
*[http://scip.zib.de SCIP] ब्रांच-कट-एंड-प्राइस के लिए | *[http://scip.zib.de SCIP] ब्रांच-कट-एंड-प्राइस के लिए ओपन सोर्स फ्रेमवर्क और मिश्रित पूर्णांक प्रोग्रामिंग सॉल्वर | ||
*[https://web.archive.org/web/20171002101301/http://www.informatik.uni-koeln.de/abacus/ ABACUS - | *[https://web.archive.org/web/20171002101301/http://www.informatik.uni-koeln.de/abacus/ ABACUS - ब्रांच-एंड-क्यूट सिस्टम] - ओपन सोर्स सॉफ्टवेयर | ||
==संदर्भ== | ==संदर्भ== | ||
Revision as of 22:00, 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 =* सॉफ्टवेयर
}}
