{"id":15612,"date":"2022-04-19T14:03:28","date_gmt":"2022-04-19T13:03:28","guid":{"rendered":"https:\/\/complex-systems-ai.com\/?page_id=15612"},"modified":"2024-02-11T16:04:54","modified_gmt":"2024-02-11T15:04:54","slug":"exercice-corrige-branch-and-bound","status":"publish","type":"page","link":"https:\/\/complex-systems-ai.com\/en\/combinatorial-optimization-2\/exercise-corrects-branch-and-bound\/","title":{"rendered":"1 Corrected exercise Branch and Bound"},"content":{"rendered":"<div data-elementor-type=\"wp-page\" data-elementor-id=\"15612\" class=\"elementor elementor-15612\">\n\t\t\t\t\t\t<section class=\"elementor-section elementor-top-section elementor-element elementor-element-9ed89d6 elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"9ed89d6\" 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-4d5d85f\" data-id=\"4d5d85f\" 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-8ce9d09 elementor-align-justify elementor-widget elementor-widget-button\" data-id=\"8ce9d09\" 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-7776d74\" data-id=\"7776d74\" 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-20411aa elementor-align-justify elementor-widget elementor-widget-button\" data-id=\"20411aa\" 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-34ce881\" data-id=\"34ce881\" 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-6bbb95b elementor-align-justify elementor-widget elementor-widget-button\" data-id=\"6bbb95b\" 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:\/\/en.wikipedia.org\/wiki\/Branch_and_bound\" 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-485855a elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"485855a\" 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-53d917d\" data-id=\"53d917d\" 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-fbb3d7c elementor-widget elementor-widget-text-editor\" data-id=\"fbb3d7c\" 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>This page presents a detailed corrected exercise of the problem of <a href=\"https:\/\/complex-systems-ai.com\/en\/linear-programming-2\/\">linear programming<\/a> solved by the algorithm of <a href=\"https:\/\/complex-systems-ai.com\/en\/combinatorial-optimization-2\/branch-and-bound\/\">branch and bound<\/a>.<\/p><p><img decoding=\"async\" class=\"aligncenter wp-image-11096 size-full\" src=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2020\/09\/cropped-Capture.png\" alt=\"branch and bound\" width=\"97\" height=\"97\" title=\"\"><\/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<section class=\"elementor-section elementor-top-section elementor-element elementor-element-e669c9f elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"e669c9f\" 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-e630115\" data-id=\"e630115\" 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-37ae126 elementor-widget elementor-widget-heading\" data-id=\"37ae126\" data-element_type=\"widget\" data-e-type=\"widget\" data-widget_type=\"heading.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t\t\t<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\/exercise-corrects-branch-and-bound\/#Exercice-corrige-pas-a-pas-du-branch-and-bound\" >Branch and bound step-by-step corrected exercise<\/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\/exercise-corrects-branch-and-bound\/#Solution\" >Solution<\/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\/exercise-corrects-branch-and-bound\/#Premier-branchement\" >First connection<\/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\/exercise-corrects-branch-and-bound\/#Deuxieme-branchement\" >Second connection<\/a><\/li><li class='ez-toc-page-1 ez-toc-heading-level-2'><a class=\"ez-toc-link ez-toc-heading-5\" href=\"https:\/\/complex-systems-ai.com\/en\/combinatorial-optimization-2\/exercise-corrects-branch-and-bound\/#Troisieme-branchement\" >Third connection<\/a><\/li><li class='ez-toc-page-1 ez-toc-heading-level-2'><a class=\"ez-toc-link ez-toc-heading-6\" href=\"https:\/\/complex-systems-ai.com\/en\/combinatorial-optimization-2\/exercise-corrects-branch-and-bound\/#Recapitulatif-de-la-methode-en-anglais\" >Summary of the method<\/a><\/li><\/ul><\/nav><\/div>\n<h2 class=\"elementor-heading-title elementor-size-default\"><span class=\"ez-toc-section\" id=\"Exercice-corrige-pas-a-pas-du-branch-and-bound\"><\/span>Branch and bound step-by-step corrected exercise<span class=\"ez-toc-section-end\"><\/span><\/h2>\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-a9fbdc9 elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"a9fbdc9\" 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-2cf986a\" data-id=\"2cf986a\" 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-dfbb9cb elementor-widget elementor-widget-text-editor\" data-id=\"dfbb9cb\" 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>A machine shop owner plans to expand by purchasing new machines, presses and lathes. The owner estimated that each purchased press will increase profits by 100 $ per day and each spin will increase profits by 150 $ per day. The number of machines the owner can purchase is limited by the cost of the machines and the floor space available in the workshop. Machine purchase prices and space requirements are as follows.<\/p><p><img decoding=\"async\" class=\"alignnone wp-image-15615 size-medium\" src=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2022\/04\/bnb-300x104.png\" alt=\"branch and bound separation and evaluation\" width=\"300\" height=\"104\" title=\"\" srcset=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2022\/04\/bnb-300x104.png 300w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2022\/04\/bnb-18x6.png 18w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2022\/04\/bnb.png 481w\" sizes=\"(max-width: 300px) 100vw, 300px\" \/><\/p><p>The owner has a budget of 40,000 $ for the purchase of machinery and 200 square feet of floor space available. The owner wants to know how many of each type of machine to buy to maximize the daily increase in profits. Solve this problem.<\/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<section class=\"elementor-section elementor-top-section elementor-element elementor-element-a6c583a elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"a6c583a\" 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-1b768d1\" data-id=\"1b768d1\" 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-f02b5c9 elementor-widget elementor-widget-heading\" data-id=\"f02b5c9\" data-element_type=\"widget\" data-e-type=\"widget\" data-widget_type=\"heading.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t\t\t<h2 class=\"elementor-heading-title elementor-size-default\"><span class=\"ez-toc-section\" id=\"Solution\"><\/span>Solution<span class=\"ez-toc-section-end\"><\/span><\/h2>\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-c4ccedb elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"c4ccedb\" 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-5e5de4e\" data-id=\"5e5de4e\" 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-adefda6 elementor-widget elementor-widget-text-editor\" data-id=\"adefda6\" 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>The first step is modeling the problem, this is a <a href=\"https:\/\/complex-systems-ai.com\/en\/help-with-the-decision\/linear-modeling\/\">linear problem<\/a> as an integer (so the <a href=\"https:\/\/complex-systems-ai.com\/en\/linear-programming-2\/simplex-method-2\/\">simplex<\/a> cannot apply).<\/p><p><img decoding=\"async\" class=\"alignnone wp-image-15616 size-medium\" src=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2022\/04\/bnb2-300x155.png\" alt=\"branch and bound separation and evaluation\" width=\"300\" height=\"155\" title=\"\" srcset=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2022\/04\/bnb2-300x155.png 300w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2022\/04\/bnb2-18x9.png 18w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2022\/04\/bnb2.png 365w\" sizes=\"(max-width: 300px) 100vw, 300px\" \/><\/p><p>With x_1 the number of presses and x_2 the number of turns.<\/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<section class=\"elementor-section elementor-top-section elementor-element elementor-element-e77b352 elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"e77b352\" 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-9da86e1\" data-id=\"9da86e1\" 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-f6894b1 elementor-widget elementor-widget-text-editor\" data-id=\"f6894b1\" 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>We start the branch and bound method by first solving the problem as a regular linear programming model with no restrictions on integers (that is, restrictions on integers are relaxed or relaxed). The linear programming model for the problem and the optimal relaxed solution is<\/p><p><img loading=\"lazy\" decoding=\"async\" class=\"alignnone wp-image-15617 size-medium\" src=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2022\/04\/bnb3-300x166.png\" alt=\"branch and bound separation and evaluation\" width=\"300\" height=\"166\" title=\"\" srcset=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2022\/04\/bnb3-300x166.png 300w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2022\/04\/bnb3-18x10.png 18w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2022\/04\/bnb3.png 334w\" sizes=\"(max-width: 300px) 100vw, 300px\" \/><\/p><p>The relaxed optimal solution is x_1=2.22 and x_2=5.56 with Z=1055.56.<\/p><p>The branch and bound method uses a diagram consisting of nodes and branches as a framework for the solution process. The first node in the branch and link diagram, shown in Figure C-1, contains the relaxed linear programming solution shown earlier and the rounded solution.<\/p><p><img loading=\"lazy\" decoding=\"async\" class=\"alignnone wp-image-15618 size-medium\" src=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2022\/04\/bnb4-300x163.png\" alt=\"branch and bound separation and evaluation\" width=\"300\" height=\"163\" title=\"\" srcset=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2022\/04\/bnb4-300x163.png 300w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2022\/04\/bnb4-18x10.png 18w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2022\/04\/bnb4.png 330w\" sizes=\"(max-width: 300px) 100vw, 300px\" \/><\/p><p>We denote upper bound the result of the relaxed optimal solution, and lower bound the result of the optimal solution as an integer (rounded down).<\/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<section class=\"elementor-section elementor-top-section elementor-element elementor-element-1929da9 elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"1929da9\" 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-fc69b69\" data-id=\"fc69b69\" 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-d47b106 elementor-widget elementor-widget-heading\" data-id=\"d47b106\" data-element_type=\"widget\" data-e-type=\"widget\" data-widget_type=\"heading.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t\t\t<h2 class=\"elementor-heading-title elementor-size-default\"><span class=\"ez-toc-section\" id=\"Premier-branchement\"><\/span>First connection<span class=\"ez-toc-section-end\"><\/span><\/h2>\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-d71dd6a elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"d71dd6a\" 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-3b81937\" data-id=\"3b81937\" 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-b3a1a4b elementor-widget elementor-widget-text-editor\" data-id=\"b3a1a4b\" 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>Create two constraints (or subsets) to eliminate the fractional part of the value from the solution and see which is farthest from the rounded integer value (i.e. which variable has the largest fractional part in value absolute). The 0.56 part of 5.56 is the largest fractional part; thus, x_2 will be the variable we are going to &quot;plug&quot; into.<\/p><p>In other words, we will create two alternative linear programs taking into account respectively that x_2 must be less than or equal to 5 on the one hand; and x_2 must be greater than or equal to 6 on the other hand.<\/p><p>So we have the following connection:<\/p><p><img loading=\"lazy\" decoding=\"async\" class=\"alignnone wp-image-15628 size-medium\" src=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2022\/04\/bnb5-300x218.png\" alt=\"branch and bound separation and evaluation\" width=\"300\" height=\"218\" title=\"\" srcset=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2022\/04\/bnb5-300x218.png 300w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2022\/04\/bnb5-18x12.png 18w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2022\/04\/bnb5.png 431w\" sizes=\"(max-width: 300px) 100vw, 300px\" \/><\/p><p>Let&#039;s solve the problem on the left:<\/p><p><img loading=\"lazy\" decoding=\"async\" class=\"alignnone wp-image-15629 size-medium\" src=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2022\/04\/bnb6-300x189.png\" alt=\"branch and bound separation and evaluation\" width=\"300\" height=\"189\" title=\"\" srcset=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2022\/04\/bnb6-300x189.png 300w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2022\/04\/bnb6-18x12.png 18w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2022\/04\/bnb6.png 336w\" sizes=\"(max-width: 300px) 100vw, 300px\" \/><\/p><p>This gives the solution x_1=2.5, x_2=5 and Z=1000.<\/p><p>Let&#039;s solve the system on the right:<\/p><p><img loading=\"lazy\" decoding=\"async\" class=\"alignnone wp-image-15630 size-medium\" src=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2022\/04\/bnb7-300x179.png\" alt=\"branch and bound separation and evaluation\" width=\"300\" height=\"179\" title=\"\" srcset=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2022\/04\/bnb7-300x179.png 300w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2022\/04\/bnb7-18x12.png 18w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2022\/04\/bnb7.png 340w\" sizes=\"(max-width: 300px) 100vw, 300px\" \/><\/p><p>This system has for solution x_1=1.33 and x_2=6, Z=1033.33<\/p><p>From a practical point of view, we cut the <a href=\"https:\/\/complex-systems-ai.com\/en\/linear-programming-2\/lp-solutions-and-realizable-domain\/\">definition field<\/a> with the constraint x_2=6 and have resolved on either side of the constraint the linear system released.<\/p><p><img loading=\"lazy\" decoding=\"async\" class=\"alignnone wp-image-15631 size-full\" src=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2022\/04\/bnb8.png\" alt=\"branch and bound separation and evaluation\" width=\"754\" height=\"418\" title=\"\" srcset=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2022\/04\/bnb8.png 754w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2022\/04\/bnb8-300x166.png 300w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2022\/04\/bnb8-18x10.png 18w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2022\/04\/bnb8-600x333.png 600w\" sizes=\"(max-width: 754px) 100vw, 754px\" \/><\/p><p>Let&#039;s update our <a href=\"https:\/\/complex-systems-ai.com\/en\/graph-theory-2\/\">graph<\/a> with the new UB and LB of each system obtained.<\/p><p><img loading=\"lazy\" decoding=\"async\" class=\"alignnone wp-image-15632 size-full\" src=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2022\/04\/bnb9.png\" alt=\"branch and bound separation and evaluation\" width=\"656\" height=\"310\" title=\"\" srcset=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2022\/04\/bnb9.png 656w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2022\/04\/bnb9-300x142.png 300w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2022\/04\/bnb9-18x9.png 18w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2022\/04\/bnb9-600x284.png 600w\" sizes=\"(max-width: 656px) 100vw, 656px\" \/><\/p><p>Since we don&#039;t have an optimal and feasible integer solution yet, we need to continue branching (i.e., partitioning) the model, either from node 2 or from node 3. A look at Figure reveals that if we branch from node 2, the maximum value that can possibly be reached is 1000 $ (the upper bound).<\/p><p>However, if we start from node 3, a higher maximum value of 1033 $ is possible. Thus, we will branch off from node 3. In general, always branch off from the node with the maximum upper bound.<\/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<section class=\"elementor-section elementor-top-section elementor-element elementor-element-168372d elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"168372d\" 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-5de9616\" data-id=\"5de9616\" 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-397392e elementor-widget elementor-widget-heading\" data-id=\"397392e\" data-element_type=\"widget\" data-e-type=\"widget\" data-widget_type=\"heading.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t\t\t<h2 class=\"elementor-heading-title elementor-size-default\"><span class=\"ez-toc-section\" id=\"Deuxieme-branchement\"><\/span>Second connection<span class=\"ez-toc-section-end\"><\/span><\/h2>\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-abd8d9e elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"abd8d9e\" 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-30b767f\" data-id=\"30b767f\" 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-004e493 elementor-widget elementor-widget-text-editor\" data-id=\"004e493\" 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>Now the branching steps previously followed at node 1 are repeated at node 3. First, the variable that has the value with the largest fractional part is selected. Since x_2 has an integer value, x_1, with a fractional part of 0.33, is the only variable we can select. Thus, two new constraints are developed from x_1.<\/p><p><img loading=\"lazy\" decoding=\"async\" class=\"alignnone wp-image-15633 size-full\" src=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2022\/04\/bnb10.png\" alt=\"branch and bound separation and evaluation\" width=\"701\" height=\"462\" title=\"\" srcset=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2022\/04\/bnb10.png 701w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2022\/04\/bnb10-300x198.png 300w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2022\/04\/bnb10-18x12.png 18w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2022\/04\/bnb10-600x395.png 600w\" sizes=\"(max-width: 701px) 100vw, 701px\" \/><\/p><p>Taking node 4, we have the following linear program:<\/p><p><img loading=\"lazy\" decoding=\"async\" class=\"alignnone wp-image-15634 size-medium\" src=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2022\/04\/bnb11-300x214.png\" alt=\"branch and bound separation and evaluation\" width=\"300\" height=\"214\" title=\"\" srcset=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2022\/04\/bnb11-300x214.png 300w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2022\/04\/bnb11-18x12.png 18w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2022\/04\/bnb11-120x85.png 120w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2022\/04\/bnb11.png 334w\" sizes=\"(max-width: 300px) 100vw, 300px\" \/><\/p><p>The solution to the problem is x_1=1 and x_2=6.17 with Z=1025.<\/p><p>The second problem is:<\/p><p><img loading=\"lazy\" decoding=\"async\" class=\"alignnone wp-image-15635 size-medium\" src=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2022\/04\/bnb12-300x225.png\" alt=\"branch and bound separation and evaluation\" width=\"300\" height=\"225\" title=\"\" srcset=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2022\/04\/bnb12-300x225.png 300w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2022\/04\/bnb12-16x12.png 16w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2022\/04\/bnb12.png 317w\" sizes=\"(max-width: 300px) 100vw, 300px\" \/><\/p><p>This problem does not admit a solution (first constraint is violated). So we have the following solution graph:<\/p><p><img loading=\"lazy\" decoding=\"async\" class=\"alignnone wp-image-15636 size-full\" src=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2022\/04\/bnb13.png\" alt=\"branch and bound separation and evaluation\" width=\"705\" height=\"451\" title=\"\" srcset=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2022\/04\/bnb13.png 705w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2022\/04\/bnb13-300x192.png 300w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2022\/04\/bnb13-18x12.png 18w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2022\/04\/bnb13-600x384.png 600w\" sizes=\"(max-width: 705px) 100vw, 705px\" \/><\/p><p>We still don&#039;t have an integer solution, so we have to continue the branch and bound algorithm<\/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<section class=\"elementor-section elementor-top-section elementor-element elementor-element-b7c390e elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"b7c390e\" 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-9ac46f4\" data-id=\"9ac46f4\" 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-3ea6162 elementor-widget elementor-widget-heading\" data-id=\"3ea6162\" data-element_type=\"widget\" data-e-type=\"widget\" data-widget_type=\"heading.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t\t\t<h2 class=\"elementor-heading-title elementor-size-default\"><span class=\"ez-toc-section\" id=\"Troisieme-branchement\"><\/span>Third connection<span class=\"ez-toc-section-end\"><\/span><\/h2>\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-9817b4f elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"9817b4f\" 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-f87d1b7\" data-id=\"f87d1b7\" 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-c3af834 elementor-widget elementor-widget-text-editor\" data-id=\"c3af834\" 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>Node 4 has the best UB. Since x_2 is the only variable that is not an integer, we will branch to this variable.<\/p><p><img loading=\"lazy\" decoding=\"async\" class=\"alignnone wp-image-15637 size-full\" src=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2022\/04\/bnb14.png\" alt=\"branch and bound separation and evaluation\" width=\"691\" height=\"599\" title=\"\" srcset=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2022\/04\/bnb14.png 691w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2022\/04\/bnb14-300x260.png 300w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2022\/04\/bnb14-14x12.png 14w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2022\/04\/bnb14-600x520.png 600w\" sizes=\"(max-width: 691px) 100vw, 691px\" \/><\/p><p>After solving the two linear programs at nodes 6 and 7, we obtain the following results:<\/p><p><img loading=\"lazy\" decoding=\"async\" class=\"alignnone wp-image-15638 size-full\" src=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2022\/04\/bnb15.png\" alt=\"branch and bound separation and evaluation\" width=\"712\" height=\"604\" title=\"\" srcset=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2022\/04\/bnb15.png 712w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2022\/04\/bnb15-300x254.png 300w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2022\/04\/bnb15-14x12.png 14w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2022\/04\/bnb15-600x509.png 600w\" sizes=\"(max-width: 712px) 100vw, 712px\" \/><\/p><p>The solution to node 6 corresponds to the criteria of the original problem (ie in whole number). Only the branch at 3 and 4 have a UB higher than node 6, however, the branch that gives node 5 and 7 does not have a feasible solution. We conclude that the optimal solution is found at node 6.<\/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<section class=\"elementor-section elementor-top-section elementor-element elementor-element-9f7bcd6 elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"9f7bcd6\" 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-4ed004f\" data-id=\"4ed004f\" 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-2bb33df elementor-widget elementor-widget-heading\" data-id=\"2bb33df\" data-element_type=\"widget\" data-e-type=\"widget\" data-widget_type=\"heading.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t\t\t<h2 class=\"elementor-heading-title elementor-size-default\"><span class=\"ez-toc-section\" id=\"Recapitulatif-de-la-methode-en-anglais\"><\/span>Summary of the method<span class=\"ez-toc-section-end\"><\/span><\/h2>\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-4335172 elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"4335172\" 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-e14f86b\" data-id=\"e14f86b\" 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-0d4c5b5 elementor-widget elementor-widget-text-editor\" data-id=\"0d4c5b5\" 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>Here is a summary in English of the method we have just used.<\/p><p><img loading=\"lazy\" decoding=\"async\" class=\"alignnone wp-image-15639 size-full\" src=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2022\/04\/bnb16.png\" alt=\"branch and bound separation and evaluation\" width=\"855\" height=\"642\" title=\"\" srcset=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2022\/04\/bnb16.png 855w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2022\/04\/bnb16-300x225.png 300w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2022\/04\/bnb16-768x577.png 768w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2022\/04\/bnb16-16x12.png 16w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2022\/04\/bnb16-600x451.png 600w\" sizes=\"(max-width: 855px) 100vw, 855px\" \/><\/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 This page presents a detailed corrected exercise of the linear programming problem solved by the branch and bound algorithm. Exercise \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-15612","page","type-page","status-publish","hentry"],"amp_enabled":true,"_links":{"self":[{"href":"https:\/\/complex-systems-ai.com\/en\/wp-json\/wp\/v2\/pages\/15612","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=15612"}],"version-history":[{"count":6,"href":"https:\/\/complex-systems-ai.com\/en\/wp-json\/wp\/v2\/pages\/15612\/revisions"}],"predecessor-version":[{"id":20259,"href":"https:\/\/complex-systems-ai.com\/en\/wp-json\/wp\/v2\/pages\/15612\/revisions\/20259"}],"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=15612"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}