English page is here.

Branch and Bound

---

列が決まったら、集合分割問題を解きますが、我々は整数計画法の標準的な解法である分枝限定法を利用しました。 これはまず何らかの形で、集合分割問題のfeasible solutionを求めます。そして変数をそれぞれ１と０に固定した場合について場合分けし（branch）、それぞれの場合について、線形緩和問題を解くことで、最適解の下限を求め(bound)、もしその下限がこれまで見つかっている解のコストよりも低い場合にのみ、さらに別の変数についての場合分けを続けていくものです。

Last modified 30 June 1998