शाखा और बंधन

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

एल्गोरिथ्म खोज स्थान के क्षेत्रों/शाखाओं की निचली और ऊपरी सीमा के कुशल आकलन पर निर्भर करता है। यदि कोई सीमा उपलब्ध नहीं है, तो एल्गोरिथम संपूर्ण खोज के लिए पतित हो जाता है।

1960 में असतत अनुकूलन के लिए BP द्वारा प्रायोजित लंदन स्कूल ऑफ इकोनॉमिक्स में शोध करते समय पहली बार ऐल्सा प्रांत और एलीसन हारर्कोट द्वारा विधि प्रस्तावित की गई थी। इस प्रकार इस कारण एनपी कठिन अनुकूलन समस्याओं को हल करने के लिए सबसे अधिक उपयोग किया जाने वाला उपकरण बन गया है। इस प्रकार इस शाखा और बंधन के नाम में सबसे पहले लिटिल एट अल के कार्य में आया हैं। जिसकी यात्रा विक्रेता की समस्याओं पर निर्भर होती हैं।

अवलोकन

ब्रांचिंग और बाउंडिंग एल्गोरिथम का लक्ष्य x मान को खोजना है, जो वास्तविक मूल्यवान फ़ंक्शन f(x) के मान को अधिकतम या कम करता है, कुछ सेट के बीच S स्वीकार्य, या उपयोगकर्ता समाधान को ऑब्जेक्टिव फ़ंक्शन कहा जाता है। इस प्रकार सेट S को खोजे गए स्थान या व्यवहार्य क्षेत्र कहा जाता है। इस प्रकार इस खंड के बचे हुए भागों के रूप में माना जाता है कि कम से कम f(x) वांछित है, इस प्रकार यह धारणा व्यापकता के हानि के बिना आती है, क्योंकि कोई अधिकतम मूल्य f(x) का न्यूनतम ज्ञात करके g(x) = −f(x) पा सकता है, इस प्रकार बी एंड बी एल्गोरिदम दो सिद्धांतों के अनुसार कार्य करता है:

• यह पुनरावर्ती रूप से खोज स्थान को छोटे स्थानों में विभाजित करता है, फिर f(x) इन छोटे स्थानों पर छोटा करता है, इस प्रकार इसके विभाजन को ब्रांचिंग कहा जाता है।
• अकेले ब्रांचिंग क्रूर-बल खोज या ब्रूट-फोर्स एन्यूमरेशन ऑफ़ कैंडिडेट सॉल्यूशंस और उन सभी का परीक्षण करने की राशि के रूप में उपयोग होती हैं। इस प्रकार ब्रूट-फोर्स सर्च के प्रदर्शन में सुधार करने के लिए, B&B एल्गोरिद्म कम से कम सीमा का ट्रैक रखता है जिसे वह खोजने का प्रयास करता है, और इस प्रकार इन सीमाओं का उपयोग खोज स्थान का निर्णय ट्री के रूप में प्रदर्शित करने के लिए करता है, इस प्रकार उपयोगकर्ता समाधानों को समाप्त करता है जो यह साबित कर सकता है इष्टतम समाधान सम्मिलित नहीं रहता है।

विशिष्ट अनुकूलन समस्या के लिए इन सिद्धांतों को ठोस एल्गोरिदम में परिवर्तित करने के लिए कुछ प्रकार की डेटा संरचना की आवश्यकता होती है जो उपयोगकर्ता समाधान के सेट का प्रतिनिधित्व करती है। इस प्रकार के प्रतिनिधित्व को समस्या का उदाहरण कहा जाता है। इस प्रकार उदाहरण के लिए उपयोगकर्ता समाधान के सेट को I द्वारा S_I निरूपित करते हैं। इसके उदाहरण के लिए प्रतिनिधित्व को तीन परिचालनों के साथ प्रदर्शित कर सकते हैं:

• branch(I) - दो या दो से अधिक उदाहरण उत्पन्न करता है जिनमें से प्रत्येक सबसेट S_I का प्रतिनिधित्व करता है। (सामान्यतः उपसमुच्चय असम्बद्ध सेट होते हैं जो एल्गोरिदम को ही उपयोगकर्ता समाधान पर दो बार जाने से रोकते हैं, लेकिन इसकी आवश्यकता नहीं है। चूंकि इस प्रकार बीच में इष्टतम समाधान S_I कम से कम सबसेट में सम्मिलित होना चाहिए।)
• bound(I) द्वारा दर्शाए गए स्थान में किसी भी उपयोगकर्ता समाधान के मूल्य पर निचली सीमा I की गणना करता है, इस प्रकार इसका मान bound(I) ≤ f(x) सभी के लिए x में S_I. के समान हैं।
• solution(I) निर्धारित करता है कि क्या I एकल उपयोगकर्ता समाधान का प्रतिनिधित्व करता है। (इस प्रकार वैकल्पिक रूप से, यदि ऐसा नहीं होता है, तो S_I ऑपरेशन बीच में से कुछ व्यवहार्य समाधान वापस करने का विकल्प चुन सकता है.) यदि solution(I) तब फंक्शन f(solution(I)) लौटाता है, इस प्रकार इसके व्यवहार्य समाधानों के पूरे स्थान पर इष्टतम उद्देश्य मान के लिए ऊपरी सीमा प्रदान करता है।

इन परिचालनों का उपयोग करते हुए, बी एंड बी एल्गोरिदम शाखा संचालन द्वारा गठित उदाहरणों के ट्री सर्चिंग के माध्यम से शीर्ष-नीचे पुनरावर्ती खोज करता है। उदाहरण पर जाने पर I, यह जांचता है कि क्या bound(I) वर्तमान ऊपरी सीमा के बराबर या उससे अधिक है; यदि ऐसा है तो, I को खोज से सुरक्षित रूप से हटाया जा सकता है और इस प्रकार पुनरावर्तन बंद हो जाता है। इस प्रकार यह सार्टिंग सामान्यतः वैश्विक वैरियेबल को बनाए रखने के द्वारा कार्यान्वित किया जाता है जो कि अब तक की जांच की गई सभी उदाहरणों में देखी गई न्यूनतम ऊपरी सीमा को रिकॉर्ड करता है।

सामान्य संस्करण

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

1. इस प्रकार अनुमानी का उपयोग करके समाधान x_h की अनुकूलन समस्या को सर्च करने के लिए किया जाता हैं। इसका मूल्य संग्रहीत करें, B = f(x_h). (यदि कोई अनुमानी मान उपलब्ध नहीं है, तो इस प्रकार B अनंत की ओर सेट करते हैं।) इस प्रकार B अब तक मिले सर्वोत्तम समाधान को दर्शाएगा, और उपयोगकर्ता समाधानों पर ऊपरी सीमा के रूप में उपयोग किया जाएगा।
2. इस प्रकार असाइन की गई समस्या के किसी भी चर के साथ आंशिक समाधान रखने के लिए क्रम आरंभ करते हैं।
3. यह क्रम रिक्त होने तक लूप चलता रहता हैं:
   1. इस प्रकार एक नोड लें N क्रम से बाहर रखते हैं।
   2. यदि N एकल उपयोगकर्ता समाधान का प्रतिनिधित्व करता है x और f(x) < B, तब x अब तक का सबसे अच्छा समाधान है। इसे रिकॉर्ड करें और सेट करें B ← f(x).
   3. इसके अतिरिक्त आगे बढ़ने पर N नए नोड बनाने के लिए N_i इनमें से प्रत्येक के लिए:
      1. यदि bound(N_i) > B, कुछ भी नहीं है, चूंकि इस प्रकार इस नोड पर निचली सीमा समस्या की ऊपरी सीमा से अधिक है, इसलिए यह कभी भी इष्टतम समाधान की ओर नहीं ले जाएगी, और इसे त्याग दिया जा सकता है।
      2. इसके अतिरिक्त N_i क्रम में स्टोर करें।

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

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

एक सी ++ - उपरोक्त के स्यूडोकोड कार्यान्वयन के समान है।

// C++-like implementation of branch and bound, 
// assuming the objective function f is to be minimized
CombinatorialSolution branch_and_bound_solve(
    CombinatorialProblem problem, 
    ObjectiveFunction objective_function /*f*/,
    BoundingFunction lower_bound_function /*bound*/) 
{
    // Step 1 above
    double problem_upper_bound = std::numeric_limits<double>::infinity; // = B
    CombinatorialSolution heuristic_solution = heuristic_solve(problem); // x_h
    problem_upper_bound = objective_function(heuristic_solution); // B = f(x_h)
    CombinatorialSolution current_optimum = heuristic_solution;
    // Step 2 above
    queue<CandidateSolutionTree> candidate_queue;
    // problem-specific queue initialization
    candidate_queue = populate_candidates(problem);
    while (!candidate_queue.empty()) { // Step 3 above
        // Step 3.1
        CandidateSolutionTree node = candidate_queue.pop();
        // "node" represents N above
        if (node.represents_single_candidate()) { // Step 3.2
            if (objective_function(node.candidate()) < problem_upper_bound) {
                current_optimum = node.candidate();
                problem_upper_bound = objective_function(current_optimum);
            }
            // else, node is a single candidate which is not optimum
        }
        else { // Step 3.3: node represents a branch of candidate solutions
            // "child_branch" represents N_i above
            for (auto&& child_branch : node.candidate_nodes) {
                if (lower_bound_function(child_branch) <= problem_upper_bound) {
                    candidate_queue.enqueue(child_branch); // Step 3.3.2
                }
                // otherwise, bound(N_i) > B so we prune the branch; step 3.3.1
            }
        }
    }
    return current_optimum;

}

उपरोक्त स्यूडोकोड में, functions heuristic_solve और populate_candidates समस्या के लिए उपयुक्त के रूप में सबरूटीन्स के रूप में काॅल किया जाना चाहिए। फंक्शन f (objective_function) और bound (lower_bound_function) लिखित रूप में फंक्शन एलिमेंट के रूप में माना जाता है, और इस प्रकार सी ++ प्रोग्रामिंग भाषा में अज्ञात फ़ंक्शंस, फंक्शन प्वाइंट और अन्य प्रकार के कॉल करने योग्य ऑब्जेक्ट्स के अनुरूप हो सकता है।

सुधार

इस प्रकार $\mathbf {x}$ का सदिश $\mathbb {R} ^{n}$ है , इस प्रकार ब्रांचिंग और बाउंड एल्गोरिदम को अंतराल अंकगणित के साथ जोड़ा जा सकता है इस प्रकार वैश्विक न्यूनतम को संलग्नक प्रदान करने के लिए अंतराल काॅंट्रैक्टर विधियों का उपओग करते हैं।

अनुप्रयोग

इस दृष्टिकोण का उपयोग कई एनपी-हार्ड समस्याओं के लिए किया जाता है:

• पूर्णांक प्रोग्रामिंग
• नॉनलाइनियर प्रोग्रामिंग
• ट्रैवलिंग सेल्समैन की समस्या (TSP)
• द्विघात असाइनमेंट समस्या (QAP)
• अधिकतम संतुष्टि समस्या (मैक्स-सैट)
• निकटतम पड़ोसी खोज (कीनोसुके फुकुनागा द्वारा)
• फ्लो शॉप शेड्यूलिंग
• स्टॉक की समस्या में कटौती
• कम्प्यूटेशनल फाइलोजेनेटिक्स
• उलटा सेट करें
• अनुमान लगाएं
• 0/1 बैग समस्या
• कवर समस्या सेट करें
• यंत्र अधिगम में फ़ीचर चयन
• कंप्यूटर दृष्टि में संरचित भविष्यवाणी
• चाइनीज पोस्टमैन समस्या सहित आर्क रूटिंग समस्या
• प्रतिभा निर्धारण , सीन शूटिंग अरेंजमेंट प्रॉब्लम

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

अन्य एल्गोरिदम से संबंध

नौ एट अल शाखा और बाउंड का सामान्यीकरण प्रस्तुत करता है जो A* खोज एल्गोरिद्म या A*, B* और ऐल्फा–बीटा प्रूनिंग या ऐल्फा–बीटा सर्च एल्गोरिद्म को समाहित करता है।

अनुकूलन उदाहरण

इस समस्या को हल करने के लिए शाखा और बाउंड का उपयोग किया जा सकता है

अधिकतम $Z=5x_{1}+6x_{2}$ इन बाधाओं के साथ

$x_{1}+x_{2}\leq 50$

$4x_{1}+7x_{2}\leq 280$

$x_{1}x_{2}\geq 0$

$x_{1}$ और $x_{2}$ पूर्णांक हैं।

पहला चरण में पूर्णांक बाधा को उपयोग नहीं किया जाता है। इस प्रकार रेखा बनाने वाले पहले समीकरण के लिए हमारे पास दो चरम बिंदु हैं: ${\begin{bmatrix}x_{1}\\x_{2}\end{bmatrix}}={\begin{bmatrix}50\\0\end{bmatrix}}$ और ${\begin{bmatrix}0\\50\end{bmatrix}}$, इस प्रकार हम सदिश बिंदुओं के साथ दूसरी पंक्ति ${\begin{bmatrix}0\\40\end{bmatrix}}$ और ${\begin{bmatrix}70\\0\end{bmatrix}}$बना सकते हैं।

दो पंक्तियाँ।

तीसरा बिंदु है ${\begin{bmatrix}0\\0\end{bmatrix}}$ यह उत्तल है इसलिए समाधान क्षेत्र के किसी कोने पर स्थित है। इस प्रकार हम पंक्ति में कमी का उपयोग करके चौराहे का पता लगा सकते हैं, जो कि है ${\begin{bmatrix}70/3\\80/3\end{bmatrix}}$, या ${\begin{bmatrix}23.333\\26.667\end{bmatrix}}$ 276.667 के मान के साथ उपयोग किया जाता हैं। इस प्रकार हम क्षेत्र के ऊपर रेखा को स्वीप करके अन्य समापन बिंदुओं का परीक्षण करते हैं और पाते हैं कि यह वास्तविक से अधिक अधिकतम है।

इस मामले में, हम अधिकतम भिन्नात्मक भाग वाले चर को चुनते हैं $x_{2}$ शाखा और बाउंड विधि के लिए पैरामीटर बन जाता है। हम शाखा करते हैं $x_{2}\leq 26$ और 276 @ प्राप्त करें $\langle 24,26\rangle$. हम पूर्णांक समाधान तक पहुँच चुके हैं इसलिए हम दूसरी शाखा में $x_{2}\geq 27$ जाते हैं। इस प्रकार हम 275.75 @ प्राप्त करते हैं$\langle 22.75,27\rangle$. हमारे पास दशमलव है इसलिए हम ब्रांच करते हैं, इस प्रकार $x_{1}$ को $x_{1}\leq 22$ और हम पाते हैं 274.571 @$\langle 22,27.4286\rangle$. हम दूसरी शाखा $x_{1}\geq 23$ का प्रयास करते हैं और कोई व्यवहार्य समाधान नहीं हैं। इसलिए, अधिकतम 276 है $x_{1}\longmapsto 24$ और $x_{2}\longmapsto 26$ संभव हैं।

यह भी देखें

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

बाहरी संबंध

• LiPS – Free easy-to-use GUI program intended for solving linear, integer and goal programming problems.
• Cbc – (Coin-or branch and cut) is an open-source mixed integer programming solver written in C++.

| group5 = Metaheuristics | abbr5 = heuristic | list5 =

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

| below =

• Software

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

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

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

}}