{"id":6679,"date":"2021-04-19T14:04:21","date_gmt":"2021-04-19T12:04:21","guid":{"rendered":"https:\/\/gts-systems.com\/?p=6679"},"modified":"2024-01-09T14:23:04","modified_gmt":"2024-01-09T13:23:04","slug":"was-bedeutet-branch-and-bound","status":"publish","type":"post","link":"https:\/\/gts-systems.com\/en\/glossar\/was-bedeutet-branch-and-bound\/","title":{"rendered":"Was bedeutet Branch and Bound"},"content":{"rendered":"<div data-elementor-type=\"wp-post\" data-elementor-id=\"6679\" class=\"elementor elementor-6679\" data-elementor-post-type=\"post\">\n\t\t\t\t\t\t<section class=\"elementor-section elementor-top-section elementor-element elementor-element-0630f37 elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"0630f37\" 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-0f3024f\" data-id=\"0f3024f\" 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-6f0a6ac elementor-widget elementor-widget-text-editor\" data-id=\"6f0a6ac\" 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>Branch-and-bound methods are algorithms that solve an optimisation problem by successively restricting or branching decision variables. A so-called decision tree is built up in the process. Before each new branching in a node, it is checked whether the subtree under this node can even occur in an optimal solution. For this purpose, a simpler optimisation problem is solved (relaxation), which specifies a bound for the best possible solution in this subtree.<\/p><p>A branch-and-bound method therefore consists of an alternating process of branching and calculating bounds. A good branch-and-bound method is characterised by the fact that the relaxation can be solved quickly, the relaxation provides a value close to the optimal solution of the original problem and, on average, as few nodes as possible have to be generated in the decision tree.<\/p><p>Branch-and-bound methods are so-called \u2018exact algorithms\u2019. This means that they always provide an optimal solution if the computing time is long enough. Unfortunately, the computing time required for this usually increases exponentially with the runtime, so that in practice only a few classes of optimisation problems can be solved using these methods.<\/p><p>In route planning, so-called branch-and-price methods or branch-and-cut methods or combinations thereof (\u2018branch-and-price-and-cut\u2019) are used in individual cases. These can solve certain types of (large) problems (e.g. travelling salesman problems) well.<\/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>Branch-and-Bound-Verfahren sind Algorithmen, die ein Optimierungsproblem durch sukzessive Einschr\u00e4nkung bzw. Verzweigung (branching) von Entscheidungsvariablen l\u00f6sen. Dabei wird ein sogenannter Entscheidungsbaum (decision tree) aufgebaut. Vor jeder neuen Verzweigung in einem Knoten wird gepr\u00fcft, ob der Teilbaum, der unter diesem Knoten liegt, \u00fcberhaupt in einer optimalen L\u00f6sung vorkommen kann. Dazu wird ein einfacher zu l\u00f6sendes Optimierungsproblem gel\u00f6st [&hellip;]<\/p>\n","protected":false},"author":5,"featured_media":0,"comment_status":"closed","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[23],"tags":[],"class_list":["post-6679","post","type-post","status-publish","format-standard","hentry","category-glossar"],"yoast_head":"<!-- This site is optimized with the Yoast SEO plugin v27.3 - https:\/\/yoast.com\/product\/yoast-seo-wordpress\/ -->\n<title>Was bedeutet Branch and Bound - gts systems<\/title>\n<meta name=\"robots\" content=\"index, follow, max-snippet:-1, max-image-preview:large, max-video-preview:-1\" \/>\n<link rel=\"canonical\" href=\"https:\/\/gts-systems.com\/en\/glossary\/was-bedeutet-branch-and-bound\/\" \/>\n<meta property=\"og:locale\" content=\"en_GB\" \/>\n<meta property=\"og:type\" content=\"article\" \/>\n<meta property=\"og:title\" content=\"Was bedeutet Branch and Bound - gts systems\" \/>\n<meta property=\"og:description\" content=\"Branch-and-Bound-Verfahren sind Algorithmen, die ein Optimierungsproblem durch sukzessive Einschr\u00e4nkung bzw. Verzweigung (branching) von Entscheidungsvariablen l\u00f6sen. Dabei wird ein sogenannter Entscheidungsbaum (decision tree) aufgebaut. Vor jeder neuen Verzweigung in einem Knoten wird gepr\u00fcft, ob der Teilbaum, der unter diesem Knoten liegt, \u00fcberhaupt in einer optimalen L\u00f6sung vorkommen kann. Dazu wird ein einfacher zu l\u00f6sendes Optimierungsproblem gel\u00f6st [&hellip;]\" \/>\n<meta property=\"og:url\" content=\"https:\/\/gts-systems.com\/en\/glossary\/was-bedeutet-branch-and-bound\/\" \/>\n<meta property=\"og:site_name\" content=\"gts systems\" \/>\n<meta property=\"article:published_time\" content=\"2021-04-19T12:04:21+00:00\" \/>\n<meta property=\"article:modified_time\" content=\"2024-01-09T13:23:04+00:00\" \/>\n<meta name=\"author\" content=\"Bastian Grein\" \/>\n<meta name=\"twitter:card\" content=\"summary_large_image\" \/>\n<meta name=\"twitter:label1\" content=\"Written by\" \/>\n\t<meta name=\"twitter:data1\" content=\"Bastian Grein\" \/>\n\t<meta name=\"twitter:label2\" content=\"Estimated reading time\" \/>\n\t<meta name=\"twitter:data2\" content=\"1 minute\" \/>\n<!-- \/ Yoast SEO plugin. -->","yoast_head_json":{"title":"Was bedeutet Branch and Bound - gts systems","robots":{"index":"index","follow":"follow","max-snippet":"max-snippet:-1","max-image-preview":"max-image-preview:large","max-video-preview":"max-video-preview:-1"},"canonical":"https:\/\/gts-systems.com\/en\/glossary\/was-bedeutet-branch-and-bound\/","og_locale":"en_GB","og_type":"article","og_title":"Was bedeutet Branch and Bound - gts systems","og_description":"Branch-and-Bound-Verfahren sind Algorithmen, die ein Optimierungsproblem durch sukzessive Einschr\u00e4nkung bzw. Verzweigung (branching) von Entscheidungsvariablen l\u00f6sen. Dabei wird ein sogenannter Entscheidungsbaum (decision tree) aufgebaut. Vor jeder neuen Verzweigung in einem Knoten wird gepr\u00fcft, ob der Teilbaum, der unter diesem Knoten liegt, \u00fcberhaupt in einer optimalen L\u00f6sung vorkommen kann. Dazu wird ein einfacher zu l\u00f6sendes Optimierungsproblem gel\u00f6st [&hellip;]","og_url":"https:\/\/gts-systems.com\/en\/glossary\/was-bedeutet-branch-and-bound\/","og_site_name":"gts systems","article_published_time":"2021-04-19T12:04:21+00:00","article_modified_time":"2024-01-09T13:23:04+00:00","author":"Bastian Grein","twitter_card":"summary_large_image","twitter_misc":{"Written by":"Bastian Grein","Estimated reading time":"1 minute"},"schema":{"@context":"https:\/\/schema.org","@graph":[{"@type":"Article","@id":"https:\/\/gts-systems.com\/glossar\/was-bedeutet-branch-and-bound\/#article","isPartOf":{"@id":"https:\/\/gts-systems.com\/glossar\/was-bedeutet-branch-and-bound\/"},"author":{"name":"Bastian Grein","@id":"https:\/\/gts-systems.com\/#\/schema\/person\/9ed8a105a05dc3ce47aa43796173bbd1"},"headline":"Was bedeutet Branch and Bound","datePublished":"2021-04-19T12:04:21+00:00","dateModified":"2024-01-09T13:23:04+00:00","mainEntityOfPage":{"@id":"https:\/\/gts-systems.com\/glossar\/was-bedeutet-branch-and-bound\/"},"wordCount":224,"publisher":{"@id":"https:\/\/gts-systems.com\/#organization"},"articleSection":["Glossar"],"inLanguage":"en-GB"},{"@type":"WebPage","@id":"https:\/\/gts-systems.com\/glossar\/was-bedeutet-branch-and-bound\/","url":"https:\/\/gts-systems.com\/glossar\/was-bedeutet-branch-and-bound\/","name":"Was bedeutet Branch and Bound - gts systems","isPartOf":{"@id":"https:\/\/gts-systems.com\/#website"},"datePublished":"2021-04-19T12:04:21+00:00","dateModified":"2024-01-09T13:23:04+00:00","breadcrumb":{"@id":"https:\/\/gts-systems.com\/glossar\/was-bedeutet-branch-and-bound\/#breadcrumb"},"inLanguage":"en-GB","potentialAction":[{"@type":"ReadAction","target":["https:\/\/gts-systems.com\/glossar\/was-bedeutet-branch-and-bound\/"]}]},{"@type":"BreadcrumbList","@id":"https:\/\/gts-systems.com\/glossar\/was-bedeutet-branch-and-bound\/#breadcrumb","itemListElement":[{"@type":"ListItem","position":1,"name":"Startseite","item":"https:\/\/gts-systems.com\/"},{"@type":"ListItem","position":2,"name":"Was bedeutet Branch and Bound"}]},{"@type":"WebSite","@id":"https:\/\/gts-systems.com\/#website","url":"https:\/\/gts-systems.com\/","name":"gts systems","description":"Optimise now","publisher":{"@id":"https:\/\/gts-systems.com\/#organization"},"potentialAction":[{"@type":"SearchAction","target":{"@type":"EntryPoint","urlTemplate":"https:\/\/gts-systems.com\/?s={search_term_string}"},"query-input":{"@type":"PropertyValueSpecification","valueRequired":true,"valueName":"search_term_string"}}],"inLanguage":"en-GB"},{"@type":"Organization","@id":"https:\/\/gts-systems.com\/#organization","name":"gts-systems","url":"https:\/\/gts-systems.com\/","logo":{"@type":"ImageObject","inLanguage":"en-GB","@id":"https:\/\/gts-systems.com\/#\/schema\/logo\/image\/","url":"https:\/\/gts-systems.com\/wp-content\/uploads\/2021\/03\/logogtssystems_1.svg","contentUrl":"https:\/\/gts-systems.com\/wp-content\/uploads\/2021\/03\/logogtssystems_1.svg","width":1,"height":1,"caption":"gts-systems"},"image":{"@id":"https:\/\/gts-systems.com\/#\/schema\/logo\/image\/"},"sameAs":["https:\/\/www.linkedin.com\/company\/gts-systems-and-consulting-gmbh"]},{"@type":"Person","@id":"https:\/\/gts-systems.com\/#\/schema\/person\/9ed8a105a05dc3ce47aa43796173bbd1","name":"Bastian Grein","image":{"@type":"ImageObject","inLanguage":"en-GB","@id":"https:\/\/secure.gravatar.com\/avatar\/63a51f72e38efaeedcea218995ed9a9d7cc599114900902bd6dceba42b9fd583?s=96&d=mm&r=g","url":"https:\/\/secure.gravatar.com\/avatar\/63a51f72e38efaeedcea218995ed9a9d7cc599114900902bd6dceba42b9fd583?s=96&d=mm&r=g","contentUrl":"https:\/\/secure.gravatar.com\/avatar\/63a51f72e38efaeedcea218995ed9a9d7cc599114900902bd6dceba42b9fd583?s=96&d=mm&r=g","caption":"Bastian Grein"}}]}},"_links":{"self":[{"href":"https:\/\/gts-systems.com\/en\/wp-json\/wp\/v2\/posts\/6679","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/gts-systems.com\/en\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/gts-systems.com\/en\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/gts-systems.com\/en\/wp-json\/wp\/v2\/users\/5"}],"replies":[{"embeddable":true,"href":"https:\/\/gts-systems.com\/en\/wp-json\/wp\/v2\/comments?post=6679"}],"version-history":[{"count":0,"href":"https:\/\/gts-systems.com\/en\/wp-json\/wp\/v2\/posts\/6679\/revisions"}],"wp:attachment":[{"href":"https:\/\/gts-systems.com\/en\/wp-json\/wp\/v2\/media?parent=6679"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/gts-systems.com\/en\/wp-json\/wp\/v2\/categories?post=6679"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/gts-systems.com\/en\/wp-json\/wp\/v2\/tags?post=6679"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}