ヘルスケアのOR」第20回研究会（学生発表会)

 学生さんの発表会です。ZOOMで視聴することにしました。

OR学会の会員ではありませんが、将来、こちらでもスケジュールナースの最近の成果についても、報告できれば、と考えています。

＜特殊から一般へ＞

ナーススケジューリング問題のオープンインスタンスを全てCloseするという空前絶後の壮大な計画は、難航していますが、INRC2については、形が見えつつあります。今までに得られた知見を総合すると、ナーススケジューリング問題を解く一般系というのが、少し見えてきたような気がします。特殊で困難な問題群ではありますが、それを解く努力を重ねることで、それで得た知見を基に、実務上の比較的容易/困難なインスタンス群についても、最適解をリーズナブルな時間内に提示するという、

塾講師配置問題の最適化 #数理最適化 - Qiitaの「ナーススケジューリング問題は、終わっていない」

に対する回答を示せるのではないか？と考え始めています。当初は、ただ世界記録更新だけを目的にしていたのですが、特殊なインスタンスから一般インスタンスへの応用が可能ではないか？と気づきました。言い換えると特殊解法から、一般解法への統一化です。どのような問題も、それに適した特殊なアルゴリズムを適用するのではなく、一般化した一つのアルゴリズムで解くのがスマートであることは言うまでもありません。どのような問題にせよ、それに入力すれば、最適解がリーズナブル時間内で出力される、それがあればアルゴリズムを選定する必要はありません。

Q.2025当直拘束表の出力が出来ません

 Ans.申し訳ございません。

貴病院用医師当直拘束表のPython記述が2024年の固定となっておりました。Python記述のバグです。申し訳ございません。

以下のようにPython記述を修正しました。

＜修正前＞

＜修正後＞

Pythonソース修正

貴病院用ユーザマニュアル追加

実務につなげる数理最適化

梅谷先生のlectureです。 

如何にして、問題を解決していくか？について道筋を述べられています。

https://speakerdeck.com/recruitengineers/brainpad-meetup-umetani

Printemps メタヒューリスティクスソルバ

 メタヒューリスティクスに基づく汎用線形整数計画ソルバーの開発 - Speaker Deck

ベースになっているのは、法政大学の野々部先生のWCSPです。WCSPは、汎用国産ソルバNuorium Optimizer にも組み込まれています。

藤井　浩一｜株式会社NTTデータ数理システム

野々部先生のWCSPは、第一回のナーススケジューリング国際競技会で、3位に入賞されています。野々部先生とは、以前RAMP講演でお会いしました。

その系統であるPrintempsもシフトスケジューリング問題に期待が持てるかもしれません。オープンソースでMPSファイルも読み取れます。オプションで連続変数を整数として読むことも出来ます。

Optimization Night#9に参加できなさそうなので発表されるPRINTEMPSで一人遊んでみた #最適化 - Qiita

こうしたソルバは、分枝限定法ソルバの初期段階でのUBを得るのに有効な場合があります。以前は、Feasibility Pump しかありませんでしたが、最近では、

GitHub - GioniMexi/FeasPumpCollection: Using multiple reference vectors in the Feasibility Pump.

CAI教授のローカルソルバシリーズ、

GitHub - shaowei-cai-group/Local-MIP: A standalone local search solver for general mixed integer programming

GitHub - shaowei-cai-group/NuPBO: A local search solver for PBO

GitHub - shaowei-cai-group/ParaILP: A Parallel Local Search Framework for Integer Linear Programming with Cooperative Evolution Mechanism

GitHub - shaowei-cai-group/PRS-sc24: Submission of PRS and PRS-distributed to International SAT Competition 2024

等あります。

n100w8_1_2-4-7-9-3-9-2-8 solved!

It took us five months to solve this problem.　The challenge lies in proving that it is optimal.

n100w8_1_2-4-7-9-3-9-2-8:  LB=2145 UB=2145

While the upper bound (UB) of 2145 is relatively easy to obtain, demonstrating that there is no better solution is quite difficult. With the standard Branch and Bound method, you could run the algorithm for a million seconds and still not achieve a proof.

The initial gap between the lower bound (LB) and upper bound (UB) is less than 10, which may seem manageable, but it is actually one of the most challenging problems.

Throughout this process, we have learned a lot and gained valuable knowledge. What makes this particular instance unique is the extremely low gap-narrowing gain (a term we coined). We believe this is due to structural symmetry. To address this, we would need to implement symmetry breaking, but we will discuss that another time.

 There are now only two remaining unresolved instances for INRC2 8weeks on our side! 

n080w814-4-9-9-3-6-0-5

n080w820-4-0-9-1-9-6-2

Optimization Night 9

CDCLによるMILP解法が興味深いです。日本でも、このような方がいらしたのですね。NTT DATA出身の方らしいのですが、この会社は、OR業界の重鎮が在籍され、東大・京大出身の方が多い、印象です。（⇒RAMP講演の懇談会で名刺交換させていただいたことがありました。そのときは、NTT DATAに所属されていました。当時、私もSATの限界を感じ分岐限定法の勉強を始めたばかりでMILPのヒュリスティクスについて質問させていただいたのですが、丁寧に教えて頂いたことがあります。）

 Optimization Night #9

INTSATについては、その後、RoundingSATやExact系に引き継がれていると思いますが、Benders　Decompositionを用いるというのは、聞いたことがありません。CDCLでBenders Cutを用いるのは新しいと思います。研究の最前線だと思いますので今後も要注目です。

CDCL による厳密解法を採用した MILP ソルバー - Speaker Deck

Q 日勤リーダを２－３日間ずつ、A/Bチーム各１名とするには？

 Ans.

休日も含めて、全日リーダを各１名配置した解です。

シフト「リーダ」を追加します。

列制約で、A/Bチームから各１名を設定します。なお、若手二人がリーダとならないようにしています。

リーダ回数を指定するために、グループ定義を設定します。

スタッププロパティシートで、各スタッフのリーダ回数を設定します。禁止の人は最大０、

制約なし（何回でもOK）の人はブランクにします。

行制約です。１日単リーダを禁止、４日連続を禁止とすれば、残りは、２－３日間連続のリーダとなります。また、日勤リーダの間隔が短くなりすぎないようにしています。

以上で、全日リーダ、２－３日間A/Bチーム各１名の実装が完了しました。

日勤者数管理は、リーダを含めて日勤者数とするか、リーダを含めない日勤者数とするかは、列制約による実装となります。ここでは示しませんが考えてみてください。

＜平日日勤リーダのみの場合＞

平日のみ日勤リーダにしたい場合は、以下を変更します。このようにすると、全てのパターンは、平日ついて作用することに注意してください。

先月部を含めるとハード制約では、矛盾が生じる可能性があるので、全てソフト制約とします。

列制約で、「今月平日」、「今月休日」を追加変更します。今月休日では、日勤リーダを不可とします。

以上の変更で、平日のみ２－３日間、日勤リーダの実装が完了しました。

下の解を見ると、休日を跨いで、２－３日間、日勤リーダが実現出来ていることが分かります。

先月休日は、リーダが割り当てられています。これは、先月予定部がフィルインされていないことと、先月休日に対しては、なんの制約もしていないためです。先月予定部がフィルインされていれば、解消するので上の制約で問題ありません。

sloppy24

Solving Linear Optimization Problems for Pseudo-Booleans and Yonder 

の略らしいです。ワークショップです。

Jakob Nordström: SLOPPY '24

確かに、SATを一般のMIP問題に適用しようとすると、CNF表現では、無理があると思います。これを疑似ブーリアンと抽象化することで、IP問題と親和性が生まれます。で、そこにCutting Proofを入れるという発想は自然なものとなります。

ただし、一般にLPの速度は、CDCLのバックトラックに比べ、二けた以上遅いので毎回行う訳には行きません。LPソルバを導入した場合、この辺をどうバランスを取っていくかというのが実装上の問題かと思います。

Yinyu Ye教授の講演集

内点法の大御所の講演集です。 

web.stanford.edu/~yyye/talks.html

特に、

Rescale

は、最近のLPの動向について詳しく大変参考になります。

COPTに関して妙に詳しいので、もしかしたら、COPTの創業者達は、教授の門下生？かもしれません。

Q 次のソフト制約で、許容範囲を超えています。のエラー解析の仕方

 Ans 

次のようなエラーとなっています。

この上部を見ると、SoftConstraintColumn5という赤エラーが表示が出ています。これは、ソフト列制約レベル５の許容範囲が超えていることを示しています。

範囲が超えているというエラーなので、極端に範囲を大きくすれば、解が出ます。許容範囲を2→１０に変更しました。

これで、解が出ました。列制約レベル５に対応する重み５のエラーが多数出ています。実際に解の状況を確認します。休日の制約であるはずなのに、平日にもエラーが表示されていることが分かります。

Day集合を確認してみると、次のように上図解の通りの集合となっています。

Day集合の指定が間違っていることが分かりました。

正しい、集合に修正します。

修正後の解です。平日日勤と排他的になっていることが分かります。

まとめ

１）一つ制約を書いたら、直ぐに求解して動作を確認しましょう。

２）制約におけるDay集合、グループ集合を確認しましょう。

３）許容範囲を超えています。⇒当該許容範囲を極端に大きくしてみて、解が出し原因を突きとめます。

pseudo boolean competition2024

Pseudo Boolean Competition 2024

 ８年ぶりにcompetitionが再開されました。この理由として、２０１６年の参加者が殆どいなかったこと、Jakob Nordstr¨ omさんが、強固に開催を主張したこと、が挙げられています。

参加者としては、CAI教授系中国チーム、RoundingSAT系、Exact系、SCIP系、そして、名古屋大酒井先生です。2016年来の進歩としては、RoundingSAT系のcutting proofがあるのですが、それなしのNAPSと比べると、それほど差がついているようには見えないというのが意外でした。

PB24 Pseudo-Boolean Competition 2024

いずれにせよ、今後の方向性としては、RoundingSATをベースとしたものになると思います。私も、この発想を取り入れようかと思っています。

chat gptの構造化出力

待ち望んでいた機能が実装されたようです。 

https://note.com/mz700/n/n1ff5b41abb8b

Azure版でも可能になっています。

Azure OpenAI Service で構造化出力を使用する方法 - Azure OpenAI | Microsoft Learn

これで、何が嬉しいかというと、出力が完全なjsonで出てくるということです。しかも、ユーザの定義するJson形式で出てくるというです。スケジュールナースの制約指示は、私が定義したJsonスキーマに基づいて、GUIが作成を担当しています。つまり、

制約作成者⇒GUI⇒JSON⇒ソルバ

という現在の流れになっています。これを、AIに学習させれば、

制約作成者⇒AI⇒JSON⇒｛ソルバ　GUI｝

という、最も熟練度を要する部分をある程度、置き換えることが出来る可能性が出てきた、ということです。既にGitlab-copilotのように、AIは、pythonコードも出力することが出来るようになってきました。スケジュールナースのJsonは、実はPythonコードも含む仕様です。なので、モデリングの全てを任せられる可能性まで視野に入れることも出来ます。信頼性については問題があるのが現状ですが、AIの日進月歩に期待しましょう。テキストもしくは音声で、「ああして、こうして」と言うだけで勝手にモデリングしてくれたらなんて幸せでしょう？

かって、看護師長時の妻は、私の傍らにいて、「ああして、こうして。」と言うだけでした。結局、私という存在がいるので、最後までスケジュールナースの制約を覚えることはありませんでした。それでも、私という制約作成者がいたおかげで勤務表づくりは何の問題もありませんでした。

私の代わりをAIに担わせることは出来ないでしょうか？

数理最適化の練習問題をLLMを使って自動生成する

幸いにして、スケジュールナースは、オープンソースのモデリング集があります。日本、否、世界中の看護師勤務に関する知見もあります。このブログも実は、モデリング学習資源の一つです。10年に渡る膨大なスケジュールナースのモデリング資源があり学習資源については事欠きません。

そのスケジュールナースJsonスキーマは、公開していませんが、出力されるJson形式をみれば、大体想像がつくと思います。

また、JsonからGUIにコンバートするプログラムの開発も必要となります。AIが出力したJsonを人間が視覚的に理解するには、GUIでの視覚表現に戻す必要があるからです。

今後の予定として、

世界記録を更新し、

公開されているナーススケジューリング問題を全て解き、

ソルバの再構築の後に

取り組んでみようと思います。ソルバ再構築は、未だ構想段階です。今回のINRC2を全て解こうという取り組みの際、得られた知見を持って再度ソルバ全体を見直す必要が感じました。一言で言うとSAT表現とリニアソルバの融合になります。具体構想については、別の機会に。

来春以降、主要テーマとしたいと思います。

NuerobackのGNN学習

 NEUROBACK: IMPROVING CDCL SAT SOLVING USING GRAPH NEURAL NETWORKS

が公開になっています。未だソースは公開になっていないようですが、５％－７％の性能向上が見られたということのようです。本当にこんな単純なことで、そんなに性能向上するのか？の疑問に答える形の論文になっています。

ソースが公開されたら、データセットも整備されているので、やってみようと思います。

スケジュールナースでのプロジェクト群を同じ理屈で学習することで、性能アップも理論的には可能であると思います。ただし、高々数パーセントなので、アルゴリズムや、アーキテクチャ変更による効果には、及ばないということだろうと思います。

しかし、AI学習よる成果を何らかの式に落とし込めるということは、AIモデリングの一歩になる可能性があります。ちょうどGPUも購入したので、ソースが公開されたら試してみようかと思います。

Q.週休、週1回の実装の仕方

Q.週休は、任意の1週間区間で見た場合、必ず1回以上含まれる必要があります。どのように記述したらよいでしょう？

 Ans.

貴職場の場合、別に6連勤務禁止、という制約があります。この制約は、上記より上位の制約になります。任意の1週間区間で見た場合、必ず1回以上含まれる⇒7日週休無は禁止ということです。6連続週休無禁止は、7日週休無禁止を必ず含みます。よって、6連続週休禁止とすれば十分です。

実装は次になります。6日連続週休なし禁止です。

2行目の記述は、このパターンに対する特殊ケースの記述です。入り後は、必ず明けとなることに注意します。制約最終日に入りが来た場合は、翌月1日は、必ず明けとなるので、連続週休無4日で切らないといけないことに注意してください。

次に、間違えている実装例を示します。

１）「休集」だと、必ずしも週休を意味しません。仕様は、任意の1週間区間で、必ず週休が1個含まれる、です。この実装の場合、週休が1回も含まれないことがあり得ます。

２）Day集合がいずれも正しくありません。（前日のブログをご参照ください）

３）防止パターンの最後に規定がないので、解空間の減少が懸念されます。防止パターンが必要なのは、制約最終日だけなので、パターン最後の曜日タイプに「制約最終日」を記述してください。

Q.月に１回は、日曜日に休みを入れたい

 Ans. この職場では、規定があり、日曜日休みを１回以上入れることはハード制約となっています。（通常は、実現が難しいと思われますので、ソフト制約とするのが常道です。）

なお、出来れば２回という意味で、２回以上は、ソフト制約にしています。

Q.月に１度は、２連休を入れたい、

 Ans.次の実装となります。

この職場では、規定によりハード制約です。（通常は、実現が難しいかもしれないので、ソフト制約としてください。）

Q.遅番の後長日不可としたい

 Ans.遅番・長日パターンを禁止すればOKです。

「xxxを不可」という場合には、単純のその「ｘｘｘパターン」を禁止にするだけでよいです。

反対に、「入りの後は明け」　のように、禁止ではなく望ましいパターンの場合の記述は、一般に、

「入りの後明けは禁止」

「明けの前に入りは禁止」

と、両方向から禁止制約にする必要があります。

今回は、禁止なので、そのパターンだけでOKです。

いずれにせよ、上手く動作しているかどうか、予定に書いてみて、あらゆる可能性を考慮したテストパターンを書きます。

そうして、意図通りにエラーが付いているのを見て、初めて検証が完了します。制約を最初から書く場合は、一つ一つ、ステップバイステップで、きちんと動く部品を積み上げていくこと姿勢が肝要となります。

Q 予定制約レベル１が求解テーブルに出現するのですが？

 Ans.

■予定制約レベル１は、予定をソフト制約化した覚えがなくても出現することがあります。

■出現の可能性があるのは、下記オプションをチェックし、かつ先月部で、スタッフ毎のシフト設定等のハード制約と、予定との矛盾の可能性があるときです。その場合、GUIが自動でそのセルをソフト制約レベル１にソフト制約化します。

■スタッフ毎のシフトは、ハード制約です。一方、先月予定もハード制約が普通なので、先月予定部が矛盾が起こり「解がない」事態となることがあり得ます。これを回避するオプションをチェックしたときに、起こり得ます。

■矛盾が無ければ、選択してハード制約化してもOKです。

CAI教授のLocalMIP

 An Efficient Local Search Solver for Mixed Integer Programming

を見ると、これは凄いなと思ってやってみました。

しかし、スケジュールナースと比べるべくもありませんでした。

確かにこの発想は、今までになかったものです。Gurobiが速いのは、Heuristicsが速いからだ、という噂もある位で、有効なUB解を早く見つけるのは、MIP解法においても有効です。Feasibleな解を早く見つけるのには、有効ですが、厳密解に近いところを見つけるのは、苦手のようです。MIPはリニアソルバが鍵となっており、そこと絡めないと厳密解に近いところは、原理的に難しいのでは？と思います。リニアソルバと平面削除法は、長い長い歴史の積み重ねがあるので、ここに立ち向かうのは勇気があります。ニッチの分野になるかもしれませんが、知見を積み重ねて改善されることを期待したいと思います。

n100w8_0_0-1-7-8-9-1-5-4が解けた

 INRC2の難問インスタンスの内の一つの最適値が確定しました。これでOpen Instancesは、残り３となりました。

n100w8_0_0-1-7-8-9-1-5-4　LB:2030　UB:2030

です。

これを、解くのに4カ月かかってしまいました。これの何が難しいかというと、最適値である証明です。UB:2030は、比較的容易に得られますが、他にこれ以上良い解はこの世に存在しない、というのが大変難しいです。通常のBranch＆Boundでは、100万秒走らせたとしても証明は得られません。初期LB-UB　Gapは、１０以下であり、容易なように見えますが、実は難問中の難問です。

このインスタンスを解く努力を積み重ねることで、多くのことを学習し、また知見を得ました。で、このインスタンスで特徴的なのは、gap narrowing gain（私の造語）が極めて低いことにあります。その原因としては、構造的なsymmetryがあると思います。これを打ち破る方法としてsymmetry breakingがありますが、その方法については、また別な機会に。

Q.休日日勤者数を増員したい（Aチーム１名、Bチーム1名計2名）から3名にしたい

 Ans.

「保健所の監査がありｘｘ日の日勤は10名に増員したい」

では、単純な包含関係にあったので、制約追加で上手く行きました。

しかし、今回は、包含関係にないので、単純な制約追加では上手く行きません。

変更前記述は次のようになっています。

■次の関係　

増員日＋増員日でない＝休日　かつ　増員日∩増員日でない＝空集合

となる集合を作成します。

上の集合は、次で作成しています。

こういう、互いに交わらない集合で、足すと休日全体集合となる集合を排他集合と言います。排他集合は、互いに交わることがないので、ダブりがなく、なおかつ

足すと、休日全体になりますから、漏れがないということになります。

つまり排他集合で作れば、ダブりや漏れがなく制約できるということです。カレンダを両者をよく見比べて、排他的であることを確認してください。

必要なDay集合が出来上がったので、制約して完成です。

メンテナンスは不要です。増員日がないときは、今月休日増員日は空集合となります。結果、「増員日以外」は、＝今月休日と一致します。

行制約 パターン制約と不等式制約のDay集合の違い

 よく間違える記述の例です。

不等式制約では、「今月」をDay集合とすることが多いです。制約中の「今月」の定義を見るには、マウスMiddleボタン（ホイールボタン）をクリックすると出てきます。

ちゃんと、今月になっていることが分かります。

一方パターン制約の場合は、「今月」にしてしまうと、先月からの続きの部分を無視してしまうことになるのでまずいです。

下の例では、6連続勤務禁止のパターンで、先月部26日からの5日間が、正しく動くためには必要ですが、先月部2日間のみとなっており、指定を間違えていることが分かります。

修正するには、「制約開始日5日前から」にすればよいのですが、面倒なときは、「自動設定」にしてしまいます。（この段階では、空白集合になってしまいます。ごめんなさい）

求解してプロジェクトを保存後再ロードすると、正しく置き換わります。

しかし、Day集合が意図通りになっていません。「表示開始日」が先月2日間分になっていることが原因です。

最大パターン分になるように「表示開始日」を修正します。

ようやく、正しく動くようになりました。

まとめ

１）制約を書くとき、Day集合、グループ集合について、集合を確認します。

２）制約を書いた後、一つ書いたら、直ぐに求解して動作を確認します。

３）行制約パターン⇒「今月自動」の活用

Q.看護クラーク・看護補助の扱い方？

 Ans.

固定した勤務で、平日のみに出勤することが決まっているならば、スタッフに入れない方がよいです。スケジュールナースは、決まっていないシフトを割り当てるソフトです。

ただし、その方が、カウント対象（例えば日勤者等）であるならば、入れる必要があります。ただし、その方を除外してカウントしてもよいときは、除外カウントして、やはり入れない方がよいです。

対象は出来る限り少なくした方が、求解速度は上がるので、上記目的外のスタッフは、下のようにチェックを外すか、行削除して、当該プロジェクトの対象スタッフではなくします。

Q.ペア制約名は、フルネームじゃなくて名字だけでもいいんですか？

 Ans.　制約名は、何であってもよいです。スタッフ名である必要はなく、例えば、AとBとかでもOKです。他の制約と区別できることが唯一の条件です。

ですのでユニークな名前にしてください。

例

プリセプタプリセプティで、スタッフ名12とスタッフ名13が、常にペアになって夜勤を行う例の記述です。「スタッフ名12」と「スタッフ名13」という固有名詞が含まれている必要はありません。制約名は、制約を特定するための目的のために存在するので、自由に名前をつけてください。名前がユニークでさえあれば、空白以外の何であってもOKです。

＜ペア制約について＞

現在、上記のように固有名を用いて記述は可能ですが、記述することは推奨しておりません。退職等でスタッフがいなくなるとエラーとなるためです。

GitHUBの挙げている例の通り、

スタッフプロパティシートを用いて、汎用化するスタイルにすることを推奨しています。

スタッフプロパティシートは毎月メンテすると思いますので、忘れることは少ないと思います。

Q .解約手続きの流れを教えて頂けますか？

 Ans.

マイクロソフトアカウントにログインして、

サブスクを停止してください。来月から課金されなくなります。

https://www.nurse-scheduling-software.com/japanese/service/pausing_subscription/

ご利用ありがとうございました。

Q.医師当直表 医師間でばらつきが大きいようなんですが..

 Q.下図、宿日直回数と休日拘束数とで、医師間のばらつきがいつもより大きいような気がします。何故でしょう？

Ans.　１２月勤務表では、１月年始も取り込んで作成している影響だと思います。（物理的要因です。）

試しに、制約最終日を１２月３１日に変更してみました。

上図をよく見比べると、医師間のバラつきは、

制約最終日            宿日直数　　休日拘束数

１月５日版　　　2－４　　　4－6

１2月31日版    　0－2　　　2－4

となっており、バラつき（偏差＝２）で変わっていません。全体が多くなっている傾向になっているだけ、ということです。これは、制約日数が5日だけ増えている影響とみることが出来ます。

この勤務表のスタッフプロパティシートは、制約区間全体に効いてくるので、適宜最適値に調整してください。

変更前

変更後

変更後の結果

エラーが殆ど無くなったので求解時間も数秒に短くなりました。

また偏差も2以下に収まっています。

休日の丸1日の宿日直、あるいは休日拘束1回に対してカウントは、２です。つまり、回数に直すと1回の偏差となります。この1回の偏差は物理制約による限界です。全員が偏差0とするには、

Σ宿日直％医師数==0

になる必要があります。平たく言うと、端数が0になる必要があります。逆に言えば、全員が偏差0となるには、端数0となるときだけです。

例えば、宿日直コマ数総和40に対して、医師が10人いれば、全員4回で均等にできますが、41の場合は、割り切れず、必ず偏差が１となります。5回行う方が1人だけ生じます。

つまり、1回の偏差が生じるのは物理限界であって、なんら不思議ではありません。

First Order GPU実装

大変、参考になる論文が出ました。 

2311.12180

PDLPは、諦めていたのですが、GPU実装を使えば、可能性があることが示されています。最近のGurobiもGPUを使い始めたのは知りませんでした。

Simplex、内点法、FirstOrderの比較考証もされています。Simplexのマルチスレッド化は、LU分解のパラレル化が困難でした。Julian Hall教授の実装もありますが、CPUキャッシュに収まりきれないと性能が出ない問題があります。また、従来IPMにしてもスパースコルスキー分解を上手くGPUに載せるのは、難しいと考えられてきました。

ここにきて、FirstOrderは、激しく性能向上争いが続いていて、ADMMを用いた方法も注目しています。

An Enhanced Alternating Direction Method of Multipliers-Based Interior Point Method for Linear and Conic Optimization | INFORMS Journal on Computing

以上のトレンドを鑑みて、GPUによる実装を検討してみようと思います。（あくまで記録更新用なので、一般の実装には影響しません。ABIP+にせよPDLPにせよ、ユーザにとっては、精度と速度が出れば何でもよいです。）

＜Simplexは必要ないか？＞

依然として必要です。なぜなら、HotStart（WarmStart）によく駆動は、Simplexによるからです。INRC2規模では、Simplexのhoststartによる方が速いのでSimplexは欠かせません。一方、超大規模、SchedulingBenchmarksのInstance23/24規模になると、SimplexはHotstartを使っても無力です。この場合、内点法かFirstOrderによる方法となります。（FirstOrderによるHotStartは、Starandmarkさんの論文にあるのですが、大して効果がなかったような印象が残っています。）

上記論文で使われているGPUは、とんでもなく高価なものですが、上のような背景の私の用途としては、普通の世代落ちしたもので十分効果があるだろう、と見ています。

CUDAが使えるＧＰＵは、以下のページで分かります。

CUDA GPUs - Compute Capability | NVIDIA Developer

とりあえず、GPUを購入して勉強・評価して、COPTを使用するかどうかを判断したいと思います。

AIの流行により、一気に花開いたGPUですが、アークテクチャを見ると、ハードウェアとソフトウェア（コンパイラ技術）の見事なバランス感覚で成り立っており、両分野に精通した人の設計なんだろうな、と思います。CPUでマルチスレッドにするとキャッシュメモリがボトルネックとなり、その部分を分離できるという意味においても一時の流行に終わることがなく、今後も汎用化が加速していくのでないかと推測します。

特集 3-1　大規模深層学習のGPUへの実装技術

ZOOMの録画が変わった模様

 今まで、ユーザさまのPCにローカルファイルで保存することを推奨してきたのですが、その選択がなくなり、勝手にクラウドに録画される仕様に変更になったみたいです。

で、この録画、AI要約があったり、文字起こしがあったりで、再度見たい箇所を素早く探すことが出来るようです。ダウンロードではなく、パスコードリンクを送ることで、ユーザさまも文字起こし付のサイトで視聴できる、ということのようです。

AI要約は、次のレベルでまだまだ、です。

次は、昨日行ったAI要約です。

--

ミーティング後、ユーザさまにパスコード付きのリンクを私菅原氏とｘｘ氏は、クラウドレコーディングシステムの導入やスタッフの休暇管理、システムにおける制約の重要性について話し合いました。 また、スケジュール変更のプロセス、ソフトウェア制約の使用、スタッフ定義を設定し、過剰と不足を調整することの重要性にも焦点が当てられました。 会話は、新しいシステムの実装、複雑な制約に対応できるシステムの必要性、ソフトウェア制約を維持することの重要性について議論で終わりましたが送れば、ユーザさまの視聴が可能です。

菅原さんとｘｘさんは、Excelの使い方をｘｘさんに教えることに焦点を当てた4時間のセッションを行い、菅原さんが指導や制限事項を提供しました。 セッションは、菅原が後でｘｘにファイルを送ることを約束して終了しました。 両参加者は、このセッションに感謝の意を表しました。

--

プロジェクトファイルが、全く動かない状態からのスタートでした。なので、制約を一から作りこむレクチャを行いました。

■仕様の聞き取り・確認

■頂いたプロジェクトファイルをベースにしながら、一から制約を作りこんでいきました。

■特に留意する点、注意事項など、その都度、質問を受けながら

■全ての実装したい制約を実装

し、その場で、ブランク予定でエラー０まで実装確認を行いました。

知人からの紹介とのことで、「知人のプロジェクトファイルをベースに、サブスクをご契約頂いて著書も購入したけれでも、全くどうすればよいか分からない」

とのことでしたが、出来栄えにご納得頂けたと思います。気づけば４時間程経っていました。OJTで、なおかつプロジェクトファイルが出来上がりました。

勿論、ご自分で一から練習してみるのが最も大事、というお話しはさせていただきました。４時間分の録画はあるので、見たいところや聞き逃したところ等、見返すことが出来、これと併せて、その職場にマッチした最適な学習教材（当該プロジェクトの解説資料５０ページ添付）にもなったと思います。

が、これほど短時間に実装できるスケジュールナースは、

凄いな！スケジュールナース！

と改めて思った次第です。慣れれば最強は疑うところなし、です。

筑波大 繁野麻衣子先生

先生には、RAMP発表の折にお世話になっていて、ORの学術世界を垣間見ることが出来ました。著書も購入しています。

Amazon.co.jp: IT Text 数理最適化 : 久野 誉人, 繁野 麻衣子, 後藤 順哉: 本

この本は、分岐限定法と妥当不等式について解説している殆ど唯一の日本語本だと思います。

ふと巻頭言を見る機会がありました。

 https://web.archive.org/web/20200211213746id_/https://www.jstage.jst.go.jp/article/jsiamt/21/4/21_KJ00007731453/_pdf

-数 理 の 専 門家で ない 人 が ， 対象 を的確 に捉 え，必要 な とこ ろを抽象化 してモ デル を作成する こ とが で きれ ば， コ ン ピ ュ ー タの 性能が一段 と向上 してい る現在で は ， 我 々 の 研 究成果 が応用 され る機会が増す と考え る．誰 もが モ デ リン グの技術を身 に つ け るた め に は ， ど うすれ ば よい か 欲を言 え ぱ ， 数理 的な思 考 をと しない 人 に も対象を整 理 して モ デ リン グの 方向性が わか る よ うなそ ん な指針 を構築 したいと常 日頃考えて い る．

これは、私が常々、感じ考えていることと全く同じであります。ソフトの使い方以前に、考えを整理する術が必要です。

最近ZOOMレクチャを意図的に多くしています。（メール回答で終わらずにZOOMで解説）分からないことが分からない自分にとって、有益な機会であることが多いです。

1年のサポート中、大体が3回程度以下で済みます。プロジェクト作成で、私が生み出したバグもあるし、お客さまの仕様変更もあるし、ですが、その後は、殆どサポートしなくとも運用出来ているようです。

年末年始の実装その３

 今回は、実装その３です。

実装１の問題は、年始の予定を自動で考慮できないことでした。そこで、実装３では、予定範囲を拡大し年始を含んだ勤務表とします。

１）制約終了日を１月５日する

２）１２月の公休区間を作成する

従来の「今月」は、制約終了日を年始１月５日としたために、１２月１日ー１月５日が「今月」扱いになってしまいます。このため、公休数区間は、１２月１日－12月３１日となるように新たに定義します。

新たな定義をした集合名が「今月区間」になります。ちゃんと１２月１日から１２月３１日までにマーキングされていますね。これは、スケジュールナースに組み込み済み定義「次月」という集合から作った「次月でない」と従来の「今月」のANDを作ることによって作成しています。これで、メンテナンスフリーとすることが出来ます。（１月勤務表では、空集合です。結果、今月＝＝今月区間と自動的になります）

３）公休数を制約しているところを「今月」⇒「今月区間」に置き換えてやります。

夜勤数については、従来通り「今月」なので、１２月１日ー１月５日区間での夜勤数になることに注意してください。

４）スタッフプロパティシートを調整する

夜勤数は、年始まで含んだ夜勤数になるので、普段より多めに設定する必要があります。

公休数については、普段通り、１２月の公休数を入力します。

５）オプション　

以上が基本の枠ですが、多分、年始の各スタッフの夜勤数については制約する必要があるでしょう。

次のその実装例です。

年始分の夜勤回数をスタッフプロパティシートかマクロで制約します。スタッフプロパティシートで行う分には、使わないときに、ブランクにするメンテナンスが必要になります。

次は、マクロで行う例です。

この意味は、J4（次月集合）数をカウントし（関数C()）０だったら、０を採用、０でなかったらD4（＝１）を採用という式になっています。これはメンテナンスフリーにするための処理文です。

マクロでは、メンテナンスフリーに出来ますが、スタッフ毎の調整が出来ません。

一長一短です。このほかに、出てきた解を予定で調整してしまうのもアリだと思います。

どれを使ってもOKです。自分が分かり易い方法が一番です。

以上３回に渡って年末年始の実装を解説しました。