शाखा और कर्तन

शाखा और कट पूर्णांक रेखीय कार्यक्रमों (ILPs) को हल करने के लिए मिश्रित अनुकूलन की एक विधि है, अर्थात्, रैखिक प्रोग्रामिंग (LP) समस्याएँ जहाँ कुछ या सभी अज्ञात पूर्णांक मानों तक सीमित हैं। ब्रांच और कट में एक शाखा और बंधन एल्गोरिथम चलाना और रैखिक प्रोग्रामिंग रिलैक्सेशन को कसने के लिए काटने का विमान का उपयोग करना शामिल है। ध्यान दें कि यदि कटौती केवल प्रारंभिक एलपी छूट को कसने के लिए उपयोग की जाती है, तो एल्गोरिदम को कट और शाखा कहा जाता है।

एल्गोरिथम

यह विवरण मानता है कि आईएलपी एक अधिकतमकरण समस्या है।

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

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

एल्गोरिथ्म का सारांश नीचे दिया गया है।

1. प्रारंभिक ILP को इसमें जोड़ें $L$, सक्रिय समस्याओं की सूची
2. तय करना $x^{*}={\text{null}}$ और $v^{*}=-\infty$
3. घुमाव के दौरान $L$ खाली नहीं है
   1. किसी समस्या को चुनें और हटाएं (डी-क्यू)। $L$
   2. समस्या की एलपी छूट को हल करें।
   3. यदि समाधान संभव नहीं है, तो 3 (जबकि) पर वापस जाएं। अन्यथा समाधान को निरूपित करें $x$ उद्देश्य मूल्य के साथ $v$.
   4. अगर $v\leq v^{*}$, 3 पर वापस जाएँ।
   5. अगर $x$ पूर्णांक है, सेट $v^{*}\leftarrow v,x^{*}\leftarrow x$ और 3 पर वापस जाएँ।
   6. यदि वांछित हो, तो उल्लंघन करने वाले विमानों को काटने की तलाश करें $x$. यदि कोई पाया जाता है, तो उन्हें एलपी छूट में जोड़ें और 3.2 पर लौटें।
   7. शाखा समस्या को सीमित व्यवहार्य क्षेत्रों के साथ नई समस्याओं में विभाजित करने के लिए। इन समस्याओं को जोड़ें $L$ और 3 पर वापस जाएँ
4. वापस करना $x^{*}$

{{Anchor|Code}स्यूडोकोड

सी ++ में - स्यूडोकोड की तरह, यह लिखा जा सकता है:

<वाक्यविन्यास प्रकाश लैंग = सी ++ लाइन = 1> // ILP शाखा और कट समाधान स्यूडोकोड, यह मानते हुए कि उद्देश्य को अधिकतम किया जाना है ILP_solution Branch_and_cut_ILP(IntegerLinearProgram initial_problem) {

   कतार सक्रिय_सूची; // एल, ऊपर
   active_list.enqueue (प्रारंभिक_समस्या); // स्टेप 1
   // चरण दो
   आईएलपी_समाधान इष्टतम_समाधान; // यह x* को ऊपर रखेगा
   डबल best_objective = -std::numeric_limits<double>::infinity; // ऊपर v* को होल्ड करेगा
   जबकि (!active_list.empty()) { // चरण 3 ऊपर
       लीनियरप्रोग्राम और curr_prob = active_list.dequeue (); // चरण 3.1
       करना { // चरण 3.2-3.7
           रिलैक्स्ड लीनियर प्रोग्राम और रिलैक्स_प्रोब = एलपी_रिलैक्स (कर_प्रोब); // चरण 3.2
           LP_solution curr_relaxed_soln = LP_solve(relaxed_prob); // यह x ऊपर है
           बूल कटिंग_प्लेन_फाउंड = झूठा;
           अगर (!curr_relaxed_soln.is_feasible()) { // चरण 3.3
               जारी रखना; // अन्य समाधान का प्रयास करें; चरण 3 पर जारी है
           }
           डबल current_objective_value = curr_relaxed_soln.value (); // वी ऊपर
           अगर (current_objective_value <= best_objective) { // चरण 3.4
               जारी रखना; // अन्य समाधान का प्रयास करें; चरण 3 पर जारी है
           }
           अगर (curr_relaxed_soln.is_integer ()) {// चरण 3.5
               best_objective = current_objective_value;
               इष्टतम समाधान = Cast_as_ILP_solution (curr_relaxed_soln);
               जारी रखना; // चरण 3 पर जारी है
           }
           // वर्तमान आराम समाधान अभिन्न नहीं है
           अगर (हंटिंग_फॉर_कटिंग_प्लेन) {// चरण 3.6
               उल्लंघन_कटिंग_प्लेन = search_for_violated_cutting_planes (curr_relaxed_soln);
               अगर (उल्लंघन_कटिंग_प्लेन.खाली ()) {// चरण 3.6
                   कटिंग_प्लेन_फाउंड = सच; // चरण 3.2 पर जारी रहेगा
                   के लिए (ऑटो&& कटिंग_प्लेन: उल्लंघन_कटिंग_प्लेन) {
                       active_list.enqueue (LP_relax (curr_prob, कटिंग_प्लेन));
                   }
                   जारी रखना; // चरण 3.2 पर जारी है
               }
           }
           // चरण 3.7: या तो उल्लंघन करने वाले विमान नहीं मिले, या हम उनकी तलाश नहीं कर रहे थे
           ऑटो&& ब्रांच्ड_प्रोब्लेम्स = ब्रांच_पार्टिशन (कर_प्रोब);
           के लिए (ऑटो और शाखा: शाखा_समस्याएं) {
               active_list.enqueue (शाखा);
           }
           जारी रखना; // चरण 3 पर जारी है
       } जबकि (hunting_for_cutting_planes /* एल्गोरिथम का पैरामीटर; 3.6 देखें */
              && कटिंग_प्लेन_फाउंड);
       // एंड स्टेप 3.2 डू-वाइल लूप
   } // लूप के दौरान चरण 3 समाप्त करें
   वापसी इष्टतम_समाधान; // चरण 4

} </वाक्यविन्यास हाइलाइट>

उपरोक्त स्यूडोकोड में, functions LP_relax, LP_solve और branch_partition समस्या के लिए उपयुक्त के रूप में सबरूटीन्स के रूप में बुलाया जाना चाहिए। उदाहरण के लिए, LP_solve संशोधित सिंप्लेक्स एल्गोरिथ्म कह सकते हैं। के लिए शाखाओं में बंटी रणनीतियाँ branch_partition नीचे चर्चा की गई है।

ब्रांचिंग रणनीतियाँ

ब्रांचिंग और कट एल्गोरिथम में एक महत्वपूर्ण कदम ब्रांचिंग स्टेप है। इस चरण में, विभिन्न प्रकार के ब्रांचिंग ह्यूरिस्टिक्स हैं जिनका उपयोग किया जा सकता है। नीचे वर्णित ब्रांचिंग रणनीतियों में वेरिएबल पर ब्रांचिंग कहा जाता है। एक चर पर ब्रांचिंग में एक चर चुनना शामिल है, $x_{i}$, भिन्नात्मक मान के साथ, $x_{i}'$, वर्तमान एलपी छूट के इष्टतम समाधान में और फिर बाधाओं को जोड़ना $x_{i}\leq \left\lfloor x_{i}'\right\rfloor$ और $x_{i}\geq \left\lceil x_{i}'\right\rceil$

सबसे अव्यवहारिक ब्रांचिंग

यह ब्रांचिंग स्ट्रैटेजी वेरिएबल को फ्रैक्शनल पार्ट के साथ 0.5 के करीब चुनती है।

छद्म लागत शाखाकरण

इस रणनीति का मूल विचार प्रत्येक चर के लिए ट्रैक रखना है $x_{i}$ उद्देश्य समारोह में परिवर्तन जब इस चर को पहले शाखा के लिए चर के रूप में चुना गया था। रणनीति तब उस चर को चुनती है जिसकी भविष्यवाणी की जाती है कि पिछले परिवर्तनों के आधार पर वस्तुनिष्ठ कार्य पर सबसे अधिक परिवर्तन होता है जब इसे शाखा चर के रूप में चुना गया था। ध्यान दें कि स्यूडो कॉस्ट ब्रांचिंग शुरू में खोज में अनौपचारिक है क्योंकि कुछ वेरिएबल्स को ब्रांच किया गया है।

मजबूत ब्रांचिंग

स्ट्रॉन्ग ब्रांचिंग में टेस्टिंग शामिल है कि कौन सा उम्मीदवार चर वास्तव में उन पर ब्रांचिंग करने से पहले ऑब्जेक्टिव फंक्शन में सबसे अच्छा सुधार देता है। पूर्ण मजबूत शाखाकरण सभी उम्मीदवार चर का परीक्षण करता है और कम्प्यूटेशनल रूप से महंगा हो सकता है। कम्प्यूटेशनल लागत को केवल उम्मीदवार चर के सबसेट पर विचार करके और संबंधित एलपी छूटों में से प्रत्येक को पूरा करने के लिए हल नहीं करके कम किया जा सकता है।

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

बाहरी संबंध

• Mixed Integer Programming
• SCIP: framework for branch-cut-and-price and a mixed integer programming solver
• ABACUS – A Branch-And-CUt System – open source software
• COIN-OR Cbc – open source software on GitHub

| group5 = Metaheuristics | abbr5 = heuristic | list5 =

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

| below =

• Software

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

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

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

}}