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

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

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

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

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

इतिहास

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

गोमोरी का कट

पूर्णांक प्रोग्रामिंग समस्या को प्रस्तुत किया जाना चाहिए । इस प्रकार है,

${\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}$

जहां x_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 =* सॉफ्टवेयर

}}