Branch and bound (BB) is a general algorithm for finding optimal solutions of various optimization problems, especially in discrete and combinatorial optimization. It consists of a systematic enumeration of all candidate solutions, where large subsets of fruitless candidates are discarded en masse, by using upper and lower estimated bounds of the quantity being optimized. The method was first proposed by A. H. Land and A. G. Doig in 1960 for linear programming.

PropertyValue
dbpprop:abstract
  • Branch and bound (BB) is a general algorithm for finding optimal solutions of various optimization problems, especially in discrete and combinatorial optimization. It consists of a systematic enumeration of all candidate solutions, where large subsets of fruitless candidates are discarded en masse, by using upper and lower estimated bounds of the quantity being optimized. The method was first proposed by A. H. Land and A. G. Doig in 1960 for linear programming.
  • Branch-and-Bound (Verzweigung und Schranke) 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.
  • El famós joc del Sudoku consisteix en omplir un quadre de 9x9 cel·les organtizades en 9 subgrups de 3x3 cel·les, amb nombres de l'1 al 9, atenint-se a la restricció que no es pot repetir el mateix nombre en la mateixa fila, columna o subgrup de 9. Un Sudoku disposa de diverses cel·les amb un valor inicial, de manera que hem de començar a resoldre el problema a partir d'aquesta solució parcial sense modificar cap de les cel·les inicials.
  • Metoda větví a mezí (angl. Branch and bound - BB) je obecný algoritmus v lineárním programování pro hledání optimálních řešení různých optimalizačních problémů, zvláště v diskrétní optimalizaci a kombinatorické optimalizaci. Princip metody je v systematickém procházení všech potenciálních řešení, přičemž velké podmnožiny nevhodných kandidátů jsou vyloučeny najednou. Přitom se využívá horní a dolní odhad hodnoty, která se optimalizuje. Metodu poprvé navrhli A. H. Land a A. G. Doig v roku 1960 pro lineární programování.
  • 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 nos lleva 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.
  • Un algorithme par séparation et évaluation, également appelé selon le terme anglo-saxon branch and bound, est une méthode générique de résolution de problèmes d'optimisation, et plus particulièrement d'optimisation combinatoire ou discrète. C'est une méthode d'énumération implicite : toutes les solutions possibles du problème peuvent être énumérées mais, l'analyse des propriétés du problème permet d'éviter l'énumération de larges classes de mauvaises solutions. Dans un bon algorithme par séparation et évaluation, seules les solutions potentiellement bonnes sont donc énumérées. 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 dédié aux problèmes de recherche opérationnelle.
  • Il Branch and Bound è una tecnica generale per la risoluzione di problemi di ottimizzazione combinatoria (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. 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à.
  • 分枝限定法（英: branch and bound、BB）とは、各種最適化問題（特に離散最適化と組合せ最適化）の最適解を求める汎用アルゴリズムである。全ての解候補を体系的に列挙するもので、最適化された量の上限と下限の概算を使って、最適でない候補は「ひとまとめに」捨てられる。 1960年、A. H. Land と A. G. Doig が線形計画法の手法として最初に提案した。
  • Метод ветвей и границ — общий алгоритмический метод для нахождения оптимальных решений различных задач оптимизации, особенно дискретной и комбинаторной оптимизации. По существу, метод является вариацией полного перебора с отсевом подмножеств допустимых решений, заведомо не содержащих оптимальных решений. Метод ветвей и границ был впервые предложен Ленд и Дойг в 1960 г. для решения задач целочисленного программирования.
dbpprop:hasPhotoCollection
rdfs:comment
  • Branch and bound (BB) is a general algorithm for finding optimal solutions of various optimization problems, especially in discrete and combinatorial optimization. It consists of a systematic enumeration of all candidate solutions, where large subsets of fruitless candidates are discarded en masse, by using upper and lower estimated bounds of the quantity being optimized. The method was first proposed by A. H. Land and A. G. Doig in 1960 for linear programming.
  • Branch-and-Bound (Verzweigung und Schranke) 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.
  • El famós joc del Sudoku consisteix en omplir un quadre de 9x9 cel·les organtizades en 9 subgrups de 3x3 cel·les, amb nombres de l'1 al 9, atenint-se a la restricció que no es pot repetir el mateix nombre en la mateixa fila, columna o subgrup de 9. Un Sudoku disposa de diverses cel·les amb un valor inicial, de manera que hem de començar a resoldre el problema a partir d'aquesta solució parcial sense modificar cap de les cel·les inicials.
  • Metoda větví a mezí (angl. Branch and bound - BB) je obecný algoritmus v lineárním programování pro hledání optimálních řešení různých optimalizačních problémů, zvláště v diskrétní optimalizaci a kombinatorické optimalizaci. Princip metody je v systematickém procházení všech potenciálních řešení, přičemž velké podmnožiny nevhodných kandidátů jsou vyloučeny najednou. Přitom se využívá horní a dolní odhad hodnoty, která se optimalizuje.
  • 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 nos lleva a una posible solución posterior a la actual.
  • Un algorithme par séparation et évaluation, également appelé selon le terme anglo-saxon branch and bound, est une méthode générique de résolution de problèmes d'optimisation, et plus particulièrement d'optimisation combinatoire ou discrète. C'est une méthode d'énumération implicite : toutes les solutions possibles du problème peuvent être énumérées mais, l'analyse des propriétés du problème permet d'éviter l'énumération de larges classes de mauvaises solutions.
  • Il Branch and Bound è una tecnica generale per la risoluzione di problemi di ottimizzazione combinatoria (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.
  • 分枝限定法（英: branch and bound、BB）とは、各種最適化問題（特に離散最適化と組合せ最適化）の最適解を求める汎用アルゴリズムである。全ての解候補を体系的に列挙するもので、最適化された量の上限と下限の概算を使って、最適でない候補は「ひとまとめに」捨てられる。 1960年、A. H. Land と A. G. Doig が線形計画法の手法として最初に提案した。
  • Метод ветвей и границ — общий алгоритмический метод для нахождения оптимальных решений различных задач оптимизации, особенно дискретной и комбинаторной оптимизации.
rdfs:label
  • Branch and bound
  • Branch-and-Bound
  • Sudoku ramificació i poda
  • Metoda větví a mezí
  • Ramificación y poda
  • Séparation et évaluation
  • Branch and bound
  • 分枝限定法
  • Метод ветвей и границ
owl:sameAs
skos:subject
foaf:page
is dbpprop:redirect of