＜ナーススケジューリング問題は終わっていない＞
実世界のインスタンスで、Reasonableな時間内に厳密解を示せることが最終目標ですが、未だ道半ばという認識です。
スケジュールナースが殆どのベンチマークテストで、厳密解を示してきたのに対して、実務インスタンスでは、そうなっていないのは、ペア制約の有無にあります。
ベンチマークテスト→ペア制約がない
実務インスタンス→ペア制約の記述がある。感覚的には、5割以上のプロジェクトで記述がある
＜アルゴリズムの要因＞
Defaultのアルゴリズムでも、厳密解を出せる場合があります。UB=0のときは、いうまでもなく厳密解です。そしてエラーの数が数個レベル以下のときも、厳密解を出せる場合もあります。しかし、その場面は、多くはなく、大抵の場合、ソフトタイムアウトを待って処理終了となるでしょう。タイムアウトを待って処理終了としているので、厳密解ではありません。Defaultアルゴリズムが厳密解を出せるのは、限られているということです。Defaultアルゴリズムが、得意なのは、AND,OR,NOT等のboolean operationです。数を数えることも出来ますが、それは、コンピュータが数を数えるのと同じ原理で数を数えるしかありません。数を数えるのは、得意ではありません。最も困難なのは、掛け算です。定数との掛け算も容易ではありません。
＜数理ソルバ＞
エラーが多いときは、数理ソルバに利があります。そこで、アルゴリズム3,4の登場となります。数理ソルバは、線形ソルバを基礎にしています。線形ソルバが出来るのは、定数ｘ変数と、変数同士の足し算(引き算)のみです。変数同士の掛け算は、出来ません。
＜線形ソルバは、And OR演算は不得意＞
一般的には、AND OR オペレーションは、線形的ではありません。なので、AND/ORで表現される ペア制約は、相性がよくありません。
実インスタンスで数理ソルバの厳密解を阻んでいる要因は、ペア制約にあります。ペア制約は、「禁止」と「AならばB」の二つがありますが、問題は、「AならばB」にあります。
逆に言えば、ペア制約の「AならばB」を使っていないプロジェクトでは、アルゴリズム4で、かなりのインスタンスが厳密解を出せると思います。
また、ペア制約があるプロジェクトでもペア制約のチェックを外せば、かなりのプロジェクトが厳密解を出せる筈です。(全部ではありません。整数最適化アプローチへの入門 (ieice.org)のように、小さくても難しい問題は存在します。）
つまり、実インスタンスでスケジュールナースの厳密解を阻んでいる主因は、ペア制約にあります。
＜なぜペア禁止は、阻害要因とならないか？＞
ペア禁止は、列制約に書き換え可能です。ペア禁止したい集合があったとして、その集合内で、ペア禁止は、二つの同じシフトが無いことなので
ΣX[p][day][shift]<=1
と制約すれば、禁止とすることが出来ます。つまり線形和で表現できます。
＜列制約は、線形和である＞
列制約の表現は、全て線形和で表現できます。禁止にしろ強制にしろ、
Σa[i]X[i] =b[lower:upper]
という線形和形式で表現できます。
＜AならばBは、線形には表現できない＞
ここで、ペア禁止に戻ると、AならばBは、単純な線形和では表現できません。
つまり、線形和で表現出来ない部分が、複雑にしているとも言えます。この複雑にしている部分を、線形和で表現するというモデリング変更を行えば、普通の線形演算のみで構成することが出来ます。
＜モデリングを線形和形式に変更する＞
そこで、ペア制約も線形和形式でモデリングすることを考えます。この辺の話は、Integer Programming と呼ばれ、アカデミックのようでいて、ノウハウのようでもあり、不思議なトリックの世界です。全てを線形トリックに変換できるとは思わないのですが、考え方変更で、かなりの部分を線形和形式にすることができます。で、線形和形式に全てできたときに、厳密解を得る公算がかなり高まります。
＜まとめ＞
■ソフトエラーが多数のとき、数理ソルバに利がある
■数理ソルバは、線形ソルバを基礎に置く。線形オペレーションが得意
■列制約は、線形である
■ペア制約も、線形にモデリングすることによって、不得意部を無くす⇒得意演算のみに出来る
■ペア制約を入れ込んだベンチマークにすべき。⇒アカデミック領域で、ベンチマークテスト開発、提案
0 件のコメント:
コメントを投稿