ラベル設定法状況

 改善中途での状況です。instance24では、およそ150sec程度かかっており、LBまで1日では到達しません。未だ未だ改善が必要です。

月を跨いでの6連勤に注意

 入明休と入明入明休みが混在するパターンでは月を跨いでの6連勤に注意が必要です。

パターン1は、通常の2交代パターンです。　4連勤の後に入りで終わると、来月初日は明けとなり、必ず6連勤になってしまいます。

今回、日宿日パターンがあるので、宿の後さらに日が入る可能性があります。これは、パターン１に同じです。

また、入明入明休の場合は、さらに前の日から見る必要があります。

まとめると、次のような実装になると思います。

Q.入明休と入明入明休みの2パターンがある場合の記述の仕方

 Ans.　下のように状態遷移図を書いて考えます。

この結果、入りの後は、明けしかないことが分かります。また、明けの前は常に入りです。なので、この部分に関しては、2交代通常パターンを流用でOKです。

問題は、明けの後休みとなったり、再び入りとなる二つのパターンが存在することです。

明け後、（入りまたは休み）以外　を禁止にすることで対応出来ます。

入りまたは休みシフト集合を作ります。

また、パターンは2回までしか許容しないとのことなので、3回連続入りを禁止にすればOKです。

以上をまとめたのが次の記述となります。

テストは、適当に、予定を散りばめます。

解を確認して完了です。

Q.宿パターン

 Q.宿直に入る場合の基本パターンを日→宿→日→休にしたい。

Ans.

特殊なシフト「宿」を中心にして、その前後を考えます。すると、次のようなルールが浮かびます。

これを行制約として記述すれば、よいです。例えば、

宿の後は日は、（宿の後、日でない＝✓マーク日）のは、禁止、

（宿の前、日でない＝✓マーク日）のは、禁止

とします。

宿日休みは、日をブランクにしていますが、勿論、宿日と記述してもOKです。

これで、パターンのテストを行います。が、行制約として記述するだけでは、パターンが出現しないかもしれません。なので、予定として記述してみます。

これに対して、解は、

ちゃんと、日宿日休パターンになっています。

注意すべきは、今回設計したこのパターンは、ハード制約ということです。この制約をハードとすべきかソフトとすべきかは、勤務表ルールの設計者によります。

Q.同日の希望勤務を複数登録

 Q.同日の希望勤務を複数登録（第１希望、第２希望等）

Ans.

GUIでは出来ません。

どうしてもやりたいということでしたら、Pythonを使わざるを得ません。

１）制約→Python..を開いて、import sc3を記述、 設定ボタンを押します。

２）言語の使用を✓します。

３）求解してソース全体を開きます。

これは、GUIで記述したところの内容をPython記法で記述した変数群になっています。日本語で記述しているように見えますが、Pythonでの正式な変数になっています。注意するのは、Pythonで使用不能な文字は、別な文字に置き換えられていますので、そちらを使う必要がある、ということです。どういう風に置き換えられたかは、このページを見ないと分かりません。

４）ソースに記述して行きます。例えば、スタッフ名１の2020年7月3日の勤務を第一希望入り、第2希望公休にしたいとします。その日のシフトVarを出して、AddSoftすればOKです。

記述してSyntaxError等のデバッグをした後、レベル７と５について、✓します。重みも欲しい重みに変更します。

重み５のエラーが1個出ていることに注意してください。

スタッフ１の第一希望（入り）が優先された結果（公休：重み５）が採用されなかったためです。

以上は、全てをPythonで記述しましたが、GUIで第１希望、Pythonで第2希望としても記述可能です。

このあたりもAIで記述可能なようにしたいですね。

パルスアルゴリズム

一瞬パルスアルゴリズムに目移りしましたが、以下の通りの弱点があるので採用しませんでした。

なお、パルスアルゴリズムのC++実装は、 

https://github.com/lyandut/MyPulseForCSP/tree/master

にあります。

パルスアルゴリズム（Pulse Algorithm）は，ラベル設定法（Label-Setting）を“極限まで強化した双方向分枝限定法”であり，

主目的は「厳しい資源制約付き最短路問題（RCSPP）」を高速に解くことです。 特徴は“ラベルを保持しない（＝DP表を持たない）”点にあります。

以下，RCSPP 文献で確立している標準的なパルスアルゴリズムの構造を，実装レベルまで整理します。

🔥 パルスアルゴリズムとは何か（要点）

• 深さ優先探索（DFS）＋強力な枝刈り（pruning）

• ラベル（DP状態）を保持しない → メモリ使用量が極端に小さい

• 資源制約（時間・コスト・勤務回数など）を満たすパスのみ探索

• 下界（Lower Bound）と上界（Upper Bound）を使って強力に枝刈り

• 列生成の pricing subproblem（RCSPP）で世界的に最強クラス

🧠 アルゴリズムの基本思想

パルスアルゴリズムは，ノード v に到達したときに次の 4 種類の枝刈りを行います。

1. 資源制約による枝刈り

累積資源 $r$ が上限を超えたら即終了。

2. 下界（Lower Bound）による枝刈り

ノード v からゴールまでの最良下界 LB(v) を事前計算しておき，

$$\text{current\_cost}+LB(v)\ge UB$$

なら探索を止める。

3. 支配（Dominance）による枝刈り

同じノードに到達した過去のパスより劣っていれば枝刈り。

4. サイクル（Cycle）除去

DFS なので，訪問済みノードを再訪しない。

⚙️ パルスの流れ（擬似コード）

pseudo

Pulse(v, cost, resources):
    if resources violate constraints:
        return

    if cost + LB(v) >= UB:
        return

    if dominated(v, cost, resources):
        return

    if v == target:
        UB = min(UB, cost)
        return

    mark v as visited

    for each arc (v → u):
        Pulse(u, cost + w(v,u), resources + res(v,u))

    unmark v

📌 ラベル設定法との違い

項目	ラベル設定法（DP）	パルスアルゴリズム
状態保存	多数のラベルを保持	ラベルを保持しない
探索	幅優先/最短路型	深さ優先（DFS）
メモリ	大量に必要	極小
枝刈り	資源制約＋支配	資源＋支配＋強力な下界
列生成との相性	良い	最高レベル

なぜ“パルス”と呼ばれるのか

探索が パルス（pulse）＝波のように深く進み，戻り，また進む という動きをするためです。

🧩 列生成（Column Generation）との関係

RCSPP は pricing subproblem として頻出します。

• RMP から得た DUAL を使って reduced cost を計算

• パルスは reduced cost < 0 の列 を高速に発見

• 特に 資源が多次元（勤務回数・連続勤務・休暇制約など） の場合に強い

パルスアルゴリズムの弱点は、強力な枝刈りと深さ優先探索による“爆発的な速さ”の裏側に、いくつか本質的な脆さがある点です。 強いところは極端に強いが、弱いところは極端に弱いという、かなりピーキーなアルゴリズムです。

以下、研究者・実装者の視点で“本当に問題になる弱点”だけを整理します。

🎯 結論：パルスアルゴリズムの主要な弱点（重要度順）

1. 下界（LB）の質に強く依存する

パルスは「LB が弱いと一気に破綻」します。

• LB が弱い → 枝刈りが効かない

• 枝刈りが効かない → DFS がほぼ全探索化

• 全探索化 → 指数時間で爆死

つまり、

LB が強いと最強、弱いと最悪

という極端な性質を持ちます。

孝幸さんのように ZDD や DP で強い LB を作れる人には向いていますが、 一般の実務者には扱いが難しい理由がこれです。

2. 資源次元が多いと急激に弱くなる

資源次元が増えると：

• 支配判定が効きにくくなる

• LB の計算が難しくなる

• DFS の探索空間が爆発する

特に 5 次元以上の資源制約では、パルスは急激に性能が落ちます。

3. 深さ優先探索ゆえに“運が悪いと”最悪ケースに落ちる

DFS は探索順序に依存します。

• 良い順序 → 最適解にすぐ到達 → UB が早く更新 → 枝刈りが効く

• 悪い順序 → 最適解に全く届かない → UB が更新されない → 枝刈りが効かない

つまり、

探索順序の設計が悪いと、指数時間に落ちる

4. 並列化が難しい

DFS＋強い枝刈りという構造は、並列化と相性が悪いです。

• スレッド間で UB を共有する必要がある

• 探索順序が変わると性能が大きく変動

• LB の更新も同期が必要

結果として、

パルスはマルチスレッド化してもスケールしにくい

 

5. 実装が難しい（バグりやすい）

パルスは：

• 支配判定

• LB の適用

• UB の更新

• サイクル除去

• 資源制約のチェック

など、複数の枝刈りが複雑に絡むため、 少しでも条件を間違えると：

• 最適解を落とす

• 不正な枝刈りが起きる

• infeasible と誤判定する

という“致命的なバグ”が発生しやすいです。

6. 最適解が高コスト側にあると弱い

パルスは「良い UB が早く見つかる」ほど強い。

逆に、

• 最適解が高コスト

• 低コストのパスが存在しない

• UB がなかなか更新されない

というケースでは、枝刈りが効かずに弱くなります。

🧩 まとめ：パルスは“尖った武器”

パルスは、 LB が強く、資源次元が少なく、探索順序が良いときに最強 という、非常に尖ったアルゴリズムです。

逆に、

• LB が弱い

• 資源次元が多い

• 探索順序が悪い

• UB が更新されない

という状況では、 指数時間で破綻するという明確な弱点があります。

結論から言うと、パルスアルゴリズムはキャッシュ特性が“かなり悪い”部類に入ります。 これはアルゴリズムの構造的に避けられない弱点で、実際に実装してみると L1/L2 ミスが多発し、CPU の IPC が落ちやすいタイプです。

実装・最適化レベルで RCSPP を扱う人が気づくのは、むしろ自然です。

🔥 なぜパルスはキャッシュ特性が悪いのか（本質的理由）

1. 深さ優先探索（DFS）はアクセス局所性が低い

パルスは DFS でグラフを深く潜るため、

• 次にアクセスするノードが予測しにくい

• メモリ上で連続していないノードに飛ぶ

• CPU のプリフェッチがほぼ効かない

結果として、

キャッシュミスが多発し、メモリアクセスがボトルネックになる

これは BFS やラベル設定法（DP）と比べて明確に不利です。

2. ラベルを保持しない＝DP テーブルがない → 局所性が生まれない

ラベル設定法は DP テーブルを持つため、

• 同じノードのラベルを何度も参照

• メモリ局所性が自然に発生

というメリットがあります。

一方パルスは、

• ラベルを保持しない

• 状態をほぼ持たない

• 毎回新しいパスを深く探索する

ため、局所性がほぼゼロです。

3. LB（下界）テーブルへのアクセスがランダム

パルスの強さは LB に依存しますが、LB の参照は

• ノード v に到達するたびに LB[v] を参照

• DFS の順序はランダム

• LB テーブルのアクセスもランダム化

つまり、

LB が強いほど LB 参照が増え、キャッシュミスも増える

という皮肉な構造になっています。

4. 支配判定（dominance check）がランダムアクセスを増やす

支配判定は通常、

• ノードごとに「過去の到達状態」を保持

• DFS の順序に依存してランダムに参照

• 状態数が増えるほどキャッシュミスが増える

特に資源次元が多い場合は顕著です。

5. スタックが深くなるとレジスタ・L1 が圧迫される

パルスは深い DFS を行うため、

• 再帰スタックが深くなる

• ローカル変数が多くなる

• レジスタが足りず spill が発生

• L1/L2 キャッシュに溢れる

という現象が起きやすいです。

📌 まとめ：パルスは“キャッシュに優しくないアルゴリズム”

構造的に、

• DFS

• ランダムアクセス

• ラベル非保持

• LB 参照の多発

• 支配判定のランダム性

が重なるため、キャッシュ効率は悪くなるのが宿命です。

Q.勤務時間を制限する条件は使用しない方が良いのでしょうか

 Q週に35時間制限など、看護補助者向けの時間制限条件を希望される病院が多くなってきています。

Ans.

必要であれば、使って構いません。ただし、

■時間よりは、回数制限の方が求解時間では有利になります。

■時間制約はハード制約のみです。ソフト制約はありません。

なので、可能であれば、回数制約で記述可能ならば、回数制約にすることをお勧めします。