Instance15 解析ツール

 ログ解析用ソフトを制作しました。ログを読み込んでBranchTreeを作ります。

"""

ブランチログから Branch Tree を DOT 形式で出力するスクリプト

対象行:

  <cpu>(cpu sec)  Selecting Child Node id=0: Br:De:d N:n D:day S:shift Dir:dir Obj:obj [Gain:g]

  Adding Node thr=0 Br:De:d N:n D:day S:shift Dir:dir Obj:obj [Gain:g]

木の組み立て規則:

  - Selecting (De:0) が ROOT ノード。

  - Adding Node は「直前に Selecting されたノード」の子として登録（未探索ノード）。

  - Selecting は、同じ (De,N,D,S,Dir) で Adding 済みのノードがあればそれを探索済みにする

    （バックトラック時もこれで正しい親につながる）。

    無ければ新規ノードを作り、直前に Selecting されたノード（深さ De-1）の子にする。

    深さが合わない場合は、深さ De-1 で最後に Selecting されたノードを親にする。

使い方:

  python branch_tree_to_dot.py instance15_log_simplified.txt

  python branch_tree_to_dot.py log.txt -o tree.dot --render svg --rankdir LR

  python branch_tree_to_dot.py log.txt --max-depth 20     # 深さ20以下のみ表示

"""

Selecting以下を読み込んでBranchTreeをDOT形式で出力します。

全部をDrawする画像化は無理なので、Depthを制限して表示しています。

これで、何が嬉しいかというと、BranchTreeの様子を視覚的に確認できる、のでボトルネックを把握しやすくなる、ということになります。

Instance15に関しては、厳密解の証明のためには、現開発中のソルバでも一週間ほどかかります。これをなんとか短くする方法を思案するのに、有効なツールです。

解収束の様子は、下図になります。

Instance15は、昨年、菅原システムズによって厳密解が示されるまで、十余年に渡って厳密解が知られていなかったインスタンスになります。それでも、3分程でLB-UBGapが1%程度の実用解に達していることが分かります。

不確実性下での看護師スケジューリング

 An analytics-driven optimization framework for nurse scheduling under uncertainty

🩺 要約：不確実性下での看護師スケジューリング最適化フレームワーク

1. 研究の背景

• 看護師の欠勤（突発的な病欠・緊急対応など）は 5〜10% と高く、特に病院や救急では 10.7% と最も高い。

• 従来のスケジューリングは「決まった条件を満たす」ことに集中しており、 欠勤の不確実性を十分に扱えていない。

• 欠勤が発生すると、業務負荷の偏り・ケア品質の低下・スタッフの不満が発生する。

2. 本研究の目的

従来の「均一な余剰配置（overstaffing）」ではなく、 欠勤が起こりやすい“クリティカルなシフト”を特定し、そこに重点的に余剰人員を配置する データ駆動型のスケジューリングモデルを提案する。

3. 提案手法の構成（3つの柱）

① データ駆動型の「クリティカルシフト」分析

• 過去の欠勤データから、曜日×シフト（朝・夕・夜）ごとに欠勤率を計算。

• 欠勤が多いシフトに criticality score（重要度） を付与。

• 例：月曜朝・週末夜などが高リスクになりやすい。

② クリティカルシフトを組み込んだ MILP 最適化モデル

• 従来の「均一に余剰配置する」方式を廃止。

• criticality score に応じて余剰配置を優先するように目的関数を修正。

• 余剰配置量にも上限を設定し、過剰な overstaffing を防止。

③ 欠勤発生時のリアルタイム再配置（Overflow Unit Heuristic）

• 余剰配置された看護師を「Overflow Unit（予備ユニット）」として確保。

• 欠勤が発生したら、Overflow Unit から必要な資格を満たす看護師を再配置。

• 特徴：

  • 再最適化不要（高速）

  • 最小限の変更で対応

  • 資格レベルの低い看護師から Overflow に回すことで柔軟性を確保

4. 実験結果（概要）

• 実データを用いて、従来モデル（均一 overstaffing）と比較。

• 提案モデルは以下の点で優れていた：

  • 欠勤発生時の カバー率が向上

  • スケジュールの 安定性が向上

  • 看護師の 希望・公平性・経験バランスも維持

• 特に欠勤が多いシフトでの効果が大きい。

5. 本研究の主な貢献

• クリティカルシフトに基づく余剰配置戦略の提案（既存研究にない視点）

• 汎用的な MILP モデル（病院ごとに制約を調整可能）

• Overflow Unit による高速な欠勤対応アルゴリズム

• 予測モデル（Hurdle Model）による現実的な欠勤シナリオ生成

6. 一言でまとめると

欠勤が起こりやすいシフトをデータで特定し、そこに余剰人員を重点配置することで、 スケジュールの頑健性と実運用の柔軟性を大幅に高めるフレームワークを提案した研究。

Maching Learningによる修正

南山大学　先生方による論文 です。

JSME-TJ

✨ 本論文の要約（A solution method of nurse scheduling problem using machine learning）

1. 研究の背景

• 看護師の勤務表作成（ナーススケジューリング問題）は、依然として多くの病院で手作業で行われている。

• 数理最適化（MIP）による自動生成手法は多数存在するが、現場の看護師長が持つ暗黙の条件（hidden conditions）を満たせず、実用化が進んでいない。

• 暗黙条件の例：看護師同士の相性、連続勤務の微妙な調整、病棟特有の慣習など。

2. 研究の目的

• 数理最適化（MIP）＋機械学習（DNN）を組み合わせたハイブリッド手法により、

  • 暗黙の条件を学習し、

  • 看護師長が受け入れられる勤務表を自動生成すること。

3. 提案手法の概要

ステップ構成

1. MIPで初期勤務表 S を生成

2. 看護師長が不満な部分を修正 → F（修正後勤務表）

3. S を入力、F を教師データとして DNN を学習

4. 学習済み DNN が勤務表を自動修正

5. 修正が不要になるまで 2〜4 を繰り返す

→ 看護師長は暗黙条件を言語化する必要がなく、修正作業そのものが学習データになる。

4. 暗黙条件を模擬する「仮想看護師長問題（VCNP）」

• 実験前に、暗黙条件を数理的に模擬するために VCNP を構築。

• VCNP は「看護師の相性」などの隠れた条件を含む MIP。

• VCNP の解を DNN の教師データとして使用し、暗黙条件を学習させる。

5. シミュレーション結果

• 20名・28日間の小規模問題で検証。

• DNN の損失（MSE）は 約20回の反復でほぼゼロに収束。

• 学習後、異なる初期勤務表を入力しても、

  • 相性の悪い看護師が同じシフトに入らない

  • その他の制約も破らない といった「暗黙条件を満たす勤務表」が自動生成された。

• 1回の反復は約20秒で実行可能。

6. 実際の病院での実験（藤田医科大学ばんたね病院）

• 看護師長が実際に勤務表を修正し、その修正を DNN が学習。

• 結果：

  • 約20回の反復（約30分）で看護師長が受け入れる勤務表を生成

  • 従来は勤務表作成に 6時間以上かかっていた

  • 学習後は、別の初期勤務表でも 即座に受け入れ可能な勤務表を生成

→ 現場での実用性が高いことを確認

7. 結論

• 提案手法は、数理最適化では扱えない暗黙条件を DNN が学習することで、現場の看護師長が受け入れる勤務表を生成できる。

• 実験では、手作業の負担を大幅に削減できることが示された。

• 今後は、より複雑な暗黙条件や実運用システムの構築を進める予定。

8. 本研究の意義

• 数理最適化と機械学習のハイブリッドは、人間の暗黙知を取り込む新しいスケジューリング手法として有望。

• 医療現場の働き方改革に寄与する可能性が高い。

CLPとCOPT 8.03 Barrier Solver 比較

 COPTのライセンスが切れる前にデータ採取した結果を次に示します。下表は、現在開発中のSolverで、同一インスタンスに対して、両者の求解時間を比較したものです。厳密解証明完了までの時間です。Instance9とInstance15、それからinstance22以降は、簡単に求まらないので外しています。

CLPによる求解時間を1としたときの結果です。上の結果を正規化しました。

考察

市井のナーススケジューリング問題の規模は、大体４Weeks、Staff30名のインスタンス8程度以下になります。そうした規模のインスタンスでは、CLP（Simplex）が圧倒的です。つまり、通常のナーススケジューリング問題規模では、商用ソルバを必要としません。

Barrier　Solverが効いてくるのは、上表黄色のインスタンスで、規模の大きなインスタンスになります。特に、Instance20以降では、指数関数的に規模が効いてきて、Simplexは、現実的ではなくなります。

従って、問題規模によってLpSolverを切り替えるのが実装としてReasonableです。規模の指標は、行数、列数とも考えられますが、Claude　Codeのお勧めは、NNZでした。NNZは、OSIのIFでは、下式で、求められます。

int nnz = osi.getNumElements();

HPR-LP-CがCuoptよりも速そう

 plato.asu.edu/ftp/lpfeas.html

によるとHPR-LP-Cが1位になっていました。

GitHub - PolyU-IOR/HPR-LP-C: HPR-LP-C: A C implementation of the Halpern Peaceman--Rachford (HPR) method for solving linear programming (LP) problems on GPUs. · GitHub

COPT Barrier Solverの評価ライセンスがもうすぐ終わるので、後継を考察しておきます。GPUを使うことを前提にすれば、First Order系の進歩が著しいので、可能性が出てきました。前にPDLP-CのCPU版を見たときは、使えないと判断しましたが、精度向上と速度向上により将来の可能性は高まりました。Cuoptのライブラリを使っているとWindows Portが実質的に困難ですが、その点は問題なさそうです。

<PDLP-Cとの違い>

2つをリポジトリで確認した結果をまとめます。cuPDLP-Cの実質的な後継であるcuPDLPx（MIT Lu Lab）も、比較のために並べておきます。

項目	HPR-LP-C	cuPDLP-C	（参考）cuPDLPx
アルゴリズム	Halpern Peaceman–Rachford（HPR）	PDHG＋適応ステップ＋KKTリスタート	Halpern PDHG＋PID制御の重み調整
既定の精度	1e-6	1e-4（primal / dual / gap それぞれ）	1e-4程度
実行不能・非有界の判定	なし（OPTIMAL / 時間制限 / 反復制限 / エラーのみ）	あり（INFEASIBLE / UNBOUNDED）	あり
初期解（warm start）	なし	公開APIにはなし	あり（set_start_values）
presolve	GPU-Presolver-C（folding付き）またはPSLP	HiGHSのpresolve	PSLP
GPUなしでの実行	不可	CPU版をビルドできる	不可（AMD GPU / ROCmには対応）
高速化の工夫	行列構造に合わせた専用SpMVカーネル、CUDA Graph、反復中の行・列の縮約	cuSPARSEの標準的な呼び出し	cuSPARSE / hipSPARSE
バッチ求解	あり（行列Aが共通の問題群）	なし	なし
制約の書き方	AL ≤ Ax ≤ AU（範囲制約をそのまま書ける）	Ax=b と Gx≥h（範囲制約は変換が必要）	l ≤ Ax ≤ u
外部依存	CUDAとzlibのみ	HiGHS 1.6とCUDA 12.3	CUDA（またはROCm）
Windows	未対応（forkなどの修正が必要）	_WIN32 分岐が一部にあり、比較的移しやすい	未確認
開発状況	活発（v0.1.3、2026年）	2024年12月で更新停止	活発（2026年9月まで更新）
ライセンス	MIT	MIT	Apache 2.0

<Windows Portの可能性>

結論から言うと、Windowsへのポートは可能で、ポート不能な箇所は見当たりませんでした。リポジトリ（main、全41コミットの履歴を含む）を確認しましたが、cuOptのライブラリは使われていません（cuopt / RAFT / RMM への参照はゼロ）。依存しているのは CUDA Toolkit 標準の cuSPARSE・cuBLAS・cuSOLVER・Thrust/CUB と、同梱の PSLP、GPU-Presolver-C、zlib、HDF5（任意）だけです。これらはすべてWindows版があります。

cuOptを使っていたら、確かに厳しいところでした。cuOptは公式にはLinux専用なので（Windowsで動かすにはWSL2経由）、ネイティブ移植の障害になっていたはずです。

ただしLinux前提の書き方をしている箇所がいくつかあり、手を入れる必要があります。

要修正（コード）

• src/presolve/pslp_integration.cpp：いちばん大きな作業です。PSLPのpresolveを fork() と pipe() で子プロセスに隔離して実行し、waitpid で後始末しています（<unistd.h>, <sys/wait.h>）。直し方は2通りです。
  • 簡単な方法：同じプロセス内で直接呼ぶ。隔離はなくなるので、PSLPがクラッシュすると全体が落ちます。
  • 同じ挙動を保つ方法：CreateProcess と匿名パイプで作り直す。ただし fork はメモリを丸ごと引き継ぐので、Windowsでは入力モデルをシリアライズして子プロセスに渡す処理が必要になります。
• GPU-Presolver-C/.../presolve_structs.hpp：__builtin_huge_val() がGCC拡張です。std::numeric_limits<double>::infinity() に置き換えれば済みます。
• PSLP本体：_WIN32 分岐が最初からあるので、Timer と thread はそのまま通ります。

要修正（ビルド系）

• CMakeLists.txt：g++-12/11 を探してホストコンパイラにし、-Xcompiler -fPIC や -D_GLIBCXX_USE_CXX11_ABI=0、-O3 -w といったGCC専用フラグを付けています。MSVC（Visual Studio）用の分岐が必要です。
• GPUアーキテクチャの自動検出：scripts/detect_cuda_arch.sh をbashで呼んでいます。Windowsでは -DCMAKE_CUDA_ARCHITECTURES=89 のように明示的に指定するのが簡単です。
• Makefile：Linux専用なので、CMakeだけを使います。
• zlib / HDF5：vcpkgで入れられます。HDF5はなくてもビルドできます。

確認が必要な点

• CUDA 13.3以上では実験的API cusparseSpMVOp が使われます。Windows版cuSPARSEにこのAPIがあるかは確認していません。もしなくても、旧来の cusparseSpMV に切り替わる仕組みがあるので、ビルドは通るはずです。
• CUDA Graph、cuSPARSE、cuBLASなどはWindowsでも普通に動きます。
• READMEの動作要件は「Linux x86-64」としか書かれていません。Windowsはテストされていないので、動作確認は自分でやる必要があります。

作業量の目安としては、ビルド系の修正と fork の置き換えがほとんどで、数百行程度の変更で収まると思います。まず動かしたいだけなら、WSL2上でLinux版をそのままビルドするのが一番早いです（GPUもそのまま使えます）。

Instance18計測

開発版で、

CLP:227sec

COPT Barrier:842sec

となりました。これは、厳密解を得るまでの時間です。今までのスケジュールナースを含めて世界最速だと思います。MIPソルバでは、恐らく厳密解を得るのも容易ではありません。

この値に近い値は、現リリース版でも確認ができると思います。

＜考察＞

１）この規模では、未だSimplexの方が優位ということだと思います。Barrier Solverが優位になるのは、Instance21～と思います。

２）このインスタンス、実は曲者で、単純な方法で、厳密解を得るのは難しいと思います。

スタッフプロパティ項目設定だけでは制約にならない

  次のようなスタッフプロパティシートで、F1というシフトの可否を選択しているように思いますが、このままでは、何の効力もありません。

スタッフプロパティーシートの項目は、項目を記述しているだけで、制約を記述していることにはなりません。F1不可にしたいならば、F1不可にする制約を行制約もしくは列制約で、ユーザ自身が、記述する必要があります。

F3業務についても同様です。

＜スタッフ毎のシフトとの違い＞

一方、スタッフ毎のシフトは、全期間に作用するハード制約です。先月にも効いてしまうので、先月F1勤務した人が、今月F1勤務のチェックを外した場合は、ハードエラー（解のない状態）となってしまいます。

スタッフ毎のシフトは、恒久的な制約記述に向いています。過去も未来もF1勤務をやることがない場合は、スタッフ毎の勤務のチェックで記述するのが楽です。

それに対して、月でシフト業務を変更したり、あるいは、ソフト制約にしたい場合は、スタッフプロパティ＋制約で、記述するのが正解となります。