2019年7月15日月曜日

SC3のメインソルバ解説



SC3は、複数のソルバを搭載していますが、基本的には、defaultソルバのみ(アルゴリズム1)を使ってください。
アルゴリズム1は、旧来ソルバ(アルゴリズム0)と同じ種類の、改良Versionになっています。

右のペインは、SchedulingBenchmarkサイトのInstance1の問題を解いたところです。
充足解を書き込み中での前の数値が目的関数値となります。

目的関数値は、OR用語で、最適化問題における最適値となります。Status Optimumが出ているので、厳密解が607 ということが分かります。これは、SchedulingBenchmarkサイトにあるKnown
Best Valueという値と一致しています。

従来のレベルに関しては、同じ扱いです。そこに重みが紐付けされていることになります。
607ということは、恐らく重み100であるレベル7のエラーが6個、重み1,2,3のエラーが数個足して7という具合になっていると思われます。

各レベルの重みをW(i)、エラー個数をE(i)としたとき、目的関数値は、リニア加算で求められ

ObjectiveValue=ΣW(i)*E(i)

という具合に表現されます。 これは、あくまでモデリングの話であって、現実の良し悪しは、Logとか2乗とか、非線形にした方が、感覚的に近いということはあるかもしれません。が、そうなると
解くのも難しくなるので、MIP問題では、線形加算で求めるのが一般的です。

それはともかく、目的関数値0が、理想的であることは、依存ないでしょう。そして、目的関数値が小さければ小さいほど、より良い勤務表のアサイン という風になるように、感覚的な重みを
選ぶことは、ユーザの仕事になります。理想からの偏差をコストとして捉えコスト最小問題として考えるとしっくりするのではないかと思います。

重みを大きくすれば、優先度が高くなります。上の例で、100というのは、ハード制約的な意味合いを持たせているだと思います。ソルバにとって、重み100(レベル7)の1個のエラーは、重み1(レベル1)100個のエラーと同じ重みとなります。

<従来ソルバとの対比>
レベルが、1-2種だとさほど感じませんが、レベルが多く時間がかかる複雑な問題では、末端レベルで悲惨な状況になりがちでした。そのような場合は、重みで表現すれば、調整がしやすくなるのではないかと思います。

また、途中で求解を打ち切る場合でもそれなりの解になっていることが
多いのではないかと思います。

トータルの数値として出てくるので、勤務表の良し悪しを目的関数数値で比喩しやすくなる、という事が言えます。また、ソルバの評価にしても、同じ問題なら、少ない目的関数値を出力した方が優秀ということが言えます。

<アルゴリズム1のソルバとアルゴリズム0(旧来)のソルバでの比較は、どうか?>
という質問には、やってみてくださいとしか言えません。

インスタンス(問題)毎で違います。
劇的に速くいく場合もあるし、却って時間がかかる場合もあります。一般には、ソフト制約が多い場合は、アルゴリズム1が強く、少ない場合(2種以下)では、アルゴリズム0が良い場合もある、という感じです。

<CPU数>
アルゴリズム0は、CPUを複数使えますが、その他のアルゴリズムは、CPUを一つしか使いません。これは、前に述べたUlitimate構想によるものです。(Ulitimate機能の実装は、来年以降でしょう。)







0 件のコメント:

コメントを投稿