分岐切除法
読み方：ぶんきせつじょほう
【英】：branch and cut method
【英】：branch and cut method
分枝切除法ともいう. 分枝限定法において, (最小化問題の場合)下界値を改善するための手法の1つで, 各部分問題の緩和問題を解く際に, 切除平面法を組み込む方法. 下界値の改善によって無駄な列挙を大幅に省くことができるが, 組み込む制約が増えると緩和問題を解く労力も増加する. それらのトレードオフの調整が, 全体の効率を左右する鍵となる. 多くの組合せ最適化問題において大規模な例題を解くことに成功しており, 実用的な手法としても高い評価を得ている.
分岐限定法
読み方：ぶんきげんていほう
【英】：branch and cut method
【英】：branch and cut method
分枝限定法ともいう. 組合せ最適化問題を厳密に解くために開発された列挙法の一種. 実行可能領域を分割するという操作を反復することによって 部分問題を生成し(分枝操作), 最適値の上下界値の情報を用いて 最適解の出現する見込みのない部分問題を省く(限定操作)ことで, 組合せ的爆発を克服する. ナップサック問題や巡回セールスマン問題など多くの組合せ最適化問題に対し, 実用性の高い厳密解法として広く用いられている.
分枝カット法
読み方：ぶんしかっとほう
【英】：branch and cut method
【英】：branch and cut method
分枝切除法ともいう. 分枝限定法において, (最小化問題の場合)下界値を改善するための手法の1つで, 各部分問題の緩和問題を解く際に, 切除平面法を組み込む方法. 下界値の改善によって無駄な列挙を大幅に省くことができるが, 組み込む制約が増えると緩和問題を解く労力も増加する. それらのトレードオフの調整が, 全体の効率を左右する鍵となる. 多くの組合せ最適化問題において大規模な例題を解くことに成功しており, 実用的な手法としても高い評価を得ている.
分枝切除法
このページでは「OR事典」からbranch and cut methodを検索した結果を表示しています。
Weblioに収録されているすべての辞書からbranch and cut methodを検索する場合は、下記のリンクをクリックしてください。
全ての辞書からbranch and cut method
を検索
Weblioに収録されているすべての辞書からbranch and cut methodを検索する場合は、下記のリンクをクリックしてください。
全ての辞書からbranch and cut method
を検索
- branch and cut methodのページへのリンク
