{"id":2091,"date":"2016-02-18T16:20:26","date_gmt":"2016-02-18T15:20:26","guid":{"rendered":"http:\/\/smart--grid.net\/?page_id=2091"},"modified":"2022-12-03T22:58:55","modified_gmt":"2022-12-03T21:58:55","slug":"branch-and-bound","status":"publish","type":"page","link":"https:\/\/complex-systems-ai.com\/en\/combinatorial-optimization-2\/branch-and-bound\/","title":{"rendered":"Branch and bound"},"content":{"rendered":"<div data-elementor-type=\"wp-page\" data-elementor-id=\"2091\" class=\"elementor elementor-2091\">\n\t\t\t\t\t\t<section class=\"elementor-section elementor-top-section elementor-element elementor-element-d247133 elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"d247133\" data-element_type=\"section\" data-e-type=\"section\">\n\t\t\t\t\t\t<div class=\"elementor-container elementor-column-gap-default\">\n\t\t\t\t\t<div class=\"elementor-column elementor-col-33 elementor-top-column elementor-element elementor-element-d72ccde\" data-id=\"d72ccde\" data-element_type=\"column\" data-e-type=\"column\">\n\t\t\t<div class=\"elementor-widget-wrap elementor-element-populated\">\n\t\t\t\t\t\t<div class=\"elementor-element elementor-element-d54a9dd elementor-align-justify elementor-widget elementor-widget-button\" data-id=\"d54a9dd\" data-element_type=\"widget\" data-e-type=\"widget\" data-widget_type=\"button.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t\t\t\t\t\t\t<div class=\"elementor-button-wrapper\">\n\t\t\t\t\t<a class=\"elementor-button elementor-button-link elementor-size-sm\" href=\"https:\/\/complex-systems-ai.com\/en\/combinatorial-optimization-2\/\">\n\t\t\t\t\t\t<span class=\"elementor-button-content-wrapper\">\n\t\t\t\t\t\t\t\t\t<span class=\"elementor-button-text\">Combinatorial optimization<\/span>\n\t\t\t\t\t<\/span>\n\t\t\t\t\t<\/a>\n\t\t\t\t<\/div>\n\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t<div class=\"elementor-column elementor-col-33 elementor-top-column elementor-element elementor-element-436b749\" data-id=\"436b749\" data-element_type=\"column\" data-e-type=\"column\">\n\t\t\t<div class=\"elementor-widget-wrap elementor-element-populated\">\n\t\t\t\t\t\t<div class=\"elementor-element elementor-element-df22ec7 elementor-align-justify elementor-widget elementor-widget-button\" data-id=\"df22ec7\" data-element_type=\"widget\" data-e-type=\"widget\" data-widget_type=\"button.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t\t\t\t\t\t\t<div class=\"elementor-button-wrapper\">\n\t\t\t\t\t<a class=\"elementor-button elementor-button-link elementor-size-sm\" href=\"https:\/\/complex-systems-ai.com\/en\/\">\n\t\t\t\t\t\t<span class=\"elementor-button-content-wrapper\">\n\t\t\t\t\t\t\t\t\t<span class=\"elementor-button-text\">Home page<\/span>\n\t\t\t\t\t<\/span>\n\t\t\t\t\t<\/a>\n\t\t\t\t<\/div>\n\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t<div class=\"elementor-column elementor-col-33 elementor-top-column elementor-element elementor-element-260d458\" data-id=\"260d458\" data-element_type=\"column\" data-e-type=\"column\">\n\t\t\t<div class=\"elementor-widget-wrap elementor-element-populated\">\n\t\t\t\t\t\t<div class=\"elementor-element elementor-element-de7d1e0 elementor-align-justify elementor-widget elementor-widget-button\" data-id=\"de7d1e0\" data-element_type=\"widget\" data-e-type=\"widget\" data-widget_type=\"button.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t\t\t\t\t\t\t<div class=\"elementor-button-wrapper\">\n\t\t\t\t\t<a class=\"elementor-button elementor-button-link elementor-size-sm\" href=\"https:\/\/fr.wikipedia.org\/wiki\/S%C3%A9paration_et_%C3%A9valuation\" target=\"_blank\" rel=\"noopener\">\n\t\t\t\t\t\t<span class=\"elementor-button-content-wrapper\">\n\t\t\t\t\t\t\t\t\t<span class=\"elementor-button-text\">Wiki<\/span>\n\t\t\t\t\t<\/span>\n\t\t\t\t\t<\/a>\n\t\t\t\t<\/div>\n\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/section>\n\t\t\t\t<section class=\"elementor-section elementor-top-section elementor-element elementor-element-77d5ba72 elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"77d5ba72\" data-element_type=\"section\" data-e-type=\"section\">\n\t\t\t\t\t\t<div class=\"elementor-container elementor-column-gap-default\">\n\t\t\t\t\t<div class=\"elementor-column elementor-col-100 elementor-top-column elementor-element elementor-element-7ee7e9ef\" data-id=\"7ee7e9ef\" data-element_type=\"column\" data-e-type=\"column\">\n\t\t\t<div class=\"elementor-widget-wrap elementor-element-populated\">\n\t\t\t\t\t\t<div class=\"elementor-element elementor-element-33898116 elementor-widget elementor-widget-text-editor\" data-id=\"33898116\" data-element_type=\"widget\" data-e-type=\"widget\" data-widget_type=\"text-editor.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t\t\t\t\t\t\t<p><\/p>\n<div id=\"ez-toc-container\" class=\"ez-toc-v2_0_82_2 counter-hierarchy ez-toc-counter ez-toc-grey ez-toc-container-direction\">\n<div class=\"ez-toc-title-container\">\n<p class=\"ez-toc-title\" style=\"cursor:inherit\">Contents<\/p>\n<span class=\"ez-toc-title-toggle\"><a href=\"#\" class=\"ez-toc-pull-right ez-toc-btn ez-toc-btn-xs ez-toc-btn-default ez-toc-toggle\" aria-label=\"Toggle Table of Content\"><span class=\"ez-toc-js-icon-con\"><span class=\"\"><span class=\"eztoc-hide\" style=\"display:none;\">Toggle<\/span><span class=\"ez-toc-icon-toggle-span\"><svg style=\"fill: #999;color:#999\" xmlns=\"http:\/\/www.w3.org\/2000\/svg\" class=\"list-377408\" width=\"20px\" height=\"20px\" viewbox=\"0 0 24 24\" fill=\"none\"><path d=\"M6 6H4v2h2V6zm14 0H8v2h12V6zM4 11h2v2H4v-2zm16 0H8v2h12v-2zM4 16h2v2H4v-2zm16 0H8v2h12v-2z\" fill=\"currentColor\"><\/path><\/svg><svg style=\"fill: #999;color:#999\" class=\"arrow-unsorted-368013\" xmlns=\"http:\/\/www.w3.org\/2000\/svg\" width=\"10px\" height=\"10px\" viewbox=\"0 0 24 24\" version=\"1.2\" baseprofile=\"tiny\"><path d=\"M18.2 9.3l-6.2-6.3-6.2 6.3c-.2.2-.3.4-.3.7s.1.5.3.7c.2.2.4.3.7.3h11c.3 0 .5-.1.7-.3.2-.2.3-.5.3-.7s-.1-.5-.3-.7zM5.8 14.7l6.2 6.3 6.2-6.3c.2-.2.3-.5.3-.7s-.1-.5-.3-.7c-.2-.2-.4-.3-.7-.3h-11c-.3 0-.5.1-.7.3-.2.2-.3.5-.3.7s.1.5.3.7z\"\/><\/svg><\/span><\/span><\/span><\/a><\/span><\/div>\n<nav><ul class='ez-toc-list ez-toc-list-level-1' ><li class='ez-toc-page-1 ez-toc-heading-level-2'><a class=\"ez-toc-link ez-toc-heading-1\" href=\"https:\/\/complex-systems-ai.com\/en\/combinatorial-optimization-2\/branch-and-bound\/#Branch-and-bound\" >Branch and bound<\/a><\/li><li class='ez-toc-page-1 ez-toc-heading-level-2'><a class=\"ez-toc-link ez-toc-heading-2\" href=\"https:\/\/complex-systems-ai.com\/en\/combinatorial-optimization-2\/branch-and-bound\/#La-separation\" >The separation<\/a><\/li><li class='ez-toc-page-1 ez-toc-heading-level-2'><a class=\"ez-toc-link ez-toc-heading-3\" href=\"https:\/\/complex-systems-ai.com\/en\/combinatorial-optimization-2\/branch-and-bound\/#Levaluation\" >Evaluation<\/a><\/li><li class='ez-toc-page-1 ez-toc-heading-level-2'><a class=\"ez-toc-link ez-toc-heading-4\" href=\"https:\/\/complex-systems-ai.com\/en\/combinatorial-optimization-2\/branch-and-bound\/#Exemple-probleme-du-sac-a-dos\" >Example: backpack problem<\/a><\/li><\/ul><\/nav><\/div>\n<h2><span class=\"ez-toc-section\" id=\"Branch-and-bound\"><\/span>Branch and bound<span class=\"ez-toc-section-end\"><\/span><\/h2>\n<p>The Branch and bound algorithm is an &quot;intelligent&quot; enumeration of the tree of possible solutions.<\/p>\n<p><\/p>\n<p><\/p>\n<div style=\"padding: 5px; background-color: #d5edff; border: 2px solid #3c95e8; -moz-border-radius: 9px; -khtml-border-radius: 9px; -webkit-border-radius: 9px; border-radius: 9px;\">\n<p>As its name suggests, the algorithm has two times:<\/p>\n<ol>\n<li>separation: to separate a set of solutions into subsets;<\/li>\n<li>evaluation: evaluate the solutions of a subset by increasing the value of the best solution of this subset.<\/li>\n<\/ol>\n<\/div>\n<p><\/p>\n<p><\/p>\n<p>The Branch and bound algorithm (Separation and evaluation) proposes to go through the tree structure of possible solutions by evaluating each subset of solutions. It keeps in memory the value of the best solution f (s) found so far. When the evaluation of a subset gives a value lower than f (s), the algorithm deems useless to explore it directly after.<\/p>\n<p><\/p>\n<p><\/p>\n<p>The Branch and bound algorithm is often used instead of the <a href=\"https:\/\/complex-systems-ai.com\/en\/algorithmic\/dynamic-programming\/\">dynamic programming<\/a>. The evaluation is often the objective function with relaxed constraints (by decreasing number) according to the depth.<\/p>\n<p><\/p>\n<p><\/p>\n<h2 class=\"wp-block-heading\"><span class=\"ez-toc-section\" id=\"La-separation\"><\/span>The separation<span class=\"ez-toc-section-end\"><\/span><\/h2>\n<p><\/p>\n<p><\/p>\n<p>Branch and bound begins with separation. The set of solutions is separated by fixing the value of one or more variables of the problem. Suppose a problem with three variables, the complete tree of separation in ascending order of the variables is as follows:<\/p>\n<p><\/p>\n<p><\/p>\n<div>\n<figure><img fetchpriority=\"high\" decoding=\"async\" class=\"aligncenter wp-image-2951 size-full\" src=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2016\/02\/bb.png\" alt=\"branch and bound separation\" width=\"776\" height=\"460\" title=\"\" srcset=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2016\/02\/bb.png 776w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2016\/02\/bb-300x178.png 300w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2016\/02\/bb-768x455.png 768w\" sizes=\"(max-width: 776px) 100vw, 776px\" \/><\/figure>\n<\/div>\n<p><\/p>\n<p><\/p>\n<p>There are two exploration techniques, linked to the paths of a <a href=\"https:\/\/complex-systems-ai.com\/en\/graph-theory-2\/trees-and-trees\/\">tree<\/a>. Breadth first consists of favoring the widening of possibilities by increasing depth, there is no backtracking. Depth first favors the widening of possibilities by visiting the deepest leaves. The advantage is to quickly provide \u201cgood\u201d solutions and to eliminate sub-optimal branches.<\/p>\n<p><\/p>\n<p><\/p>\n<h2 class=\"wp-block-heading\"><span class=\"ez-toc-section\" id=\"Levaluation\"><\/span>Evaluation<span class=\"ez-toc-section-end\"><\/span><\/h2>\n<p><\/p>\n<p><\/p>\n<p>Branch and bound takes turns evaluating each separation. The root of the tree is an admissible solution which will serve as a reference. We thus obtain a solution giving a value z increasing the optimal solution.<\/p>\n<p><\/p>\n<p><\/p>\n<div style=\"padding: 5px; background-color: #ffdcd3; border: 2px solid #ff7964; -moz-border-radius: 9px; -khtml-border-radius: 9px; -webkit-border-radius: 9px; border-radius: 9px;\">For the subsets of solutions to be tested, noted S<sub>i<\/sub>, we are looking for a lower bound of the objective function in each subset. We therefore have evaluation (S<sub>i<\/sub>) \u2264min<sub>(x\u2208S<sub>i<\/sub>)<\/sub> f (x). For the case of a maximum, we are looking for an upper bound evaluation (S<sub>i<\/sub>) \u2265max<sub>(x\u2208S<sub>i<\/sub>)<\/sub> f (x).<\/div>\n<p><\/p>\n<p><\/p>\n<p>Assessment is often performed on the initial problem after relaxation. A relaxation makes it possible to pass from complex constraints to linear constraints or of which the dual is simple. For example, integrity relaxation allows working with real variables instead of whole variables.<\/p>\n<p><\/p>\n<p><\/p>\n<div style=\"padding: 3px; border: 2px dotted #a5a5a5; background-color: #f6f9fa;\">\n<p>Once the assessment has been carried out, two cases are possible:<\/p>\n<ul>\n<li>If evaluation (S<sub>i<\/sub>) \u2265z, then S<sub>i<\/sub> does not contain any optimal solution, it is not useful to explore in detail the subset S<sub>i<\/sub>.<\/li>\n<li>If evaluation (S<sub>i<\/sub>) &lt;z, alors on teste l\u2019admissibilit\u00e9 de la solution d\u2019\u00e9valuation. Si elle est admissible, on actualise z, sinon on continue l\u2019exploration jusqu\u2019\u00e0 l\u2019obtention d\u2019une des conditions pr\u00e9c\u00e9dentes.<\/li>\n<\/ul>\n<\/div>\n<p><\/p>\n<p><\/p>\n<h2 class=\"wp-block-heading\"><span class=\"ez-toc-section\" id=\"Exemple-probleme-du-sac-a-dos\"><\/span>Example: backpack problem<span class=\"ez-toc-section-end\"><\/span><\/h2>\n<p><\/p>\n<p><\/p>\n<p>A cargo plane has a cargo capacity of 18 volume units. He must transport containers of goods in such a way as to maximize the total value of his cargo. The available containers are in unlimited quantity for each type:<\/p>\n<p><\/p>\n<p><\/p>\n<ul class=\"wp-block-list\">\n<li>Type A container, value 6, volume 2;<\/li>\n<li>Type B container, value 8, volume 3;<\/li>\n<li>Type C container, value 13, volume 4;<\/li>\n<li>Type D container, value 17, volume 5;<\/li>\n<li>Type E container, value 20, volume 7.<\/li>\n<\/ul>\n<p><\/p>\n<p><\/p>\n<p>At first, we will solve the problem using a <a href=\"https:\/\/complex-systems-ai.com\/en\/algorithmic\/\">algorithm<\/a> gluttonous. Then we will determine the optimal solution by a Branch&amp;Bound procedure.<\/p>\n<p><\/p>\n<p><\/p>\n<p>The <a href=\"https:\/\/complex-systems-ai.com\/en\/help-with-the-decision\/mathematical-modeling\/\">mathematical modeling<\/a> of the problem is the following system: max z=6*x<sub>TO<\/sub>+ 8 * x<sub>B<\/sub>+ 13 * x<sub>VS<\/sub>+ 17 * x<sub>D<\/sub>+ 20 * x<sub>E<\/sub> under 2 * x<sub>TO<\/sub>+ 3 * x<sub>B<\/sub>+ 4 * x<sub>VS<\/sub>+ 5 * x<sub>D<\/sub>+ 7 * x<sub>E<\/sub>\u226418 with x<sub>i<\/sub> the integer number of type i containers.<\/p>\n<p><\/p>\n<p><\/p>\n<p>The initial solution is carried out by the greedy algorithm of the best value \/ volume ratio. We get the solution vector (1,0,0,3,0) with z = 57. x<sub>D<\/sub> being the largest, we will perform the separation on this criterion. We will obtain 4 branches for respectively x<sub>D<\/sub>= 3, 2, 1 and 0:<\/p>\n<p><\/p>\n<p><\/p>\n<ul class=\"wp-block-list\">\n<li>x<sub>D<\/sub>=3. We solve the <a href=\"https:\/\/complex-systems-ai.com\/en\/linear-programming-2\/\">linear program<\/a> relaxed which gives x<sub>VS<\/sub>= 3\/4 and z = 60.75. It is an inadmissible solution therefore one separates compared to x<sub>TO<\/sub> :\n<ul>\n<li>x<sub>TO<\/sub>=1. the <a href=\"https:\/\/complex-systems-ai.com\/en\/help-with-the-decision\/linear-modeling\/\">linear problem<\/a> relaxed gives x<sub>VS<\/sub>= 1\/4 and z = 60.25. This is an unacceptable solution. It is no longer possible to separate because there are no more x<sub>i<\/sub>&gt; 0. The closest whole solution comes down to our starting approximate solution.<\/li>\n<li>x<sub>TO<\/sub>= 0. The relaxed linear problem gives x<sub>B<\/sub>= 1. The solution is admissible and gives z = 59. We update z.<\/li>\n<\/ul>\n<\/li>\n<li>x<sub>D<\/sub>= 2. We solve the relaxed linear program which gives x<sub>VS<\/sub>= 2 and z = 60. It is an admissible solution so we update z.<\/li>\n<li>x<sub>D<\/sub>= 1. We solve the relaxed linear program which gives x<sub>VS<\/sub>= 13\/4 and z = 59.25. This bound is lower than z, so we do not visit this branch.<\/li>\n<li>x<sub>D<\/sub>= 0. We solve the relaxed linear program which gives x<sub>VS<\/sub>= 9\/2 and z = 58.5. This bound is lower than z, so we do not visit this branch.<\/li>\n<\/ul>\n<p><\/p>\n<p><\/p>\n<p>The whole area is explored. The optimum z * = 60 was obtained with the solution vector (0,0,2,2,0).<\/p>\n<p><\/p>\n<p><\/p>\n<div>\n<figure><img decoding=\"async\" class=\"aligncenter wp-image-3037 size-full\" src=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2016\/02\/bb2.png\" alt=\"branch and bound backpack\" width=\"888\" height=\"496\" title=\"\" srcset=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2016\/02\/bb2.png 888w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2016\/02\/bb2-300x168.png 300w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2016\/02\/bb2-768x429.png 768w\" sizes=\"(max-width: 888px) 100vw, 888px\" \/><\/figure>\n<\/div>\n<p><\/p>\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/section>\n\t\t\t\t<\/div>","protected":false},"excerpt":{"rendered":"<p>Combinatorial Optimization Wiki Home Page Branch and bound The Branch and bound algorithm is an \u201cintelligent\u201d enumeration of the tree of possible solutions. \u2026 <\/p>","protected":false},"author":1,"featured_media":0,"parent":1770,"menu_order":0,"comment_status":"closed","ping_status":"closed","template":"","meta":{"footnotes":""},"class_list":["post-2091","page","type-page","status-publish","hentry"],"amp_enabled":true,"_links":{"self":[{"href":"https:\/\/complex-systems-ai.com\/en\/wp-json\/wp\/v2\/pages\/2091","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/complex-systems-ai.com\/en\/wp-json\/wp\/v2\/pages"}],"about":[{"href":"https:\/\/complex-systems-ai.com\/en\/wp-json\/wp\/v2\/types\/page"}],"author":[{"embeddable":true,"href":"https:\/\/complex-systems-ai.com\/en\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/complex-systems-ai.com\/en\/wp-json\/wp\/v2\/comments?post=2091"}],"version-history":[{"count":4,"href":"https:\/\/complex-systems-ai.com\/en\/wp-json\/wp\/v2\/pages\/2091\/revisions"}],"predecessor-version":[{"id":17898,"href":"https:\/\/complex-systems-ai.com\/en\/wp-json\/wp\/v2\/pages\/2091\/revisions\/17898"}],"up":[{"embeddable":true,"href":"https:\/\/complex-systems-ai.com\/en\/wp-json\/wp\/v2\/pages\/1770"}],"wp:attachment":[{"href":"https:\/\/complex-systems-ai.com\/en\/wp-json\/wp\/v2\/media?parent=2091"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}