整数計画問題を含むNP困難な組合せ最適化問題では,分枝限定法と切除平面法が代表的な厳密解法として知られています.
分枝限定法は,直接に解くことが難しい問題をいくつかの小規模な子問題に分割する分枝操作と,最適解が得られる見込みのない子問題を見つける限定操作の2つの操作を繰り返し適用するアルゴリズムで,整数計画問題以外にも多くの最適化問題で使われています.
切除平面法は,緩和問題の最適解から始めて,実行可能解を残しつつ緩和問題の最適解を除去する制約条件を組織的に追加する手続きを繰り返し適用するアルゴリズムです.
今回は,分枝限定法と切除平面法の考え方と手続きを説明した後に,整数計画問題を解くソフトウェアの利用法を紹介します.