分野別セミナー

最新の汎用整数計画ソルバは，最も複雑なソフトウェアの一つである．計算複雑性理論の観点からは，解く問題はNP困難であるにも関わらず，現実的な時間内で実用的な問題が扱えるようになってきている．線形計画ソルバを利用した分枝カット法で問題は解かれるが，それぞれのアルゴリズム構成要素はヒューリスティックな実装であり，それぞれが多くのパラメタを持つ．このため，新たなアルゴリズムの追加や，あるヒューリスティックのパラメタの変更が，全体の性能へ与える影響を正確に把握することも困難である．加えて，ソルバの性能評価方法も確立されているわけではなく，どのような評価方法を用いても，解く問題のデータセットによって評価は変わる．このような状態にも関わらず，整数計画ソルバは，実感として性能が向上していると受け入れられている．本講演では，整数計画ソルバ開発の現状を紹介するとともに，その性能評価について議論する．また，並列分枝限定法ソルバの性能評価についても議論する．