最適化楽屋話#18 Benders分解の概要

Numerical Optimizer 開発責任者の田辺隆人でございます。

Numerical Optimizer のオンラインセミナー（Webinar）は幸いご好評をいただいており、日程を増やして実施しております。詳しくはこちらをご参照ください。

車両スケジューリングや訪問スケジューリングの問題には「エージェント（車両や人）を訪問先に割り当てる」という決定と「（割り当てられた訪問先に対する）各エージェントの訪問時刻を決める」という二つの決定が含まれていて、全体の構造は「訪問先に割り当てる」問題が上位の層にあって、その答を基に「訪問時刻を決める」問題が下位の層にある、と見立てることができます。

解く側の事情を言うと「割り当てる」問題と「訪問時刻を決める」問題は適したアルゴリズムがかなり異なるので、できることなら別々に扱いたいのですが、この階層構造のためにそうできないのが困ったところ。こんな構造の問題を扱う時に役立つ手法の一つがBenders分解と呼ばれる手法です。

上位層の問題の答え $y$（例えばエージェントに対する訪問先の割り当て）を与えると、この $y$ を入力として下位層の最適な目的関数値を教えてくれる関数 $F(y)$ を定義してしまいます。もちろん $F(y)$ を出力するには与えられた $y$ に対して、下位層の問題を解いて $x$（例えば各エージェントの訪問時刻）を決定する必要があるのですが、その目的関数の最適値を形式的に $F(y)$ と置いてしまうわけです。下位層の問題の $F$ に与える $y$ の筋が悪いと不幸にして下位層の問題が実行不可能になってしまうのですが、そういうときには $F(y)$ が極端な値（全体が最小化問題の場合には無限大）になる、という風に定義しておきます。

この $F(y)$ は下位層の問題のレスポンスを表現している関数、とでも解釈できますが、形式的には $F(y)$ を使えば、問題全体が上位層の問題の変数 $y$ のみで書けてしまいます（下位層の問題を解く、という所作が $F(y)$ に押し込められてしまっていますので、見掛け上、下位層の変数 $x$ は表面に現れなくなる）。

$F(y)$ はかなり複雑な構造をしていて正確には近似することはできない。ただ、$y$ の一次式（Bendersカット）の集合で、逐次的に近似してゆくことならできることが知られています。この事実を使って、効率的に全体を解こうとするのがBenders分解という手法です。$F(y)$ を求めることが線形計画問題を解くことに帰着されるのが古典的なケース（$F(y)$ を求めるときに用いる $x$ の問題の双対問題を考えて $y$ を $x$ の問題の目的関数に追いやってしまうのが常套手段）ですが、前回紹介した訪問介護問題に関する論文では $F(y)$ が離散計画問題を解いて定義されるようなより一般的なケースに拡張されたBenders分解（Logic-Based Benders Decomposition）を用いています。

人に対する訪問先の割り当てを上位層、割り当てられた訪問先の訪問時刻の決定を下位層としてモデル化し、上位層の問題には汎用MILPソルバー、下位層の問題には制約充足問題ソルバーをそれぞれ用いて、訪問先60個程度の実際規模の訪問スケジューリング問題について、訪問先の一部を入れ替えてリスケジュールを繰り返す設定で厳密解を数分で導くことができると報告されています。

上位層の問題に対する暫定解（制約は満たすが最適性は証明できない答）が現れるたびに制約充足問題ソルバーで下位層の問題を解いて、その結果から上位層の問題（に含まれている $F(y)$ の表現）を改善する、ということを繰り返すのですが、あまり質が良くなくても上位層の問題の暫定解を沢山出して下位層の問題からのフィードバックを沢山得る方が全体にとっては高速になるのだそうです。こういった実装上の知見も豊富で実に参考になります。