2024年3月27日水曜日

古くて新しいヒューリスティックス

現在でも新しいヒューリスティックス開発が進められています。

中国のShaowei Cai教授は、昔から取り組んでいて、最近のSAT Competitionでは、その成果が結実し連戦連勝中です。それとは別に、触手をMIP系に広げてきたようです。FeasibilityJumpの発想の一般化ではないかと思いますが、今後注目です。

New Characterizations and Efficient Local Search for General Integer Linear Programming (arxiv.org)

Feasibility Jump: an LP-free Lagrangian MIP heuristic | Mathematical Programming Computation (springer.com)




2024年3月26日火曜日

スケジュールナースは、大規模なソフトウェアです

ナーススケジューリング問題のソルバのコア部分は、数百行でも書けます。勿論性能は別にしてです。なのでスケジュールナースもその程度の規模と思っている人がいるかもしれません。

それは、全く違います。 

スケジュールナースのエンジンは、C++で書いています。SAT系、MIP系があり自分で書いたのは、10万行以下です。さらに外部ライブラリとして、HIGHS、CLP、バリアソルバ、SATソルバに加えて、組み込みPythonがあり、GUI用に、ソースエディタscintilla、データグリッド・Excel等のSyncfusionコンポーネント、GUIソースを加えると、50万行を軽く超えると思います。

これらは、人類の知の塊です。今後も、これらフレームワーク上に新たな知見が追加されると思います。私は、組み合わせ最適化の性能向上の余地は未だある、と見ています。そして、これら最新のアカデミクスによる成果と実務管理者の実務とのギャップを埋めるのがスケジュールナースの仕事です。



2024年3月25日月曜日

アルゴリズム1の非決定性

 アルゴリズム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を時刻等で初期化することによっても非決定的になっています。


2024年3月24日日曜日

平日週1回休みの簡易実装

 補助員的な位置づけのスタッフで、平日に週一回休みが欲しい人の実装です。

真面目に制約を書いてもよいのですが、解は最終段階であり、最後の実装として上記要求の実装が残っているものとします。

1)まずは、当該スタッフの平日日勤で予定を埋めてしまいます。

2)全ての予定をロックします。

3)求解し、今月解全てを選択して予定へ送ります。

4)予定セルは、ロックされているのでそのままです。それ以外が解でFILLINされます。

5)解を参照して、当該スタッフ職種の余裕がある日を休みに予定変更します。


6)求解して最終解を得る

以上です。

制約を用いないで、解を修正することによって要求を満足させています。

よく「解の修正はできないか?」と聞かれますが、解を直接修正するのではなく、あくまで予定で修正するのがスケジュールナーススタイルです。予定は、解でFILLINされているのですが、その予定に対して制約が利くので、最終的に解が妥当であるかどうか、チェックされるところが違います。

また、この方法は、他に修正がない最終解でのみしか使えません。さほど重要でなく、制約化するのも面倒という場合に有効な手段です。

2024年3月23日土曜日

タイのナーススケジューリング

 How would you implement the following in an emergency department in Thailand, assuming that nurses with higher skill levels can also do the work of lower skill levels (nurse-scheduling-software.com)

救急での例です。論文の数値に誤りがあるとは思いますが、日本を上回る勤務形態になっています。1日のうちに、朝夕の連続シフト、もしくは、朝夜の2シフトがありえます。





2024年3月22日金曜日

イタリアのナーススケジューリング

 イタリアでもオンコールはあるようです。CALLシフトと妊婦さんのプロジェクトです。妊婦さんは、連続勤務3日、週30時間と制約しています。

I would like to implement a Call shift for the following paper in Italy (nurse-scheduling-software.com)