大域的最適化アルゴリズムとその化学相平衡問題への応用

点击翻译按钮获取中文摘要

化学プロセスで解決の求められることの多い非線形0-1型混合整数計画問題は,0-1変数を固定すれば通常の凸計画問題に帰着するものの,正しい解を求めるためには,0-1変数の数の巾乗個もの凸計画問題の中から大域的に最適な解を与えるものを見つけ出さなければならない.このため,従来は発見的に精度保障のない近似解を求めるほか術がないとされてきたが,この多極値非凸最適化問題に対して厳密な最適解を生成する分枝カットアルゴリズムを構築した.対象となる問題を凸計画問題に連続緩和したときの最適解が,その実行可能領域における,ある1次関数の最小点に一致することを明かにした.これをもとに,緩和問題の最適解を離接切除平面によって効果的に除去する方法を考案した.離接切除平面は,0-1変数で離接が生じることを利用して各0-1変数の定めるアフィン空間に子問題を射影し,これを解くことによって生成する.しかし,射影された問題は非線形計画問題であり,アルゴリズムの各反復でこれを解くことは全体として効率的でない.そこで,この問題をさらに線形計画問題に緩和し,その双対問題を用いて切除平面が子問題に対して常に妥当となるように調整を行なった.同時に,残りの0-1変数の整数性も利用し,解を与えない領域をなるべく深く除去するように切除平面の強化を行なった.以上の方法で生成される離接切除平面は,必ずしも離接集合に対する凸包のファセットとはならない.しかし,予備実験では典型的な2つの化学設計問題に対して十分な効果のあることが確認できた.