新しいAlgorithm1のアーキテクチャ

 従来のAlgorithm1のアーキテクチャは、パラレルSATソルバです。ポートフォリオと呼ばれる形態を取っています。これは、同一の問題を異なるパラメータで解く方式です。この方式の問題は、

■決定的にならないこと

■大して高速化しない。良い場合もあるが、シングルスレッドの方が良い場合もある

内部のソルバ間は、学習節を交換しながら進みます。マルチスレッドであっても、基本的にアルゴリズムは、一つです。つまり多様性に乏しく、実使用時の様々な問題に対して常に最適なアルゴリズムであるとは言い切れない、という問題がありました。

そこで新しいアーキテクチャは、次のようにします。複数のアルゴリズムを並列に走らせます。問題の形態によっては、得意なアルゴリズムは変わってきます。複数のアルゴリズムを一機に走らせます。アルゴリズムを選びません。どの問題に対して、どいうアルゴリズムが親和性があるか？判定するのも時間がかかってしまうからです。アルゴリズム間では、情報を交換しません。先に着いた者勝ちという、単純な構想です。

懸念としては、駆動インスタンス分のメモリがどうしても必要になります。キャッシュヒット率が下がり、シングルスレッドよりも遅くなることが考えられます。この傾向は、規模が大きければ大きい程顕著になります。

これによる効果としては、

■安定度が高い。プロジェクトが決定的になる確率が高い

■求解速度向上

デメリットとして

■解は、一つのみ

■原因解析機構は、後回し

■リニア解の最適値には、必ずしも合致しない（準最適解）

■環境によっては、遅くなる懸念（メモリキャッシュ問題）

なので、Algorithm5として実験的に実装する予定です。Algorithm1は、そのままとします。

目標は、

１）解を決定的にする

２）ICU70人問題の求解時間6分を2分以下にする

３）SchedulingBenchmarksの記録更新

４）INRC2の記録更新

にありますが、これにより１）２）について、ほぼ達成見込みとなりました。

実使用時の改善となります。しかし、本題の３）４）の改善には、全く寄与しません。

学術問題のベンチマークと実使用時の問題とでは、問題の性質が全く異なるからです。言い換えるならば、Algorithm1/5は、実使用時の問題用、ということです。

学術問題には、学術問題用のアプローチが必要であり、Algorithm5では歯が立ちません。

しかしながら、そこも含めて改善しておかないと、記録更新に到底届くものではありません。今回の改善もそのために必要なステップです。

SATヒューリスティクスの歴史

 長い間、VSIDSというスコアリングが主流でした。その後MapleSATでLRB、その実用形態としてCHBが提案されました。KISSATではCHBは実装されず、またCryptiminisatでも廃止に至ってまたVSIDSに回帰しています。しかし、その後、MABとして、ダイナミックに切り替える方法が提案されて現在に至ります。

ConstraintSolving[2]SATSolvingBasisAndCDCLpdf (ios.ac.cn)

アルゴリズム１系も見直すにあたり、ヒューリスティクス系も見直すことにしました。

SAT　Solverを牽引してきたのは、フライブルク大学のArmin Biere教授です。

paper6.pdf (ceur-ws.org)

MiniSAT以来、色々提案はされていますが、Kissat以降目立った向上はありません。

最近気になった論文

 CadiCaLというSATソルバの実装を見ていて、面白いインタフェースを備えていることに気づきました。案の定、SMTソルバcvc5の実装で使われているようです。

IPASIR-UP: User Propagators for CDCL - YouTube

これは、従来のスタンドアロン的な使い方に留まらず、可能性が広がることを意味しています。安直に思いつくのは、B&B(Branch and Bound)　と併用することです。その他にも可能性があり、今後の一研究領域になると確信します。

2番目の論文は、既出ですが、改めて見てみました。5%の改善ならば、最近のSAT Competitionでも優勝候補になると思います。

[2110.14053] NeuroBack: Improving CDCL SAT Solving using Graph Neural Networks (arxiv.org)

最近、NPU搭載のCPUが出始めており、例えば、そのプロジェクトに特化した学習をオフラインで行うことが将来可能になる、というです。個別プロジェクト毎に性能向上の可能性があるということです。

しかし、上記手段を用いても速度向上は、数％のオーダでしょう。速度向上を体感できるには、2倍以上が必要と考えます。その意味で、重要なのはアルゴリズムです。新しいアーキテクチャでは、速度向上が体感できると思います。

Q.勤務表作成サービスを利用したいのですが..

 Q.契約とか無くて大丈夫なのでしょうか？

Ans.

プロジェクト作成サービスは、無料で始められます。

仕様を上手く文章で表現できなくとも、ZOOMで会話しながら、始めることが可能です。

スケジュールナースが出した答えをExcelで確認して頂きながら、ステップアップしていきます。ある程度、基本的なところが出来たことが確認できたのならば、発注して頂きます。それまでは、一切料金はかかりません。

発注後は、プロジェクトファイルが届くので、細かな仕様の実装を行います。細かな点についてお聞きしながら進めていきます。

＜進め方＞

１）ルール.txt の改定（菅原システムズ、お客さま）

２）プロジェクトファイル作成のためのExcelFormatシートの書き出し(お客さま、詳細は、そのときに説明します。）

３）１）２）に基づいたプロジェクトファイル作成(菅原システムズ)　Ｅｘｃｅｌ解提出(ｘ月解)

４）Ｅｘｃｅｌ解検証、１）２）追加・修正(お客さま）

１）～４）を基本的に使えそう、となるまで繰り返します。通常数回程度ループします。この段階では、一切料金は発生しません。

ＯＫとなったら発注ください。

プロジェクトファイル作成サービスは、2種類あり、

A）3カ月サポート（税込み3万3千円、ソフトは別途サブスクをマイクロソフトストアで購入する必要があります)

B）1年サポート(税込み11万円、買い切りソフト込み)

https://www.nurse-scheduling-software.com/japanese/service2/onetime_purchase/

があります。現時点で決定する必要はありません。しかし、サブスクは、クレジットカード購入の一択しかありませんので、国公立病院の場合、２）となってしまうと思います。

５）発注後、プロジェクトファイルを送付します。使い方等、ZOOMでお教えします。また、サポート期間内で、細かな仕様追加・修正等を承ります。

６）サポート期間終了後は、一般ユーザと同様となります。(ご質問に対する回答をメールで行います)

チュートリアル後に、注意するべきこと

スケジュールナースビギナが注意するべきことを、まとめました。

１）ファイル→ダブルクリックでプロジェクトファイルを開かない

２）制約の変更・集合定義の変更は、ブランク予定で行う。ブランク予定以上にUBが良くなることは決してありません。ブランク予定時は、UB=0をできるだけ維持するように心がけてください。

３）設定・制約の変更をしたら、即求解、動作確認を一つづつ行う。一つ変更一つ求解確認が原則です。高速ソルバたる必要と所以がここにあります。

４）解がないときに、解を見ても意味はありません。解がない原因は、ハード制約間の矛盾です。エラーメッセージを冷静に見て、今起きている矛盾を取り除いてください。今、起きていることを冷静に分析・推理することが重要です。エラーメッセージがヒントの全てです。

５）制約の確認は、マウスホイールボタン、Day集合・スタッフ集合により行う

６）スタッフプロパティシートは制約ではありません。集合の定義です。一方スタッフ毎のシフトは、制約です。しかも前月を含む全体に対するハード制約になります。

Q.介護スタッフ専用の「A勤務」（まれに看護が入ることもある）が看護職に連続で入ったりする..

 Ans.

スタッフ定義のスタッフプロパティシートは、集合の定義です。制約ではありません。

制約ではないので、書いたとしても何の作用も引き起こしません。そこで、グループ集合で

否定集合を作り、

否定した集合に対して制約して、初めて意味を持ちます。

一方、スタッフ毎のシフトは、全期間に作用するハード制約です。

ハード制約なので、チェックされてない人のシフトは、絶対に割り当てられることはないです。スタッフ毎のシフトは、将来も変わることのない勤務に使い、月々で変わる勤務には、スタッフプロパティシートによる記述をお勧めしています。このハード制約は、全区間に作用します。チェックを変更すると、それ故先月部にハードエラーを引き起こします。そのために、先月部に矛盾があったときは、先月部をソフト制約にして逃げるオプションにチェックを入れておきましょう。こうしておくと、先月部でハードエラーとなることはありません。レベル１のソフトエラーとなります。

この違いを理解して適切に制約してください。

Q.同じプロジェクトファイルに対して複数のスケジュールナース...

 が出ています。どうしたらよいでしょう？

Ans.

いいえにしてください。名前を付けて保存をして、名前のバージョンを例えば、ver9→ver10という風に、別名にて保存することをお勧めします。

恐らく.nurse3の拡張子の同じファイルをダブルクリックして起動しているのだと思います。スケジュールナースのアイコンをクリックすると、次のように複数起動していることが分かります。これが原因です。

「ファイル」→「プロジェクトファイルを開く」でプロジェクトファイルを開いた方が間違いなく操作できると思います。