分岐限定法

【ぶんきげんていほう (branch and cut method)】

分枝限定法ともいう. 組合せ最適化問題を厳密に解くために開発された列挙法の一種. 実行可能領域を分割するという操作を反復することによって 部分問題を生成し(分枝操作), 最適値の上下界値の情報を用いて 最適解の出現する見込みのない部分問題を省く(限定操作)ことで, 組合せ的爆発を克服する. ナップサック問題や巡回セールスマン問題など多くの組合せ最適化問題に対し, 実用性の高い厳密解法として広く用いられている.