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

कटिंग प्लेन के साथ यूनिट क्यूब का चौराहा $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 =* सॉफ्टवेयर

}}