कटिंग-प्लेन विधि

कटिंग प्लेन के साथ यूनिट क्यूब का चौराहा $x_{1}+x_{2}+x_{3}\geq 2$. तीन नोड्स पर ट्रैवलिंग सेल्समैन समस्या के संदर्भ में, यह (बल्कि कमजोर) असमानता बताती है कि हर दौरे में कम से कम दो किनारे होने चाहिए।

गणित अनुकूलन (गणित) में, कटिंग-प्लेन विधि विभिन्न प्रकार की अनुकूलन विधियों में से एक है, जो रैखिक असमानताओं के माध्यम से एक व्यवहार्य सेट या उद्देश्य फ़ंक्शन को पुनरावृत्त रूप से परिष्कृत करती है, जिसे 'कट' कहा जाता है। ऐसी प्रक्रियाओं का उपयोग आमतौर पर मिश्रित पूर्णांक रैखिक प्रोग्रामिंग (एमआईएलपी) समस्याओं के पूर्णांक समाधान खोजने के लिए किया जाता है, साथ ही साथ सामान्य रूप से अलग करने योग्य उत्तल अनुकूलन समस्याओं को हल करने के लिए भी किया जाता है। MILP को हल करने के लिए कटिंग प्लेन के उपयोग की शुरुआत राल्फ ई. गोमोरी ने की थी।

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

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

गोमरी का कट

पूर्णांक प्रोग्रामिंग और मिश्रित-पूर्णांक प्रोग्रामिंग समस्याओं को हल करने के लिए एक विधि के रूप में 1950 के दशक में राल्फ ई. गोमरी द्वारा कटिंग प्लेन प्रस्तावित किए गए थे। हालांकि, खुद गोमोरी सहित अधिकांश विशेषज्ञों ने संख्यात्मक अस्थिरता के साथ-साथ अप्रभावी होने के कारण उन्हें अव्यावहारिक माना, क्योंकि समाधान की दिशा में प्रगति करने के लिए कई दौर की कटौती की आवश्यकता थी। 1990 के दशक के मध्य में जब जेरार्ड कॉर्नुएजोल और सहकर्मियों ने उन्हें शाखा और बंधन | ब्रांच-एंड-बाउंड (शाखा और कट | ब्रांच-एंड-कट कहा जाता है) और संख्यात्मक पर काबू पाने के तरीकों के संयोजन में बहुत प्रभावी दिखाया। अस्थिरता। आजकल, सभी व्यावसायिक MILP सॉल्वर एक या दूसरे तरीके से गोमरी कट्स का उपयोग करते हैं। सिंप्लेक्स झांकी से गोमोरी कट बहुत कुशलता से उत्पन्न होते हैं, जबकि कई अन्य प्रकार के कट या तो महंगे होते हैं या अलग करने के लिए एनपी-मुश्किल होते हैं। एमआईएलपी के लिए अन्य सामान्य कटौती में, विशेष रूप से लिफ्ट-एंड-प्रोजेक्ट गोमरी कटौती पर हावी है। एक पूर्णांक प्रोग्रामिंग समस्या को तैयार किया जाना चाहिए (पूर्णांक प्रोग्रामिंग#कैनोनिकल और ILPs के लिए मानक रूप में) इस प्रकार है:

${\begin{aligned}{\text{Maximize }}&c^{T}x\\{\text{Subject to }}&Ax\leq b,\\&x\geq 0,\,x_{i}{\text{ all integers}}.\end{aligned}}$

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

एक रेखीय कार्यक्रम को हल करने के लिए सिम्प्लेक्स विधि का उपयोग करने से फॉर्म के समीकरणों का एक सेट तैयार होता है

$x_{i}+\sum {\bar {a}}_{i,j}x_{j}={\bar {b}}_{i}$

जहां एक्स_iएक बुनियादी है चर और x_jएस गैर बुनियादी चर हैं। इस समीकरण को फिर से लिखें ताकि पूर्णांक भाग बाईं ओर हों और आंशिक भाग दाईं ओर हों:

$x_{i}+\sum \lfloor {\bar {a}}_{i,j}\rfloor x_{j}-\lfloor {\bar {b}}_{i}\rfloor ={\bar {b}}_{i}-\lfloor {\bar {b}}_{i}\rfloor -\sum ({\bar {a}}_{i,j}-\lfloor {\bar {a}}_{i,j}\rfloor )x_{j}.$

सुसंगत क्षेत्र में किसी भी पूर्णांक बिंदु के लिए, इस समीकरण का दाहिना पक्ष 1 से कम है और बायां पक्ष एक पूर्णांक है, इसलिए सामान्य मान 0 से कम या उसके बराबर होना चाहिए। इसलिए असमानता

${\bar {b}}_{i}-\lfloor {\bar {b}}_{i}\rfloor -\sum ({\bar {a}}_{i,j}-\lfloor {\bar {a}}_{i,j}\rfloor )x_{j}\leq 0$

संभव क्षेत्र में किसी भी पूर्णांक बिंदु के लिए धारण करना चाहिए। इसके अलावा, गैर-मूल चर किसी भी मूल समाधान में 0s के बराबर हैं और यदि x_iमूल हल x के लिए पूर्णांक नहीं है,

${\bar {b}}_{i}-\lfloor {\bar {b}}_{i}\rfloor -\sum ({\bar {a}}_{i,j}-\lfloor {\bar {a}}_{i,j}\rfloor )x_{j}={\bar {b}}_{i}-\lfloor {\bar {b}}_{i}\rfloor >0.$

तो उपरोक्त असमानता मूल व्यवहार्य समाधान को बाहर करती है और इस प्रकार वांछित गुणों के साथ एक कटौती है। पेश है एक नया स्लैक वेरिएबल x_k इस असमानता के लिए, रैखिक कार्यक्रम में एक नई बाधा जोड़ी जाती है, अर्थात्

$x_{k}+\sum (\lfloor {\bar {a}}_{i,j}\rfloor -{\bar {a}}_{i,j})x_{j}=\lfloor {\bar {b}}_{i}\rfloor -{\bar {b}}_{i},\,x_{k}\geq 0,\,x_{k}{\mbox{ an integer}}.$

उत्तल अनुकूलन

गैर रेखीय प्रोग्रामिंग में कटिंग प्लेन के तरीके भी लागू होते हैं। अंतर्निहित सिद्धांत एक गैर-रैखिक (उत्तल) कार्यक्रम के व्यवहार्य क्षेत्र को बंद आधे स्थानों के एक परिमित सेट द्वारा अनुमानित करना और अनुमानित रैखिक कार्यक्रमों के अनुक्रम को हल करना है।

यह भी देखें

• बेंडर्स का अपघटन
• शाखा और कट
• शाखा और बंधन
• स्तंभ पीढ़ी
• डेंटजिग-वोल्फ अपघटन

संदर्भ

• Marchand, Hugues; Martin, Alexander; Weismantel, Robert; Wolsey, Laurence (2002). "Cutting planes in integer and mixed integer programming". Discrete Applied Mathematics. 123 (1–3): 387–446. doi:10.1016/s0166-218x(01)00348-1.
• Avriel, Mordecai (2003). Nonlinear Programming: Analysis and Methods. Dover Publications. ISBN 0-486-43227-0
• Cornuéjols, Gérard (2008). Valid Inequalities for Mixed Integer Linear Programs. Mathematical Programming Ser. B, (2008) 112:3–44. [1]
• Cornuéjols, Gérard (2007). Revival of the Gomory Cuts in the 1990s. Annals of Operations Research, Vol. 149 (2007), pp. 63–66. [2]

बाहरी संबंध

• "Integer Programming" Section 9.8 Applied Mathematical Programming Chapter 9 Integer Programming (full text). Bradley, Hax, and Magnanti (Addison-Wesley, 1977)

| group5 = Metaheuristics | abbr5 = heuristic | list5 =

• Evolutionary algorithm
• Hill climbing
• Local search
• Simulated annealing
• Tabu search

| below =

• Software

}} | group5 =Metaheuuristic |abbr5 = heuristic | list5 =*विकासवादी एल्गोरिथ्म

• पहाड़ी की चढ़ाई
• स्थानीय खोज
• तैयार किए हुयी धातु पे पानी चढाने की कला
• तब्बू खोज

| below =* सॉफ्टवेयर

}}