Branch and bound (original) (raw)

About DBpedia

Branch-and-Bound (engl. für Verzweigung und Schranke oder Verzweigen und begrenzen) ist eine im Bereich Operations Research häufig verwendete mathematische Methode, deren Ziel darin besteht, für ein gegebenes ganzzahliges Optimierungsproblem eine beste Lösung zu finden. Branch-and-Bound führt auf einen Entscheidungsbaum, ist selbst aber kein spezielles Verfahren, sondern eine Behandlungsmethode, ein Meta-Verfahren. Für konkrete kombinatorische Optimierungsprobleme ergeben sich dementsprechend angepasste Branch-and-Bound-Algorithmen.

thumbnail

Property Value
dbo:abstract Jako metoda větví a mezí nebo též metoda větví a hranic či B&B, anglicky branch and bound se označuje typ algoritmů v a , které při prohledávání stavového prostoru postupují, jako by se jednalo o strom; pro jednotlivé větve reprezentující části prostoru možných řešení odhadují horní a spodní meze cílové funkce, a vylučují větve, ve kterých se na základě těchto odhadů nemůže vyskytovat optimální řešení. Metoda se používá i pro nekonvexní spojitou optimalizace bez omezení. Metoda je implementována například v programu BARON ([1]). Metoda hledá vždy globální řešení optimalizačního problému. Metodu poprvé navrhly a v roce 1960 pro lineární programování. Typickou úlohou, kde se využívá, je problém batohu. (cs) Branch and bound (BB, B&B, or BnB) is an algorithm design paradigm for discrete and combinatorial optimization problems, as well as mathematical optimization. A branch-and-bound algorithm consists of a systematic enumeration of candidate solutions by means of state space search: the set of candidate solutions is thought of as forming a rooted tree with the full set at the root. The algorithm explores branches of this tree, which represent subsets of the solution set. Before enumerating the candidate solutions of a branch, the branch is checked against upper and lower estimated bounds on the optimal solution, and is discarded if it cannot produce a better solution than the best one found so far by the algorithm. The algorithm depends on efficient estimation of the lower and upper bounds of regions/branches of the search space. If no bounds are available, the algorithm degenerates to an exhaustive search. The method was first proposed by Ailsa Land and Alison Doig whilst carrying out research at the London School of Economics sponsored by British Petroleum in 1960 for discrete programming, and has become the most commonly used tool for solving NP-hard optimization problems. The name "branch and bound" first occurred in the work of Little et al. on the traveling salesman problem. Branch and bound methods do not go deep like Depth-first search; the first direction is lateral movement in the tree similar to Breadth-first search (BFS). (en) Branch-and-Bound (engl. für Verzweigung und Schranke oder Verzweigen und begrenzen) ist eine im Bereich Operations Research häufig verwendete mathematische Methode, deren Ziel darin besteht, für ein gegebenes ganzzahliges Optimierungsproblem eine beste Lösung zu finden. Branch-and-Bound führt auf einen Entscheidungsbaum, ist selbst aber kein spezielles Verfahren, sondern eine Behandlungsmethode, ein Meta-Verfahren. Für konkrete kombinatorische Optimierungsprobleme ergeben sich dementsprechend angepasste Branch-and-Bound-Algorithmen. (de) El método de diseño de algoritmos ramificación y poda (también llamado ramificación y acotación) es una variante del backtracking mejorado sustancialmente. El término (del inglés, Branch and Bound) se aplica mayoritariamente para resolver cuestiones o problemas de optimización. La técnica de ramificación y poda se suele interpretar como un árbol de soluciones, donde cada rama conduce a una posible solución posterior a la actual. La característica de esta técnica con respecto a otras anteriores (y a la que debe su nombre) es que el algoritmo se encarga de detectar en qué ramificación las soluciones dadas ya no están siendo óptimas, para «podar» esa rama del árbol y no continuar malgastando recursos y procesos en casos que se alejan de la solución óptima. (es) Un algorithme par séparation et évaluation, ou branch and bound en anglais, est une méthode générique de résolution de problèmes d'optimisation combinatoire. Cet algorithme a été introduit par Ailsa Land et Alison Harcourt (Doig) en 1960. L'optimisation combinatoire consiste à trouver un point minimisant une fonction, appelée coût, dans un ensemble dénombrable. Une méthode naïve pour résoudre ce problème est d'énumérer toutes les solutions du problème, de calculer le coût pour chacune, puis de donner le minimum. Parfois, il est possible d'éviter d'énumérer des solutions dont on sait, par l'analyse des propriétés du problème, que ce sont de mauvaises solutions, c'est-à-dire des solutions qui ne peuvent pas être le minimum. La méthode séparation et évaluation est une méthode générale pour cela. Cette méthode est très utilisée pour résoudre des problèmes NP-complets, c'est-à-dire des problèmes considérés comme difficiles à résoudre efficacement. Le branch and bound est parfois comparé à une autre technique de recherche de solution, l'algorithme A*, très souvent utilisé en intelligence artificielle, alors que le branch and bound est plutôt destiné aux problèmes de recherche opérationnelle. (fr) 분기 한정법(分岐限定法, Branch and bound)은 다양한 최적화 문제를 풀기 위한 범용 알고리즘이다. 주로 나 조합 최적화 문제를 풀 때 쓴다. 분기 한정법은 모든 후보해를 체계적으로 늘어놓으면서 최적화할 수치의 상한과 하한을 추정, 가망 없다는 판정이 나는 해를 제거해 나간다. 제거하는 해에서 파생되는 해는 살펴보지 않기 때문에 불필요한 시간 소모를 줄이게 된다. 이 방법은 A. H. 랜드와 A. G. 도이그가 1960년에 선형 계획법을 풀기 위해서 제안하였다. (ko) Il branch and bound è una tecnica generale per la risoluzione di problemi di (cioè problemi con spazio di soluzioni finito) e si basa sulla scomposizione del problema originale in sottoproblemi più semplici da risolvere. Questo metodo è stato inizialmente proposto da A. H. Land e A. G. Doig nel 1960 per risolvere problemi di programmazione lineare intera. Gli algoritmi Branch and Bound sono detti di enumerazione implicita perché si comportano esattamente come un algoritmo di enumerazione -cioè "provano" tutte le soluzioni possibili fino a trovare quella ottima (o quella corretta)- ma ne scartano alcune dimostrando a priori la loro non ottimalità. (it) 分枝限定法（ぶんしげんていほう、英: branch and bound, BB）は、各種最適化問題（特にと組合せ最適化）の最適解を求める汎用アルゴリズムである。分枝操作（英: branching operation）と限定操作（英: bounding operation）から構成される。全ての解候補を体系的に列挙するもので、最適化された量の上限と下限の概算を使って、最適でない候補は「ひとまとめに」捨てられる。 1960年、A. H. Land と A. G. Doig が線型計画法の手法として最初に提案した。 (ja) O método de Ramificar e limitar (em inglês, Branch and bound) é um algoritmo para encontrar soluções ótimas para vários problemas de otimização, especialmente em otimização combinatória. Consiste em uma enumeração sistemática de todos os candidatos a solução, através da qual grandes subconjuntos de candidatos infrutíferos são descartados em massa utilizando os limites superior e inferior da quantia otimizada. O método foi proposto por A. H. Land e A. G. Doig em 1960 para . É utilizado para vários problemas NP-completos como o problema do caixeiro viajante e o problema da mochila. (pt) Метод ветвей и границ (англ. branch and bound) — общий алгоритмический метод для нахождения оптимальных решений различных задач оптимизации, особенно дискретной и комбинаторной оптимизации. Метод является развитием метода полного перебора, в отличие от последнего — с отсевом подмножеств допустимых решений, заведомо не содержащих оптимальных решений. Метод ветвей и границ впервые предложен в 1960 году Алисой Лэнд и Элисон Дойг для решения задач целочисленного программирования. Общая идея метода может быть описана на примере поиска минимума функции на множестве допустимых значений переменной . Функция и переменная могут быть произвольной природы. Для метода ветвей и границ необходимы две процедуры: ветвление и нахождение оценок (границ). Процедура ветвления состоит в разбиении множества допустимых значений переменной на подобласти (подмножества) меньших размеров. Процедуру можно рекурсивно применять к подобластям. Полученные подобласти образуют дерево, называемое деревом поиска или деревом ветвей и границ. Узлами этого дерева являются построенные подобласти (подмножества множества значений переменной ). Процедура нахождения оценок заключается в поиске верхних и нижних границ для решения задачи на подобласти допустимых значений переменной . В основе метода ветвей и границ лежит следующая идея: если нижняя граница значений функции на подобласти дерева поиска больше, чем верхняя граница на какой-либо ранее просмотренной подобласти , то может быть исключена из дальнейшего рассмотрения (правило отсева). Обычно минимальную из полученных верхних оценок записывают в глобальную переменную ; любой узел дерева поиска, нижняя граница которого больше значения , может быть исключён из дальнейшего рассмотрения. Если нижняя граница для узла дерева совпадает с верхней границей, то это значение является минимумом функции и достигается на соответствующей подобласти. Метод используется для решения некоторых NP-полных задач, в том числе задачи коммивояжёра и задачи о ранце. (ru) Метод гілок і меж (англ. Branch-and-Bound) — один з поширених методів дискретної оптимізації. Метод працює на дереві рішень та визначає принципи роботи конкретних алгоритмів пошуку розв'язків, тобто, є мета-алгоритмом. Для різних задач комбінаторної оптимізації створюють спеціалізовані алгоритми гілок та меж. Ідею методу було вперше сформульовано A.H. Land та A.G. Doig (1960) в галузі дослідження операцій. R.J. Dakin (1965) розробив простий для впровадження алгоритм. (uk) 分支定界（英語：Branch and bound，BB）是用于离散优化、组合优化以及数学优化问题的算法设计范式。分支定界算法可以视为一种对可行解进行穷举的算法，但是和穷举法所不同的是，分支定界算法在对某一分支进行检索之前会先算出该分支的上界或下界，如果界限不比目前最佳解更好，那么该分支就会被舍弃，从而节约了大量的时间。分支定界算法非常依赖合适的上界或下界，如果无法找到合适的界限，该算法将会退化为穷举法。 该方法最初是由阿尔萨·兰德和艾莉森·哈考特在1960年由英国石油公司赞助的伦敦经济学院进行离散规划研究时提出的，目前已成为解决NP困难优化问题最常用的工具。“分支定界”一词最早出现在解决旅行推销员问题的时候。 (zh)
dbo:thumbnail wiki-commons:Special:FilePath/Branch_and_Bound_opti...timate_Academic_Edition.png?width=300
dbo:wikiPageExternalLink https://projects.coin-or.org/Cbc http://sourceforge.net/projects/lipside/
dbo:wikiPageID 456580 (xsd:integer)
dbo:wikiPageLength 20091 (xsd:nonNegativeInteger)
dbo:wikiPageRevisionID 1106168616 (xsd:integer)
dbo:wikiPageWikiLink dbr:Candidate_solution dbr:Queue_(abstract_data_type) dbr:Nearest_neighbor_search dbr:Algorithm dbr:Algorithmic_paradigm dbr:Best-first_search dbr:Cutting_stock_problem dbr:Depth-first_search dbr:Integer_programming dbr:Interval_contractor dbr:Set_inversion dbr:Structured_prediction dbc:Combinatorial_optimization dbr:Mathematical_optimization dbr:Noise dbr:Branch_and_cut dbr:NP-hard dbr:Convex_hull dbr:Anonymous_function dbr:Alpha-beta_pruning dbr:London_School_of_Economics dbr:Machine_learning dbr:Callable_object dbr:Statistics dbr:Combinatorial_optimization dbr:Computational_phylogenetics dbr:Computer_vision dbr:Feasible_region dbr:Feature_selection dbr:Function_object dbr:Function_pointer dbr:Priority_queue dbr:Maximum_satisfiability_problem dbr:State_space_search dbr:BP dbr:C++ dbc:Optimization_algorithms_and_methods dbr:Travelling_salesman_problem dbr:Tree_(graph_theory) dbr:Data_structure dbr:Disjoint_sets dbr:A*_search_algorithm dbr:Ailsa_Land dbr:Alison_Harcourt dbr:Alpha–beta_pruning dbr:Flow_shop_scheduling dbr:Breadth-first_search dbr:Discrete_optimization dbr:Keinosuke_Fukunaga dbr:Probability dbr:Quadratic_assignment_problem dbr:Higher-order_function dbr:Interval_arithmetic dbr:Backtracking dbr:Talent_Scheduling dbr:Heuristic dbr:Stack_(data_structure) dbr:Dijkstra's_algorithm dbr:B* dbr:Brute-force_search dbr:Set_cover_problem dbr:Without_loss_of_generality dbr:FIFO_(computing_and_electronics) dbr:Nonlinear_programming dbr:Integer_linear_programs dbr:Set_estimation dbr:Pruning_(decision_trees) dbr:Search_tree dbr:Traveling_salesman_problem dbr:Arc_routing_problem dbr:A*_search dbr:0/1_knapsack_problem dbr:Cutting_plane dbr:File:Branch_and_Bound_optimization_exa...ricsCad_Ultimate_Academic_Edition.png
dbp:wikiPageUsesTemplate dbt:Graph_search_algorithm dbt:= dbt:Anchor dbt:Citation_needed dbt:Math dbt:Mvar dbt:R dbt:Reflist dbt:Rp dbt:Short_description dbt:Optimization_algorithms
dcterms:isPartOf http://zbw.eu/stw/mapping/dbpedia/target
dcterms:subject dbc:Combinatorial_optimization dbc:Optimization_algorithms_and_methods
gold:hypernym dbr:Paradigm
rdf:type dbo:ProgrammingLanguage
rdfs:comment Branch-and-Bound (engl. für Verzweigung und Schranke oder Verzweigen und begrenzen) ist eine im Bereich Operations Research häufig verwendete mathematische Methode, deren Ziel darin besteht, für ein gegebenes ganzzahliges Optimierungsproblem eine beste Lösung zu finden. Branch-and-Bound führt auf einen Entscheidungsbaum, ist selbst aber kein spezielles Verfahren, sondern eine Behandlungsmethode, ein Meta-Verfahren. Für konkrete kombinatorische Optimierungsprobleme ergeben sich dementsprechend angepasste Branch-and-Bound-Algorithmen. (de) 분기 한정법(分岐限定法, Branch and bound)은 다양한 최적화 문제를 풀기 위한 범용 알고리즘이다. 주로 나 조합 최적화 문제를 풀 때 쓴다. 분기 한정법은 모든 후보해를 체계적으로 늘어놓으면서 최적화할 수치의 상한과 하한을 추정, 가망 없다는 판정이 나는 해를 제거해 나간다. 제거하는 해에서 파생되는 해는 살펴보지 않기 때문에 불필요한 시간 소모를 줄이게 된다. 이 방법은 A. H. 랜드와 A. G. 도이그가 1960년에 선형 계획법을 풀기 위해서 제안하였다. (ko) 分枝限定法（ぶんしげんていほう、英: branch and bound, BB）は、各種最適化問題（特にと組合せ最適化）の最適解を求める汎用アルゴリズムである。分枝操作（英: branching operation）と限定操作（英: bounding operation）から構成される。全ての解候補を体系的に列挙するもので、最適化された量の上限と下限の概算を使って、最適でない候補は「ひとまとめに」捨てられる。 1960年、A. H. Land と A. G. Doig が線型計画法の手法として最初に提案した。 (ja) O método de Ramificar e limitar (em inglês, Branch and bound) é um algoritmo para encontrar soluções ótimas para vários problemas de otimização, especialmente em otimização combinatória. Consiste em uma enumeração sistemática de todos os candidatos a solução, através da qual grandes subconjuntos de candidatos infrutíferos são descartados em massa utilizando os limites superior e inferior da quantia otimizada. O método foi proposto por A. H. Land e A. G. Doig em 1960 para . É utilizado para vários problemas NP-completos como o problema do caixeiro viajante e o problema da mochila. (pt) Метод гілок і меж (англ. Branch-and-Bound) — один з поширених методів дискретної оптимізації. Метод працює на дереві рішень та визначає принципи роботи конкретних алгоритмів пошуку розв'язків, тобто, є мета-алгоритмом. Для різних задач комбінаторної оптимізації створюють спеціалізовані алгоритми гілок та меж. Ідею методу було вперше сформульовано A.H. Land та A.G. Doig (1960) в галузі дослідження операцій. R.J. Dakin (1965) розробив простий для впровадження алгоритм. (uk) 分支定界（英語：Branch and bound，BB）是用于离散优化、组合优化以及数学优化问题的算法设计范式。分支定界算法可以视为一种对可行解进行穷举的算法，但是和穷举法所不同的是，分支定界算法在对某一分支进行检索之前会先算出该分支的上界或下界，如果界限不比目前最佳解更好，那么该分支就会被舍弃，从而节约了大量的时间。分支定界算法非常依赖合适的上界或下界，如果无法找到合适的界限，该算法将会退化为穷举法。 该方法最初是由阿尔萨·兰德和艾莉森·哈考特在1960年由英国石油公司赞助的伦敦经济学院进行离散规划研究时提出的，目前已成为解决NP困难优化问题最常用的工具。“分支定界”一词最早出现在解决旅行推销员问题的时候。 (zh) Jako metoda větví a mezí nebo též metoda větví a hranic či B&B, anglicky branch and bound se označuje typ algoritmů v a , které při prohledávání stavového prostoru postupují, jako by se jednalo o strom; pro jednotlivé větve reprezentující části prostoru možných řešení odhadují horní a spodní meze cílové funkce, a vylučují větve, ve kterých se na základě těchto odhadů nemůže vyskytovat optimální řešení. Metoda se používá i pro nekonvexní spojitou optimalizace bez omezení. Metoda je implementována například v programu BARON ([1]). Metoda hledá vždy globální řešení optimalizačního problému. (cs) Branch and bound (BB, B&B, or BnB) is an algorithm design paradigm for discrete and combinatorial optimization problems, as well as mathematical optimization. A branch-and-bound algorithm consists of a systematic enumeration of candidate solutions by means of state space search: the set of candidate solutions is thought of as forming a rooted tree with the full set at the root. The algorithm explores branches of this tree, which represent subsets of the solution set. Before enumerating the candidate solutions of a branch, the branch is checked against upper and lower estimated bounds on the optimal solution, and is discarded if it cannot produce a better solution than the best one found so far by the algorithm. (en) El método de diseño de algoritmos ramificación y poda (también llamado ramificación y acotación) es una variante del backtracking mejorado sustancialmente. El término (del inglés, Branch and Bound) se aplica mayoritariamente para resolver cuestiones o problemas de optimización. (es) Un algorithme par séparation et évaluation, ou branch and bound en anglais, est une méthode générique de résolution de problèmes d'optimisation combinatoire. Cet algorithme a été introduit par Ailsa Land et Alison Harcourt (Doig) en 1960. Cette méthode est très utilisée pour résoudre des problèmes NP-complets, c'est-à-dire des problèmes considérés comme difficiles à résoudre efficacement. (fr) Il branch and bound è una tecnica generale per la risoluzione di problemi di (cioè problemi con spazio di soluzioni finito) e si basa sulla scomposizione del problema originale in sottoproblemi più semplici da risolvere. Questo metodo è stato inizialmente proposto da A. H. Land e A. G. Doig nel 1960 per risolvere problemi di programmazione lineare intera. (it) Метод ветвей и границ (англ. branch and bound) — общий алгоритмический метод для нахождения оптимальных решений различных задач оптимизации, особенно дискретной и комбинаторной оптимизации. Метод является развитием метода полного перебора, в отличие от последнего — с отсевом подмножеств допустимых решений, заведомо не содержащих оптимальных решений. Метод ветвей и границ впервые предложен в 1960 году Алисой Лэнд и Элисон Дойг для решения задач целочисленного программирования. Метод используется для решения некоторых NP-полных задач, в том числе задачи коммивояжёра и задачи о ранце. (ru)
rdfs:label Metoda větví a mezí (cs) Branch-and-Bound (de) Ramificación y poda (es) Branch and bound (en) Séparation et évaluation (fr) Branch and bound (it) 分枝限定法 (ja) 분기 한정법 (ko) Ramificar e limitar (pt) Метод ветвей и границ (ru) Метод гілок і меж (uk) 分支定界 (zh)
owl:sameAs freebase:Branch and bound wikidata:Branch and bound dbpedia-cs:Branch and bound dbpedia-de:Branch and bound dbpedia-es:Branch and bound dbpedia-fa:Branch and bound dbpedia-fr:Branch and bound dbpedia-hu:Branch and bound dbpedia-it:Branch and bound dbpedia-ja:Branch and bound dbpedia-ko:Branch and bound dbpedia-pt:Branch and bound dbpedia-ru:Branch and bound dbpedia-sh:Branch and bound dbpedia-sr:Branch and bound dbpedia-uk:Branch and bound dbpedia-zh:Branch and bound https://global.dbpedia.org/id/53bw3
skos:closeMatch http://zbw.eu/stw/descriptor/15488-4
prov:wasDerivedFrom wikipedia-en:Branch_and_bound?oldid=1106168616&ns=0
foaf:depiction wiki-commons:Special:FilePath/Branch_and_Bound_opti...ricsCad_Ultimate_Academic_Edition.png
foaf:isPrimaryTopicOf wikipedia-en:Branch_and_bound
is dbo:knownFor of dbr:Ailsa_Land dbr:Alison_Harcourt
is dbo:wikiPageDisambiguates of dbr:BB
is dbo:wikiPageRedirects of dbr:Branch_and_Bound dbr:Least_discrepancy_search dbr:Branch-and-bound dbr:Branch-and-bound_algorithm dbr:Branch-and-bound_technique dbr:Branch_and_bound_algorithm
is dbo:wikiPageWikiLink of dbr:B&B dbr:BB dbr:Protein_design dbr:Branch_and_Bound dbr:List_of_algorithms dbr:Nearest_neighbor_search dbr:Algorithm dbr:Algorithmic_paradigm dbr:Arc_routing dbr:Relaxation_(approximation) dbr:Cutting-plane_method dbr:Cutting_stock_problem dbr:Independent_component_analysis dbr:Integer_programming dbr:Interval_contractor dbr:Leximin_order dbr:List_of_institute_professors_at_the_Massachusetts_Institute_of_Technology dbr:Set_inversion dbr:Computational_science dbr:Chemical_graph_generator dbr:Chromatic_polynomial dbr:Clique_problem dbr:Enrique_Alba dbr:GNU_Linear_Programming_Kit dbr:Graph_coloring dbr:Branch_and_cut dbr:Branch_and_price dbr:MINTO dbr:Stack_(abstract_data_type) dbr:Combinatorial_optimization dbr:Computational_phylogenetics dbr:Feature_selection dbr:Parallel_computing dbr:Pattern_recognition dbr:Process_network_synthesis dbr:Shifting_bottleneck_heuristic dbr:State_space_search dbr:COIN-OR dbr:Travelling_salesman_problem dbr:Treewidth dbr:Dr.Fill dbr:Held–Karp_algorithm dbr:Linear_programming dbr:Linear_programming_relaxation dbr:PM2 dbr:Minimum-weight_triangulation dbr:A*_search_algorithm dbr:Ailsa_Land dbr:Alison_Harcourt dbr:Alpha–beta_pruning dbr:Eugene_Lawler dbr:FICO_Xpress dbr:Feature_Selection_Toolbox dbr:Fernandez's_method dbr:British_Museum_algorithm dbr:Flow-shop_scheduling dbr:FortMP dbr:Routing_and_wavelength_assignment dbr:Interval_arithmetic dbr:Monotone_priority_queue dbr:ChessV dbr:Symbolic_artificial_intelligence dbr:Threading_(protein_sequence) dbr:B* dbr:Point-set_registration dbr:Guillotine_cutting dbr:Search_algorithm dbr:Knapsack_problem dbr:Special_ordered_set dbr:Weapon_target_assignment_problem dbr:In_Pursuit_of_the_Traveling_Salesman dbr:List_of_terms_relating_to_algorithms_and_data_structures dbr:Nonlinear_programming dbr:Outline_of_combinatorics dbr:Least_discrepancy_search dbr:Branch-and-bound dbr:Branch-and-bound_algorithm dbr:Branch-and-bound_technique dbr:Branch_and_bound_algorithm
is foaf:primaryTopic of wikipedia-en:Branch_and_bound