शाखा और कर्तन

शाखा और कर्तन पूर्णांक रेखीय कार्यक्रमों (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^{*}$ वापस करना

स्यूडोकोड

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

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

ILP_solution Branch_and_cut_ILP(IntegerLinearProgram initial_problem) {

// ILP branch and cut solution pseudocode, assuming objective is to be maximized
ILP_solution branch_and_cut_ILP(IntegerLinearProgram initial_problem) {
    queue active_list; // L, above
    active_list.enqueue(initial_problem); // step 1
    // step 2
    ILP_solution optimal_solution; // this will hold x* above
    double best_objective = -std::numeric_limits<double>::infinity; // will hold v* above
    while (!active_list.empty()) { // step 3 above
        LinearProgram& curr_prob = active_list.dequeue(); // step 3.1
        do { // steps 3.2-3.7
            RelaxedLinearProgram& relaxed_prob = LP_relax(curr_prob); // step 3.2
            LP_solution curr_relaxed_soln = LP_solve(relaxed_prob); // this is x above
            bool cutting_planes_found = false;
            if (!curr_relaxed_soln.is_feasible()) { // step 3.3
                continue; // try another solution; continues at step 3
            }
            double current_objective_value = curr_relaxed_soln.value(); // v above
            if (current_objective_value <= best_objective) { // step 3.4
                continue; // try another solution; continues at step 3
            }
            if (curr_relaxed_soln.is_integer()) { // step 3.5
                best_objective = current_objective_value;
                optimal_solution = cast_as_ILP_solution(curr_relaxed_soln);
                continue; // continues at step 3
            }
            // current relaxed solution isn't integral
            if (hunting_for_cutting_planes) { // step 3.6
                violated_cutting_planes = search_for_violated_cutting_planes(curr_relaxed_soln);
                if (!violated_cutting_planes.empty()) { // step 3.6
                    cutting_planes_found = true; // will continue at step 3.2
                    for (auto&& cutting_plane : violated_cutting_planes) {
                        active_list.enqueue(LP_relax(curr_prob, cutting_plane));
                    }
                    continue; // continues at step 3.2
                }
            }
            // step 3.7: either violated cutting planes not found, or we weren't looking for them
            auto&& branched_problems = branch_partition(curr_prob);
            for (auto&& branch : branched_problems) {
                active_list.enqueue(branch);
            }
            continue; // continues at step 3
        } while (hunting_for_cutting_planes /* parameter of the algorithm; see 3.6 */
               && cutting_planes_found);
        // end step 3.2 do-while loop
    } // end step 3 while loop
    return optimal_solution; // step 4
}

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

प्रशाखी रणनीतियाँ

प्रशाखी और कर्तन कलन विधि में एक महत्वपूर्ण कदम प्रशाखी कदम है। इस चरण में, विभिन्न प्रकार के प्रशाखी स्वतः शोध प्रणाली हैं जिनका उपयोग किया जा सकता है। नीचे वर्णित प्रशाखी रणनीतियों में परिवर्तनशील पर प्रशाखी कहा जाता है। एक चर पर प्रशाखी में भिन्नात्मक मान $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 =* सॉफ्टवेयर

}}