Branch-and-bound

ウィキペディア

分枝限定法

出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2020/12/10 08:34 UTC 版)

分枝限定法（ぶんしげんていほう、英: branch and bound, BB）は、各種最適化問題（特に離散最適化と組合せ最適化）の最適解を求める汎用アルゴリズムである。分枝操作（英: branching operation）と限定操作（英: bounding operation）から構成される。全ての解候補を体系的に列挙するもので、最適化された量の上限と下限の概算を使って、最適でない候補は「ひとまとめに」捨てられる。

1960年、A. H. Land と A. G. Doig が線型計画法の手法として最初に提案した。

概要

関数 ${\displaystyle f(x)}$

Optimization computes maxima and minima.

非線形(制約付き)

一般	バリア関数 ペナルティ関数法（英語版）
微分可能	ラグランジュの未定乗数法 逐次二次計画法 連続線形計画（英語版）

凸最適化

凸縮小化	切除平面法（英語版、デンマーク語版、ドイツ語版、スペイン語版） 簡約勾配法 劣勾配法（英語版）
線型 および 二次	内点法 カチヤン楕円体法 カーマーカーの投影アルゴリズム ベイズ-交換 単体法 改訂シンプレックス法（英語版） 十字法（英語版） レムケの主ピボット操作法（英語版）

組合せ最適化

系列範例 (Paradigms)	近似アルゴリズム 動的計画法 貪欲法 整数計画問題(分枝限定法 若しくは 切断)
グラフ理論	最小全域木 ベルマン–フォード法 ブルーフカ法 ダイクストラ法 ワーシャル–フロイド法 ジョンソン法（英語版） クラスカル法 最大フロー問題 Dinic法（英語版） エドモンズ・カープ フォード・ファルカーソン プッシュリラベル最大流アルゴリズム（英語版）

メタヒューリスティクス

• 進化的アルゴリズム（進化戦略）
• 山登り法
• 局所探索法
• 焼きなまし法
• タブーサーチ
• ベイスンホッピング法

• カテゴリ（最適化 • アルゴリズム） • ソフトウェア（英語版）