従来のAlgorithm1のアーキテクチャは、パラレルSATソルバです。ポートフォリオと呼ばれる形態を取っています。これは、同一の問題を異なるパラメータで解く方式です。この方式の問題は、
■決定的にならないこと
■大して高速化しない。良い場合もあるが、シングルスレッドの方が良い場合もある
従来のAlgorithm1のアーキテクチャは、パラレルSATソルバです。ポートフォリオと呼ばれる形態を取っています。これは、同一の問題を異なるパラメータで解く方式です。この方式の問題は、
■決定的にならないこと
■大して高速化しない。良い場合もあるが、シングルスレッドの方が良い場合もある
長い間、VSIDSというスコアリングが主流でした。その後MapleSATでLRB、その実用形態としてCHBが提案されました。KISSATではCHBは実装されず、またCryptiminisatでも廃止に至ってまたVSIDSに回帰しています。しかし、その後、MABとして、ダイナミックに切り替える方法が提案されて現在に至ります。
ConstraintSolving[2]SATSolvingBasisAndCDCLpdf (ios.ac.cn)
アルゴリズム1系も見直すにあたり、ヒューリスティクス系も見直すことにしました。
SAT Solverを牽引してきたのは、フライブルク大学のArmin Biere教授です。
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.契約とか無くて大丈夫なのでしょうか?
Ans.
プロジェクト作成サービスは、無料で始められます。
仕様を上手く文章で表現できなくとも、ZOOMで会話しながら、始めることが可能です。
スケジュールナースが出した答えをExcelで確認して頂きながら、ステップアップしていきます。ある程度、基本的なところが出来たことが確認できたのならば、発注して頂きます。それまでは、一切料金はかかりません。
発注後は、プロジェクトファイルが届くので、細かな仕様の実装を行います。細かな点についてお聞きしながら進めていきます。
<進め方>
1)ルール.txt の改定(菅原システムズ、お客さま)
2)プロジェクトファイル作成のためのExcelFormatシートの書き出し(お客さま、詳細は、そのときに説明します。)
3)1)2)に基づいたプロジェクトファイル作成(菅原システムズ) Excel解提出(x月解)
4)Excel解検証、1)2)追加・修正(お客さま)
1)~4)を基本的に使えそう、となるまで繰り返します。通常数回程度ループします。この段階では、一切料金は発生しません。
OKとなったら発注ください。
プロジェクトファイル作成サービスは、2種類あり、
A)3カ月サポート(税込み3万3千円、ソフトは別途サブスクをマイクロソフトストアで購入する必要があります)
B)1年サポート(税込み11万円、買い切りソフト込み)
https://www.nurse-scheduling-software.com/japanese/service2/onetime_purchase/
があります。現時点で決定する必要はありません。しかし、サブスクは、クレジットカード購入の一択しかありませんので、国公立病院の場合、2)となってしまうと思います。
5)発注後、プロジェクトファイルを送付します。使い方等、ZOOMでお教えします。また、サポート期間内で、細かな仕様追加・修正等を承ります。
6)サポート期間終了後は、一般ユーザと同様となります。(ご質問に対する回答をメールで行います)
スケジュールナースビギナが注意するべきことを、まとめました。
1)ファイル→ダブルクリックでプロジェクトファイルを開かない
2)制約の変更・集合定義の変更は、ブランク予定で行う。ブランク予定以上にUBが良くなることは決してありません。ブランク予定時は、UB=0をできるだけ維持するように心がけてください。
3)設定・制約の変更をしたら、即求解、動作確認を一つづつ行う。一つ変更一つ求解確認が原則です。高速ソルバたる必要と所以がここにあります。
4)解がないときに、解を見ても意味はありません。解がない原因は、ハード制約間の矛盾です。エラーメッセージを冷静に見て、今起きている矛盾を取り除いてください。今、起きていることを冷静に分析・推理することが重要です。エラーメッセージがヒントの全てです。
5)制約の確認は、マウスホイールボタン、Day集合・スタッフ集合により行う
6)スタッフプロパティシートは制約ではありません。集合の定義です。一方スタッフ毎のシフトは、制約です。しかも前月を含む全体に対するハード制約になります。
Ans.
スタッフ定義のスタッフプロパティシートは、集合の定義です。制約ではありません。
制約ではないので、書いたとしても何の作用も引き起こしません。そこで、グループ集合で
否定集合を作り、
一方、スタッフ毎のシフトは、全期間に作用するハード制約です。
ハード制約なので、チェックされてない人のシフトは、絶対に割り当てられることはないです。スタッフ毎のシフトは、将来も変わることのない勤務に使い、月々で変わる勤務には、スタッフプロパティシートによる記述をお勧めしています。このハード制約は、全区間に作用します。チェックを変更すると、それ故先月部にハードエラーを引き起こします。そのために、先月部に矛盾があったときは、先月部をソフト制約にして逃げるオプションにチェックを入れておきましょう。こうしておくと、先月部でハードエラーとなることはありません。レベル1のソフトエラーとなります。
この違いを理解して適切に制約してください。
が出ています。どうしたらよいでしょう?
Ans.
いいえにしてください。名前を付けて保存をして、名前のバージョンを例えば、ver9→ver10という風に、別名にて保存することをお勧めします。
恐らく.nurse3の拡張子の同じファイルをダブルクリックして起動しているのだと思います。スケジュールナースのアイコンをクリックすると、次のように複数起動していることが分かります。これが原因です。
「ファイル」→「プロジェクトファイルを開く」でプロジェクトファイルを開いた方が間違いなく操作できると思います。
Ans.
誰もその人とはペアになりたくない、という方はいらっしゃるかもしれません。大体どの病棟・施設でも、そういう方はいらっしゃいます。しかし、だからと言って誰ともペアを組ませないと、夜勤の人数は、常にその方、一人となってしまい、列制約を満足できなくなってしまいます。題意は、恐らく、そのようなスタッフと組む回数を平等にする、ということなので、その人とのペア回数を平準化することです。
例えば、その方とのペア回数を全員1回以下とする、可能ならば。ということではないかと思います。
残念ながら、この制約は、Pythonでしか記述できません。この職場の場合、男同士の夜勤は禁止、なおかつ看護師と介護各々1名ということなので、その方が介護・男である場合、あり得る組み合わせ対象は、女性・看護師に限定されることに注意します。そうなると、意外に組み合わせ範囲は、限定され、例えば、夜勤を6回、女性看護師が4人しかいない場合、
6回=1回2人 2回2人
6回=2回 3人
6回= 3回 2人
6回=3回1人 1回1人 2回1人
つまり、ペア1回の人が2人、ペア2回の人が2人という解しか、全員が負担する、という解は存在しないことになります。他の全てのでケースにおいて、負担0の方が存在し不平等がありえます。「私2回だ、不平等だ」は、4人のうちの50%、2人に発生するのは必然となることは理解しておいた方が良いと思います。別な見方をするなら、3回ペア夜勤を禁止することで、2回以下となる解が得られるようになる、ということです。また、ペア1回以下をハード制約とすると解は存在しない、ということになります。
この辺が組み合わせ最適化の難しいところです。単純なリニア制約では表現できないところが、人間的であるところだと思います。
次の求解パラーメータ、許容エラー1に注目してください。
一番下で、オーバライドにチェックが入っています。
これは、次のPythonソースで、最大ペア回数を1回に制限している部分に作用します。
Pythonソース上は、許容エラー数が3(sc3.SeqError(min,max,許容エラー数)になっていますが、上記のようにオーバライドのチェックされているので、1が適用されて、実際は、
0±1≦ペア回数≦1 ±1
のように許容エラー部±1として作用します。たとえば、
6回=3回1人 1回1人 2回1人
のように一人の人にエラーが集中しても、目的関数値が小さければそちらが最適値になります。しかし、題意は、一人の人に負担を集中させないことにあるので、±1で2回まではOKだが、3回は絶対ダメよ、とハード制約にしている訳です。この辺の設定をPythonソースを弄ることがなく出来るようなオプションがオーバライド設定になります。
ちなみに、許容0とすれば、ハード制約となり、解が存在しない、もしくは、強制的に夜勤4回以下となるでしょう。→やってみました。解がありません。つまり、全員を1回以下にする解は物理的に存在しません、ということです。
import sc3 def ペア回数制限Sub(person1,person2): list=[] for day in 今月: v1=sc3.GetShiftVar(person1,day,'入り') v2=sc3.GetShiftVar(person2,day,'入り') list.append(v1&v2) s=staffdef[person1]+"と"+staffdef[person2]+"の組み合わせ回数" print(s) sc3.AddSoft(sc3.SeqError(0,1,3,list),s,5)#min max allowable errors 最大1回に制限 def ペア回数制限(person1): if person1 in 男: if person1 in 看護師 or person in 准看護師: #ペア対象 女性 かつ 看護師または准看護師 ではない for person2 in 入り: if person2 in 女 and person2 not in 看護師 and person2 not in 准看護師: ペア回数制限Sub(person1,person2) else: #ペア対象 女性 かつ 看護師または准看護師 for person2 in 入り: if person2 in 女 and (person2 in 看護師 or person2 in 准看護師): ペア回数制限Sub(person1,person2) else: if person1 in 看護師 or person in 准看護師: #ペア対象 看護師または准看護師 ではない for person2 in 入り: if person2 not in 看護師 and person2 not in 准看護師: ペア回数制限Sub(person1,person2) else: #ペア対象 看護師または准看護師 for person2 in 入り: if person2 in 看護師 or person2 in 准看護師: ペア回数制限Sub(person1,person2) for person in 特別ペア回数制限: ペア回数制限(person)
Ans.
男同士の夜勤禁止が、間違っています。「かつ」は、「全員」という意味です。この制約を言葉にしてみると、
男全員が男全員と入りをすることは禁止
という意味になります。そもそも男全員が夜勤に入ること自体があり得ないので、それを禁止にしても意味はありません。
問題は、二つあり
■同じ集合である「男」と「男」を禁止にしていること、
■全員の意味である「かつ」を使用している
Ans.
スタッフプロパティシートに、連続夜勤回数の最大と最小を記述します。連続夜勤を行うスタッフには、このプロジェクトの場合、漏れなく2連休が付いてきます。(ハード制約で記述)
そのために、稼ぐ意味も含めて連続夜勤を好む方は、最小連続夜勤回数を設定します。反対に、連続夜勤を好まない方もいるでしょう。そういう方は、最大連続夜勤回数を0にします。
連続夜勤のカウントは、明入パターンで行えばよいでしょう。
Ans.
パターンが間違っています。下のパターンで□で囲んだところは、各々
「明けの後週休以外」の禁止 →明けの後週休を強制
「明けの後、入り」
で「明けの後」が共通しています。
パターンは全体に対して作用する。同じパターンがあったときは、短いパターンで制約される、という原理を想いだしてください。長いパターンの方は、6日のスパンに対して、禁止です。一方短い方は、2日のスパンに対して禁止です。よって、「明けの後週休を強制」制約が作用し、行制約No4は、決してヒットすることはありません。
次の2点です。
1)連続勤務6日禁止の定義の明確化が必要
必ず週休が5日内に1回以上含まれるなのか?休日集合が5日内に含まれるか? 施設によって違います。週休でなければならない施設もあるし
2交代の場合、入り明けは、連続しています。入りが、今月最終日が連続勤務5日目だったとしたら、来月1日目は、6日目明けが強制され矛盾となってしまいます。従い、予めそのようなパターンは、禁止しておく必要があります。例えば、次の記述青部になります。入明入明まで考慮すると、恐らくリソース的に月末は困難になってしまうでしょう。なので強制的に先月からの夜勤の場合は入明休となるこのパターンで良いと思います。
Ans.曜日集合の指定が間違っていました。「制約開始日一日前」と「制約開始日一日前から」
は、違います。
マウス中ボタン(ホイールボタン)を押すとDay集合が表示されるので確認してみてください。スケジュールナースは、この曜日集合を一日づつずらしながら全体をスイープして制約しています。なので、「制約開始日一日前から」は、先月の最後の日+今月(28日)分の集合である必要があります。他も同様です。
間違いのないやりかたは、
パターンをいじったら、曜日タイプを「今月自動」にして求解し、ファイルを保存するようにします。
こうすると次回プロジェクトを読み込んだときに、適切に設定されているのが分かります。
Ans. 申し訳ありませんが、ありません。将来的にも、ほぼ可能性はないと考えてください。
理由は、こちら側の内部の事情によるものです。申し訳ございません。
■技術的には、エンジン系が、インテル系のCPUに限られるという事情があります。極限まで、最適化エンジンを「最適化」しているためです。X86/X64というインテル系のCPUをターゲットにしています。互換CPUとしてAMDがあり将来的にも王道と考えています。
■技術外の理由は、サブスク・買い切り版の形態の対応です。Appleの形態では、現状の買い切り版のような菅原システムズに支払う形態は認められていません。公的機関に納入している菅原システムズにとってこれは痛いです。
Appleに対して「App Storeでの30%というマージンは法外なぼったくり」「ユーザーの選択を狭める」と批判が集中 - GIGAZINE
また、マイクロソフトのマージンは、15%です。ただし、マイクロソフトの場合は、米国からの支払いとなるので、米国の税金が取られるようです。アップルは分かりません。なので、どちらに利があるかは、一概に比較できません。余談ですが、Appleは、審査もマイクロソフトに比べて厳しいので、GUIを大分見直す必要があります。
■Excelとの親和性
ソフトの性質上、デスクトップアプリであり、Excelとの連携・親和性が必須です。
Ans.
買い切り版をお買い上げ頂きありがとうございます。
ソフトウェアは、常にバージョンアップしています。無償版での旧プロジェクトを含めて、下位互換を実現しています。適正な記述であれば、新しいバージョンでもそのまま読み込み、実行が可能です。
しかしながら、新しいバージョンでは、より不正な制約記述に対してエラーチェックを厳しくしており、無償版ではエラーが出なかったものが、新しい版ではエラーが発生することは考えられます。求解ページに何等かのエラーメッセージが赤字である筈ですので、エラーメッセージに従ってエラーを潰してください。
もし、何も表示されない場合は、恐れ入りますが当該プロジェクトをサポートまで送って頂くようお願いします。記述修正をして返送します。
→**その後、連絡があり自力で記述修正をして動いているとのことです。
Ans.いいえ、アンインストールしてもアカウントとマシンは紐づけされたままです。紐づけは、ソフトではなくマシンで行われているためです。
ですので、自宅のPC等、不要となったマシンの紐づけを解除するには、以下のようなマイクソフトアカウント上で操作します。(アンインストール済とします。)
ストアにサインインします。
ご自分のアイコンが表示されていると思いますので、クリックすると次のような画面が出ます。アカウントとデバイスの管理をクリックします。
ご自分のマイクロソフトアカウントページが開きます。下の方にデバイスの表示があります。「全てのデバイスの表示」をクリックします。課題メモです。
1)icu 70人問題
夜勤10人という制約で、長日勤10人、入り10人、明け10人という規模の問題に対して現状6分位時間がかかっています。これを32threads cpuで実行したときに2分以下となるようにしたい。Algorithm1の再設計。
2)SchedulingBenchmark記録更新問題
大容量3次キャッシュを積んだCPUで、記録更新を狙いたい。Alrogirhm1の再設計とAlgorithm3/4の整数化機構再設計 Coptの採用検討(評価ライセンスを長期にもらえないか交渉)
3) INCR2 記録更新問題
Algorithm3/4 LowerBoundに課題。StrongBranchのDeepLearning化、再設計。2)と共通
4)ペア制約 Algorithm3/4問題
ペア制約があると、途端にAlgorithm3/4の優位性が失われる問題。ブランチングと、整数化機構の再設計
5)論文執筆
国内特許ばかりで国際的な認知がない。WEB結果では認知されない。上記新記録を結果を持って投稿。Native共著者要。
6)英語本
英語Kindle本化。英語講義・トレーニングプロジェクト作成
7)AIモデル化
LLMのファインチューニングでJSONを出力させる。プロジェクトの自動作成支援
課題が多すぎですが、サポートもしっかり行いつつ、一歩一歩進めていきます。
1)に関しては、5月中の性能評価を目指しています。2)ー6)に関しては、今年前半に目途を付けたいと思っています。7)に関しては面白いテーマだと思います。私の方は、ソルバの高性能化で手が回りませんが、面白い研究ネタだと思います。
プロジェクトファイルは附属していますが、そのままでは動きません。Windowsにポートしたときのメモ
1)namespace Topor 追加@TopiWL.cc
Topor::CTopi<TLit, TUInd, Compress>::TULit* CTopi<TLit, TUInd, Compress>::WLPrepareArena(TULit l, bool allowNewBinaryWatch, bool allowNewLongWatch)
2) NOMINMAX define 追加::max()がマクロで置き換えられる問題回避
4) SKIP_ZLIB define 追加 ZLIB使用しない
5)popen/pclose をfopen/flcoseに代替え UNIX用を置き換え
6)ソース追加
TopBitcompression.cc TopiInprocess.cc
以下1分20秒時点の、instance partial-10-13-s.cnfの結果です。
DPS n=1 120MB
Intel SAT 75MB
Minisat 250MB
ということで、Intel Nadalさんのソルバが少ない結果となっています。時間が経つと、Minisatは、GBオーダになっていました。一方他の二つは、ほぼ同じ値のままであり、進化していることが伺えます。性能はともかく、メモリ消費が少ないのが欲しかったので、Intel SATを採用することにしました。ちなみに、このソルバは、超巨大なインスタンスを扱えるのが特徴で、電通大、戸田先生のALLSATを簡単なブロッキング手法で凌駕する性能だそうです。
今回、考えたアルゴリズム1の実装は以下の通りです。
1)多数スレッドによるメタヒューリスティクス
2)多数スレッドによるSAT
3)DPS
究極的な目標は、
A)ICU 70人で2分を切る
B)INSCⅡでの記録更新
C)Scheduling Benchmark での記録更新
です。2)3)が当初の目標だったのですが、どうせなら、実用的な成果も得たいという壮大な計画の基にアルゴリズム1の改善に取り組むことにしました。Aが出来るとB)C)でも組み込むことが出来、有利に働きます。
条件は、高機能CPUで64GB/32threadsで実現するものとします。
メタヒューリスティクスは、従来使っていませんでしたが、探索初期段階では有効なことが分かっています。問題は、局所解からの脱出ですが、単純な解決策は、多数スレッドで解く、というものです。イメージ的には、徒競走です。どの子が速いからは分かりません。が、多数を走らせれば、中には速い子もいるでしょう。
2)は、障害物競争です。1)の子のバトンを受けて、障害物に挑みますが、障害の大きさは、不明なため、必ずしも1)のトップが2)のトップになるとは限りません。
3)は、玉入れ競争のイメージです。2)のトップのバトンを受けて皆でスタートします。1)2)は、個人競技ですが、3)は団体で挑みます。皆の総合力で解を得ます。
解を決定的にしつつ、高速かつ安定に動作させます。上記の枠組みを作成し、作業を進めていきます。
今だに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されているのですが、その予定に対して制約が利くので、最終的に解が妥当であるかどうか、チェックされるところが違います。
また、この方法は、他に修正がない最終解でのみしか使えません。さほど重要でなく、制約化するのも面倒という場合に有効な手段です。
Ans:求解エンジン(ソルバ)に渡している制約ファイルです。無視して頂いて構いません。
求解するとソフトがjsonファイルを生成しソルバに渡します。ソルバは、最適割り当て解をGUIに渡して求解終了となります。
例えば、tutorial1.jsonの中身は、次のようになっています。テキストファイルなので、メモ帳等で、中身を眺めることが出来ます。
ビギナのためのAIアプリの作り方18講
Visual Studio Dev Essentials (microsoftemail.com)
昨日のNueroBackで用いられているHugging Faceとは?
AIプラットフォーム「Hugging Face」の使い方を解説 #NLP - Qiita
少しサーベイしてみました。
MIPソルバーのBranch and Boundについて、
Neural Divingと、Neural Branchingについて提案しています。
[2110.14053] NeuroBack: Improving CDCL SAT Solving using Graph Neural Networks (arxiv.org)
CNFをGNN構造に展開して機械学習によりInitial Phaseを予測しようというもの。
アルゴリズム3,4に関して、少しアイデアが浮かんできたので、今年前半で実装してみようと思います。組み合わせ最適化で最も重要、かつ難しいのは、整数解を如何に速く発見できるか?です。LBを推定するだけなら、かなり大きな問題でも1分もあれば、出来てしまいます。しかし、そこからUBを近づけるには、現状かなり時間がかかってしまいます。
上記に挙げた方法も無くはないと思いますが、NSPに関しては、未だ本質的改善が出来る可能性があると思います。
昨日もユーザミーテイングで、一緒に悩みました。
現象は、夜勤明け公休なしになってしまうというものです。
結論から言うと、原因は、いつもの、
「リソースのないところでの予定の入れすぎ」
でした。
調査として次を行いました。
<公休数が少なすぎる可能性>
可能性として、8回しか公休がないところで、7回夜勤をすると難しそうだ、という懸念はありました。そこで、年休をフリーで追加しましが、変化はありませんでした。別手段としては、公休数のソフト制約を弱めて変化がなければ、それが原因ではない、ということが言えます。
<夜勤明け公休制約のハード制約化>
「夜勤明け公休なしは、許容できない」とのことでしたので、ハード制約にしました。結果、ハードエラーとなり解はありませんでした。
<当該日周辺の予定をソフト制約化 原因の特定>
ハードエラーで指摘される箇所周辺の予定を弱いソフト制約を行いました。結果、予定変更された箇所が一か所ありました。リフレ予定が早番1に置き換わった箇所が1か所ありました。これにより、原因が確定しました。早番1を行うスタッフがいなかったのです。
<暫定対策>
列制約の殆どはハード制約、夜勤明け公休もハード制約、リフレ等の希望休みもハード制約で、解がない状況です。そこで、2F/3F間のJOB変更を行い急場をしのぎました。
<恒久対策>
リソース余裕がないところに、予定が多数重なると、スタッフQOLに関わる部分に影響として現れることがあります。そうなると、
■列制約の殆どはハード制約、
■夜勤明け公休もハード制約、
■リフレ等の希望休みもハード制約
では、解があるはずもないので、あらかじめその日に入れられる予定数を制限することが恒久対策になります。
例えば、
入り 1名
明け 1名
明け公休1名
早番1 1名
早番2 1名
遅番 1名
であり、上記仕事を出来るスタッフが8名しかいないのであれば、休みが取得可能なのは、僅かに8-6=2名ということになります。これが物理制約でこれ以上予定休みがエントリーされれば、解は決してありません。なので、この場合、
「休みエントリーは、2人まで、それ以上は、予定を出すときにスタッフ間で話し合い、じゃんけん、あみだくじ...で決めてね」。と予定書き込み表に予め書いておけばよい訳です。こうすれば、今回のような問題は起こりにくくなります。
事ある度に、言及しているのですが、なかなか理解されていない方が多いです。
schedule_nurse_lecture_note.pdf (nurse-scheduling-software.com)
の45page入学式・卒業式を参照ください。
人生初の勤務表作成 算数ができない?師長 (nurse-scheduling-software.com)
予定エントリーが無制限であったとしても、この歯止めがあれば、かなりの確率で救えると思います。入学式・卒業式に限りません。上記を取り入れて欲しいと思います。
是非、算数を理解して、出来れば、スケジュールナースの解析機能を使うことなく、勤務表を完成して頂きたいと思います。解析は、上記のように面倒な作業ですから。(一見関係のない、スタッフQOLに関わる部分にソフトエラーが出てくるので、気づきにくい種類のエラーとなります。予定入れすぎによるリソース不足という真の原因に辿りつくのに時間がかかります。)
4月は、新任の看護師長になりますが、古参スタッフからいじめられるケースを耳にします。知見を共有し助けられる場があれば、と思います。
https://www.nurse-scheduling-software.com/constraints_faqs/chapter51/
下がオリジナル解ですが、普通に逆循環や10連勤とかあったりします。
流石にそれはないだろうということで、制約を追加しています。Q.スケジュールナースの開発者は誰?
スケジュールナースは、ナーススケジューリング問題を解決するために開発された高速勤務表ソフトウェアです。その哲学は、日本のシフトを改善し、管理者の負担を軽減するだけでなく、スタッフのライフスタイルにも影響を与え、生産性の向上に寄与することです1。
スケジュールナースは、以下の成果を持つ菅原システムズのCEO、菅原孝幸氏によって開発されました:
もちろんです!ハード制約とソフト制約は、最適化問題やスケジューリング問題などでよく使われる用語です。それでは、両者の違いを説明しましょう。
ハード制約:
ソフト制約:
例えば、スケジューリング問題において、ハード制約は必ず守らなければならない制約(例:スタッフの最低労働時間)であり、ソフト制約はできるだけ守りたい制約(例:スタッフの希望休み日)です。最適化アルゴリズムは、ソフト制約を満たすように試行しますが、ハード制約に準拠するソリューションを見つけるために必要であればソフト制約を破ることができます。
理論的には、ソフト制約は柔軟性を持たせ、現実の問題に適した解を見つけるのに役立ちま
とまともな答えが返ってきます。面白いのは、昨日も全く同じ質問をしたのですが、答えは、同じ内容もしくは、近い内容ではあるものの、同じ文章ではない、ということです。
この深層化学習・機械学習は、モデリングに使えると思います。つまり、スケジュールナースに仕事をさせるには、
仕様→制約→Day集合・グループ集合・シフト集合の合成と、
スケジュールナースが理解している言葉にボトムダウンしていく必要がありますが、最も下層の集合合成で使おうというアイデアです。
例えば、昨日行ったDay集合の合成を自動で出来る可能性があると思います。このDay 集合の合成は、初めて行う方には難しいと思いますが、これを代わりに生成する、みたいなイメージです。
こちらは、スケジュールナース専用の学習が必要になりますが、無料で使える環境も出てきており試せる環境が出てきました。しばらくは時間が取れないので、直ぐには無理ですが、今年後半以降考えて行きたいと思います。
実装してみました。Pythonは、使っていません。
Day集合上級編とマクロによる実装となります。結構難しいと思いますが、Day集合作成とマクロの練習用としてもよいと思います。
SUGOIYAさんによる看護師勤務表2交代のサンプルが提供されました。ソース公開の主旨に賛同くださりプロジェクトファイルを公開して頂きました。
看護師2交代のサンプルとして、多くの方に利用して頂けると思います。
https://www.nurse-scheduling-software.com/japanese/nurse_scheduling_problem/chapter13/
本当にありがとうございました。
schedule_nurse_practical_training.pdf (nurse-scheduling-software.com)
の付録に付けているクイズプロジェクトは、昔のサポートで実際に遭遇した勤務パターンを題材にしたものです。是非答えを読む前にやってみてください。
私自身は、このパターンに遭遇したときに、どうしてエラーになるかが分かりませんでした。
スケジュールナースは、こういう問題に対しても、解がないことを直ぐに指摘できます。恐らく他のソフトでは、ダンマリになっていつまでも答えがでてこない、という状況になり易い問題、だと思います。さらにこのパターン部に問題があるという指摘ができないために、何が何だか分からない、という状況になることが予想されます。
これもアカデミックと現場とのギャップの一つです。MIPソルバでこれを解くと解がない、Infeasibleと出てくるとは思いますが、「スタッフXのYDayが。。」という指摘は決してできません。現場では、こういう問題がしょっちゅう出てくるのに、アカデミックは、何も答えてはいません。全てをソフト制約にすることは、一別解ではありますが、意図しない年休や、意図しない公休増加をもたらすという別の問題にすり替わる可能性があります。間違いなのか、意図なのかは、多分管理者しか分かりません。否、管理者さえも分かっていない場合もあります。それ故にハード制約とハード制約の衝突(Conflict)は、衝突可能性部をレポートされるべきだと思います。厳密には、これもNP困難なので完璧に行うのは無理があるのですが、大半のケースで対処可能です。(これは、スケジュールナースの特許6364638によるものです。最適化の技術に関しては、学術世界において日進月歩の激しい競争があります。しかし、実用性において重要なのは、ハード制約の原因をアシストすることです。)
しかし、熟練した師長に見てもらうと、一瞬で問題点を指摘されました。話を伺うと、スタッフの中にはこういうパターンを出してくるスタッフがいるのだそうです。このパターンだと必ず、年休または有給が必要となるのです。敵もさるもので、つまりは、分かって希望休を出してきているということです。先輩師長から、「このスタッフは、こういうのをよく出してくるから先に作っていくといいよ!」という人力アドバイスを受けたそうですが、それが唯一の人力による勤務表作成のアドバイスだったようです。
自動勤務表の場合は、もちろんそういう配慮は不要です。ただし、ソフトで年休を付けてやる必要があります。当該プロジェクトのオリジナルでは、もちろんソフト制約になっていたのですが、ハード制約とソフト制約の違いを学習・トレーニングするために、ハード制約にして、なおかつ公休数を8(ハード制約)に意図的に設定していた、というのが答えです。つまり、
■公休数8
■当該希望休パターン
は、どちらもハード制約であり、同時に満たす解が存在し得ない、というのが答えになります。解があるようにするには、どちらかをソフト制約にすればよいです。つまり希望休パターンの変更もしくは、公休数を9にすればハード制約違反は解消されます。
https://schedule-nurse.blogspot.com/2024/03/blog-post_6.html
マクロ設定がプロパゲートしない問題のFIX
■ExcelExportパス
ファイルが存在しない表示しない仕様に変更
■Dayグループ集合 マウスホイールボタン表示
空集合が明示されない問題のFIX
Q.
行制約グループ1の7行目で6連続勤務禁止の制約をしているのですが、求解するとxxの先月29日から今月3日まで6連続勤務となってしまいます。
解決方法をお願いします
Ans.
パターン最初の曜日タイプの指定を外してください。
「パターン最初の曜日タイプ」がブランクだとすると、7日パターンの場合、
先月部から制約されます。これがあるべき姿です。Q. Aさんは日曜始まりの1週間に4日勤務の条件があります。スケジュールナースのブログを見てPython制約でできるのを読みましたが、どのように解決したらよいか分からない状況です。自分なりに行制約の「Aさん」のタブに制約をしてみましたが何か間違っているような。。。。Python制約なら便利そうなのですが。。
「日曜日始まりの一週間」を先月からの1週間も見て継続する場合のやり方です。
表示開始日が6日間に限定した場合の話ですが、Pythonを使わなくても可能です。
先月が6日分あるとすると、以下の色部分に最初の日曜日がどのパターンにも一個だけ含まれます。
これを利用して、次のように曜日集合を構築出来ます。これで、必要な曜日集合が定義できました。
定義した集合を用いて制約します。
<端数の処理>
第5・第6週は、端数になる可能性があります。そのためマクロを定義します。
次は、マクロの値をマウスホイールボタンを押して確認しました。第5週の値は、1になっていることが分かります。ちゃんと端数処理されていることが分かります。(第6週の値は0になっていました。)
マクロの記述です。注意:
残念ながら自動で次月も自動計算するように出来ていないので、その月毎、マクロの設定を押す必要があります。次のリリースで改善予定です。
→BUILDMAR072024で改善しました。
https://www.nurse-scheduling-software.com/japanese/constraints_faqs/chapter35/