今だにrand()を使っているソースを見ると悲しくなります。
ichimura-sho-koen.pdf (hiroshima-u.ac.jp)
SIMD-oriented Fast Mersenne Twister (SFMT) (hiroshima-u.ac.jp)
今まで、メルセンヌツイスター一択だと思っていたのですが、
10年前の自分に伝えたい、たった一つの擬似乱数生成器 #乱数 - Qiita
PCGが最速のようなので、こちらを使うことにしました。
今だにrand()を使っているソースを見ると悲しくなります。
ichimura-sho-koen.pdf (hiroshima-u.ac.jp)
SIMD-oriented Fast Mersenne Twister (SFMT) (hiroshima-u.ac.jp)
今まで、メルセンヌツイスター一択だと思っていたのですが、
10年前の自分に伝えたい、たった一つの擬似乱数生成器 #乱数 - Qiita
PCGが最速のようなので、こちらを使うことにしました。
現在でも新しいヒューリスティックス開発が進められています。
中国のShaowei Cai教授は、昔から取り組んでいて、最近のSAT Competitionでは、その成果が結実し連戦連勝中です。それとは別に、触手をMIP系に広げてきたようです。FeasibilityJumpの発想の一般化ではないかと思いますが、今後注目です。
New Characterizations and Efficient Local Search for General Integer Linear Programming (arxiv.org)
ナーススケジューリング問題のソルバのコア部分は、数百行でも書けます。勿論性能は別にしてです。なのでスケジュールナースもその程度の規模と思っている人がいるかもしれません。
それは、全く違います。
スケジュールナースのエンジンは、C++で書いています。SAT系、MIP系があり自分で書いたのは、10万行以下です。さらに外部ライブラリとして、HIGHS、CLP、バリアソルバ、SATソルバに加えて、組み込みPythonがあり、GUI用に、ソースエディタscintilla、データグリッド・Excel等のSyncfusionコンポーネント、GUIソースを加えると、50万行を軽く超えると思います。
これらは、人類の知の塊です。今後も、これらフレームワーク上に新たな知見が追加されると思います。私は、組み合わせ最適化の性能向上の余地は未だある、と見ています。そして、これら最新のアカデミクスによる成果と実務管理者の実務とのギャップを埋めるのがスケジュールナースの仕事です。
アルゴリズム1は、非決定的です。非決定的というのは、複数回 求解したときに解が同じにはならないことを指します。この原因は、二つあります。
1)時間タイムアウトによる非決定性
2)マルチスレッド間での非同期性
数独みたいに、ソフト制約がないプロジェクトをCPUコア数1で駆動したときは、1)要因がないので、解は決定的に出来ます。しかし、その場合でも複数のCPUで駆動した場合は、2)の問題により解は決定的にはなりません。
この問題に対する有効な方法は、山梨大学鍋島先生によるDPSです。マルチスレッドの速度向上を阻害せずに、決定的にするのは、大変難しい問題ですが、DPSは、速度低下を最小限に収めつつ、決定的にすることが出来ます。
改めて再評価したところ安定的に動作することを確認しました。次は、そのデータです。20コアで、最速を記録していますが、このデータは、「再現性がある」ということです。逆に8コアでは、4コアよりも遅くなりますが、これも再現性があります。常にコア数を増やせば、速度が上がる訳ではないのですが、傾向としてはそうであり、そうであるならば、安定的に動作して欲しい、ということであります。
dps 10-13-s
コア数 時間 メモリ
1 289sec 120mb
2 302sec 188mb
3 69sec 249mb
4 31sec 307mb
6 34sec 455mb
8 73sec 535mb
10 46sec 704mb
12 28sec 837mb
14 105sec 923mb
16 41sec 1099mb
20 12sec 1379mb
24 37sec 1611mb
32 25sec 2173mb
現在は、アルゴリズム3,4用のアルゴリズム1の再設計を行っています。(余裕があれば、DPSの枠組みを組み込みたいと思っています。)
ちなみに、MIPソルバも含めて、99.9%のソルバは、非決定的だと思います。上の事情に加えて、ランダムSeedを時刻等で初期化することによっても非決定的になっています。
補助員的な位置づけのスタッフで、平日に週一回休みが欲しい人の実装です。
真面目に制約を書いてもよいのですが、解は最終段階であり、最後の実装として上記要求の実装が残っているものとします。
1)まずは、当該スタッフの平日日勤で予定を埋めてしまいます。
2)全ての予定をロックします。以上です。
制約を用いないで、解を修正することによって要求を満足させています。
よく「解の修正はできないか?」と聞かれますが、解を直接修正するのではなく、あくまで予定で修正するのがスケジュールナーススタイルです。予定は、解でFILLINされているのですが、その予定に対して制約が利くので、最終的に解が妥当であるかどうか、チェックされるところが違います。
また、この方法は、他に修正がない最終解でのみしか使えません。さほど重要でなく、制約化するのも面倒という場合に有効な手段です。