いつの間にか、米国税金の支払フォームが日本語で整備されていました。良くわからずに、今まで米国に30％取られていたのですが、W-8BENが日本語フォームで簡単に出来るようになってちゃんとしたので、その分は0％になるはずです。
Microsoftストア用のW-8BENの作成 #ストアアプリ - Qiita
マイクロソフトの分が15％あるので、今まで約半分取られていたことになります。マイクロソフトの場合、内訳明細も分かりませんし、お客さまがサブスク契約者かどうかも分かりません。
毎月マイクロソフトから外国送金があり、その都度、銀行からマネーロンダリングのチェックが入るのには閉口します。
列制約とは、縦の列のことです。
＜上記赤ラインを必要以上に高くとったときの問題＞
下記は、人力では到底できないような複雑な列制約です。
人力解の目的関数値は、UB=877
二つの問題が生じます。
（１）解空間が必要以上に狭まる
メンテナンスのない勤務表は存在しません。組織変更、人事異動、退職、妊娠・出産等により、月々に変更することが付きまといます。制約が複雑であればあるほど程、融通が利かないので、誰かが制約を変更しなければならない確率が高まります。
お客さまから仕様書を頂いて、制約に落としプロジェクトファイルを作成しました。この仕様書は、看護師勤務表ですが、今までにない複雑で精緻な仕様でした。特に列制約記述が複雑でした。
下は、お客さまの勤務表解（人力解）をスケジュールナースの予定として入力し求解した結果です。Excelデータを整列させ、コピペし、予定入力としています。この際、EXCELデータシート上の勤務表名をスケジュールナースのシフトラベルとしています。これを求解させると、人力解に対して仕様違反の箇所をマークさせることが出来ます。
Excelデータ
できるだけ看護品質を高めたい、スケジュールナースなら何とかしてくれる？という気持ちの表れだと思いますが、仕様書は、願望を書くところではありません。
仕様書は、現実の今運用している、あるがままのルールを書く ようにしてください。
願望仕様による弊害は、後述します。
行制約で、１回以下のところ、土日祝で２回勤務しているスタッフが１名います。
＜まとめ＞
予定が入ると、上記は、予定ハード制約の影響が出てきて、真の原因を見つけ出すのが困難となるので、ブランク予定のうちに、原因を特定しておくことをお勧めします。
こうした問題の多くは、行制約と列制約の矛盾で、供給コマ数と消費コマ数の関係で説明できます。
行制約のソフトエラーの要因は、列制約コマ数が原因だった訳ですが、このように着目するソフト制約をハード制約化して、その結果何が浮かび上がってくるのか？を見るのが原因解析の一手法です。
日～土を指定があります。まともに実装するのは面倒で、夜呼び出し間隔で1週間未満を禁止にする方が簡単です。この方式は、1週間未満のあらゆる2回を禁止するので、題意の（日～土）仕様を含んでいます。
このプロジェクトの場合は、呼び出しは、タスクなので、以下のように実装しています。
DDR5は、4枚刺しは、推奨されていないようです。実際48GBメモリ2枚＋16GBメモリ2枚では、起動しませんでした。
DDR5の異サイズ4枚刺ししてみた #自作PC - Qiita
マザーボードのマニュアルにも同一ロット4枚刺しが記述されていたのですが、同一メーカ品の同一仕様4枚,4x48=192GBで、何とか動いてくれました。
しかし、やはり同じに動いているようではないようです。
これからAIをローカルで試してみたい方は、GPUはなしとしても、メインメモリは32GBでは不足すると思うので要注意です。
メモリ問題から、全基数制約をコンパイルするのを諦めて、TIME制約とWEEKEND制約のみコンパイルします。
そうしたときに要するRoster1個あたりのメモリ所要量です。
コンパイルメモリ所要 コンパイル時間 グラフメモリ所要量
instance23 48GB 45分 0.7GB
instance24 140GB 2-3時間 1.5GB
このために、メモリを32GB⇒48GB⇒96GB⇒192GBまでDDR5を増量しました。instance23で、グラフコンパイルだけで、丸2日、instance24で2週間程度かかります。
＜コンパイル時間問題＞
こんなに時間がかかるなら、別な方法を検討したくなりますが、実は、この問題は、クラウドを使えば現在でも解決できます。というのは、スタッフ毎に独立してコンパイルが可能だからです。リソース無尽蔵のクラウド資源を使えば、並列にコンパイル可能です。つまり、リソースさえ気にしなければ、全スタッフを2時間でコンパイルは出来ます。
＜コンパイルメモリ問題＞
グラフのコンパイルに192GBメモリが必要です。AIに10年後の予測をしてもらったところ、AI需要等により64-256GBになるとのことでした。
よって、10年後では、標準的なPCで十分に対処可能になると予測します。
＜グラフメモリ問題＞
instance24は、150staffなので、平均1.5GBだとすると1.5*150=225GB > 192GB で足りません。
Diskに退避した場合、現在の高速SSD+対応ボードを使うと14GB/secの転送レートで、メモリ転送レートと比べて、そんなに遅くはありません。以前のHDDを使った転送レートと比べれば雲泥の差です。それでもGraph処理レートよりもDisk転送レートの方が遅い可能性が高いので、できるだけメモリ上で圧縮処理した方が得策とみます。
＜グラフ縮約＞
一度LBが算出されれば、後は、厳密解に拘る必要はありません。つまりLB算出までは、Fine、それ以降は、Coarseで制御します。グラフ処理速度は、グラフ規模で一意に決まるので、グラフを極小化することで、処理速度を向上させます。
まとめると、
LB算出までは、厳密解を得るために、多少時間がかかってもグラフの縮約は用いません。
LB算出以降は、実用的なBranch＆Bound速度とするために、グラフの縮約を用いて高速化を図ります。
以上の検討により,
■instance24のコンパイルに192GBメモリ48x4
■必要ならば、メモリ上でグラフ圧縮処理
■LB算出後のグラフ縮約
を行うこととします。
さすれば、グラフメモリ問題は解決できる、と結論します。
とりあえず、instance24のグラフメモリをDISKに保存中です。この予備処理に2週間程度かかる予定です。一旦グラフメモリを保存することが出来たならば、後はそれを用いてさらにアルゴリズムの検討を行うことが出来ます。HIGHSの新IPMは、GITHUBを見るとかなり期待出来る速度となるようです。これにより、課題要素は、それぞれクリアできるのではないか？と期待されます。
各スタッフの制約を全てグラフ化することは、現在のメモリで難しいので、次善の策として、以下を検討しました。
１）MIPソルバで解く
HIGHSで解いてみましたが、遅すぎて使えません。ただし、ROOT LB時のみ使用する、アイデアはあります。
２）基数制約を主問題に移す
主問題のLpソルバの負担大となる問題点があります。また、概算値を高速に得る手段としては、有望ですが、今回の要件は、厳密解を得ることにあり、その面では何ら解決策にはなりません。厳密解を得るには別な手段が必要です。
３）基数制約をコンパイルしないでグラフ化、列生成問題として解く
この手段は、前にも行っていて(instance22の世界記録提出で使用）有望なのですが、厳密解を得るという意味においては、苦しいです。加えて、Instance24では、やはり遅すぎて使えませんでした。
４）部分的に基数制約をグラフ化、列制約問題として解く
最終的に残った候補です。基数制約の全てをグラフ化することはメモリ的にアウトなので、支配的性質を持った基数制約についてのみ着目してグラフ化します。この方法は、厳密解を得易く、しかも３）よりは遥かに高速で有望です。しかし、instance24のたった一つの基数制約をコンパイルするにも128GBメモリでは出来ませんでした。
そこで、4)のグラフをコンパイルするべく、メモリ増強を行いました。
Q.下図のようにしたいのですが、上手く行きません。
| AM(ph0) ｜ PM(ph1)
| 作1,作2 ｜ 会
=================================
早番 から作業１を 2名 | PMは会議の日であれば会議メンバーのみ会議。その他はタスクなし
遅番から作業２を１名 | PMは会議の日であれば会議メンバーのみ会議。その他はタスクなし
日勤 から作業２を１名 | PMは会議の日であれば会議メンバーのみ会議。その他はタスクなし
Q.
例えば、No1で作業所１早番は早番可能な職員を午前中に作業場所１のタスクを最大２名配置そしましたが、これは午後には配置しないと同義にはならず、午後に配置したくなければ、No２のように午後は禁止とすることが正解なのでしょうか？
Q.タスク型勤務表の作成についてご教授お願いします。
① 10名の職員
② 勤務は日勤、早番、遅番の3つ
③ 毎日早番は2名、遅番は2名、日勤6名
④ 午前中に作業所１に早番１名と遅番１名を配置
⑤ 午前中に作業所２に日勤１名、早番１名を配置
⑥ 会議が５，１０，１５，２０，２５，３０日の午後にある
⑦ 会議メンバーは全員午後の会議に出席、午前中は作業１もしくは作業２の配置可
上記の条件でタスク型勤務表を初めて作成してみましたが、うまくいかずなにをどうしたらよいのか全く分からない状態です。
タスク型勤務表も勉強したいので、ぜひご教授ください。
Ans.
タスク定義が以下になっていますが、
Q.
介護施設における相性問題です。被害者A/B共、問題スタッフからの執拗な攻撃を受けています。特にBは、利用者からの評価が高いスタッフですが、問題スタッフの顔を見るのも心的ストレスとなるので、完全に分離した勤務とする必要があります。被害者Aは、それほど酷くはないのですが、心療内科を受診中であり、可能ならば、Bと同様に、完全分離勤務としたいです。
Ans.
被害者集合を定義します。
ペア制約で、以下を禁止とします。この施設では、夜勤スタッフは、日勤を行わないので、日勤を考慮する必要はありません。
■問題スタッフが入り ー 被害者グループの遅番
■問題スタッフが明け ー 被害者グループの早番
■問題スタッフが遅番 ー 被害者グループの入り
■問題スタッフが早番 ー 被害者グループの明け
制約名は、IfThen形式で記述していますが、両方向に作用することに注意してください。
Ans.
整数カウント制約を使います。半日関係のカウントを１、その他を2として計数します。
Ans.
＜解析＞
赤●のラインをダブルクリックします。
この制約、ソフト制約レベル２の許容エラーは、下記より１です。
なので、ハード制約は、４＋１＝５最大として作用します。つまり６回以上の２連休はハードエラーとなります。予定もハード制約、行制約もハード制約、ハード制約間の矛盾ですので、ハードエラー、つまり解のない状態となる訳です。
＜改善策＞
意図は、「有給も含んで１回以上の２連休を確保したい」、ということだと思いますので、最小制約だけを残して、最大制約は削除すれば、矛盾を解消できます。
しかし、「休み２連休は最大４回(有給は除く）も制約したい」、ので、最大用に新たに制約を追加します。
Ans.
難しいと思います。スケジュールナースは、分野を跨いだ最先端の技術を採用しており、少なくとも理工学大学院程度以上の広範な知識が必要となります。加えて、設計ソースを理解するには、C++に対する深い造詣、C#とpythonのプログラミング能力に加え、以下の分野の先端研究論文を理解する必要があります。
１）人口知能学会 SATソルバ・Maxsatソルバ for AL1
２）オペレーションズリサーチ学会 組み合わせ最適化 for AL2-3
３） 人口知能学会 グラフ理論 for AL3
４） 電気通信学会 回路合成 for AL3
５）言語処理学会 コード生成
しかし、プロジェクト作成をするだけならば、構造の理解は必要ありません。Pythonも殆どの場合必要なく、中学校の集合の知識さえあれば、誰でも学べます。
Ans.
問題ございません。ただし、サブスクライセンス(480円/月)については、エンドユーザ様病棟毎に一個づつ必要になることにご注意ください。お持ちのライセンスでエンドユーザさまのプロジェクトを設計・開発することは出来ますが、そのライセンスで、エンドユーザさまが運用することは出来ません。
例えば、次のような立ち上げのシナリオは、如何でしょうか？。
１）他の病棟プロジェクトを作ってみる。（報酬なしで）
２）分からないところは、菅原システムズに相談する（必要に応じてZOOMを依頼）
３）数病棟の経験の後、報酬付の受託サービスを開始する。
１)を数病棟OJTを行うことで、スケジュールナースの使い方と、その過程がどれ位大変か？が分かってくると思います。
大変なのは、スケジュールナースそのものではなく、エンドユーザの意図とスケジュールナースのマッチングを取ることです。
エンドユーザのお話を聞いて、スケジュールナースに落とすには、時間がかかります。作って終わりではなく、メンテナンスや操作指導等も時間がかかります。大抵の場合、「割に合わない仕事だなあ、」
という結論になると思います。従い、３）に移行しないまま終了することもアリだと思います。
スケジュールナースの使い方については、数病棟を経験すれば、看護師勤務表については、出来るようになると思います。（看護師勤務表は、既存パターンのどれかに当てはまります。）
まとめとして、
A）プロジェクト作成について、上記１）～３）のステージに関係なく、その都度アドバイスを行う支援は可能です。
B）それ以外について（販促等）、支援・アドバイスは出来ません。
Cuopt,Highs共に、ダイレクトコルスキー分解を用いたIPM（内点法）を準備中の模様です。
Githubで実装を眺めることが出来ます。10月中のリリースと予想します。
超大規模問題、instance23/24の問題は、
■グラフがコンパイル出来ない
■SATソルバがコンパイル出来ない
■Lpソルバが遅すぎる
というものです。３番目の問題について、PDLPに期待しました。1e-4では、期待通りの性能を示すものの1e-5以上の精度となると遅すぎ、実用精度の1e-7では、全く遅すぎて使えないことが判明しました。
そこで、高精度領域でも速度が落ちないバリアソルバに期待がかかります。NVidia CuDSS疎行列のコルスキー分解で革新的な速度向上があったようです。CuDSSについては、プレリリースされており、その気になれば、これを用いて自前実装も可能だとは思いますが、上記の通り、リリースを寝て待てばよいだけなので、待つことにしたいと思います。それまでに、上記他の課題をクリアしたいと思います。
■SATソルバが使えない問題
に対して、構造を見直しメモリダイエットを行いました。およそ1/4程度にはなりました。
結果、instance23については、AL1でコンパイル出来るようになりました。このとき、25GB位の消費です。
SATソルバが使えないと、やはり痛いです。LPソルバから整数化を行うのにLPソルバだけで整数化しようとすると途方もない時間がかかります。現実的な時間内に解を得るには、なんとかして使えるような検討を行う必要があります。
PDLPの改善版です。3倍程度、特に高精度領域において、改善が著しいようです。
[2507.14051] cuPDLPx: A Further Enhanced GPU-Based First-Order Solver for Linear Programming
■LPソルバが遅すぎる問題
現状では、全く遅すぎて、10倍以上の速度アップが必要ではないかと見ています。
上記でも足りませんが、とりあえず、
ＨＩＧＨＳまたは、Cuopt で、実装されるのを待ちたいと思います。
