第3世代AL1(SAT)から第4世代AL3(LP)へ

 下記資料中、

Q.　4page 「人的リソースの物理限界まで配置が可能」とは、どういうことか？

質問を頂きました。

 https://www.nurse-scheduling-software.com/japanese/publications/Schedule_Nurse_Presentation_for_AI_modeling_and_state_of_the_art_solver.pdf

Ans.　

誤解を招く表現で申し訳ありません。正しくは、

「世界で一番、人的リソースの物理限界まで配置が可能」

です。絶対的な意味ではなく、相対的な意味になります。

そもそも、ナーススケジューリング問題は、規模が大きくなれば、組み合わせ爆発が生じ、リーズナブルな時間内には、解が求められない、ということが証明された問題分野（NP困難）にあります。このことが意味しているのは、「どんな規模の人的リソースでも物理限界まで配置可能」という命題は数学的には成立しません、ということです。

なので絶対表現ではなく、他と比較して相対的に、ということを意図していました。

では、具体的に何が違うのか？　アルゴリズム上の観点で、説明します。

AL1は、現在のスケジュールナースの基幹アルゴリズムで、SATソルバベースのアルゴリズムになっています。201ｘ年のMAXSAT Competitionで、4カテゴリ中3カテゴリで優勝しましたが、それをベースとして、これまで、進化してきました。

AL3は、現在もリリースされてはいますが、問題分野がアカデミックなベンチマーク専用という意味あいが強く、実務的な貢献は殆どされていません。そのコアアルゴリズムは、数理ソルバあるいは、LPベースのソルバ、世の中にある汎用最適化ソルバ(MIPソルバ）の類と同じ学問分野にあるアルゴリズムで、AL1のSATソルバベースとは全く動作原理が異なります。

AL1 は、通常規模のナーススケジューリング問題については、無類の強さを発揮しますが、規模が大きいかつソフトエラーが多発する問題は、弱いという傾向があります。この弱点がもっとも顕著に出るのがアカデミックベンチマークです。逆にこの弱点を克服するべく、未解決のアカデミックベンチマークを全問解くという目標を掲げ、実際最後の1問を残すのみという研究実績を積み重ねてきました。

この挑戦の過程で、多くの知見を得ることが出来ました。それを現在のAL1と同じく市井の実務問題を解くソルバに技術移転することが次の課題として残っています。この課題解決の後に、ユーザさまは、AL1/AL3、好きなソルバで作業することが出来るようになります。

規模が大きい、あるいは、ソフトエラーが多発する、あるいは、物理限界の極限まで、スタッフの希望休みを詰め込みたい、といった用途には、AL3を使用することになると思います。私の経験則は、ほぼすべての師長さんが、「スタッフの希望休みを全部(極限まで)詰め込みたい」ですので、勤務表リリース前の最終段階では、結局、AL3が使用されることになる、と見ています。

もう一つの誤解は、高速性です。求解が高速であることと、求解品質は、関連がありません。高速だけども低精度、つまり、スタッフの希望予定が切り捨てられる、では話になりません。これからの指標は、高速であることは勿論ですが、どれだけ、「スタッフの希望休みを全部(極限まで)詰め込めるか？」です。

このスケジュールナースのエンジンが広く行き渡れば、100万人いる？日本の全てのシフト看護師・介護師に恩恵があると思うので、1社に限定することなく、広く世の中で使われるように積極的にライセンス展開をして行きたいと思います。

ユーザさまよりメールを頂きました

永くお使い頂いているユーザさまより メールを頂きました。

＊＊＊

思えば、2016年ごろにスケジュールナースを見つけて、

使わせていただいてから、もう10年近くになります。

最初の頃は、記号記述のような制約入力方法と格闘していましたが、

すぐに、わかりやすいUIに進化して、性能も向上して、

次々と新機能も追加され、使いやすさがアップしていきました。

使えば使うほど、こんなこともできてしまうのかと、スケジュールナースの

ポテンシャルの深さには、今でも驚かされています。

幾度となく、厳しく複雑な勤務条件にも遭遇しましたが、

スケジュールナースの性能と柔軟な制約記述方法のおかげで

条件をクリアすることができて、勤務の質も看護の質も落すことなく

ベストを目指した勤務表作成ができています。

スケジュールナースと菅原さんには感謝しかありません。

本当にありがとうございます。

＊＊＊

永くお使い頂きありがとうございます。引き続いて、第4世代（新ソルバ）、第5世代（AIモデリング）を準備中です。現在、世界記録更新で最後の1問に苦闘していますが、この挑戦で得た知見をフィードバックして汎用実務問題で他を圧倒するスケジュールナースがさらに進化した版ソルバを今年中に、リリースしたいと思います。

また、検証・ご評価をお願いできればと思っております。宜しくお願い致します。

Q.6月以降のカレンダーが表示されない

Q. 5月の勤務表作成にあたり、制約日の設定をしようとしたところ

6月以降の制約終了日のカレンダーが表示されなくなりました。

開始日、終了日、表示日すべて６月以降の表示ができないようです。

設定等の変更の必要がありましたら、ご教示ください。

Ans.

古いエディションをお使いのようです。（ご案内が漏れていたようです。）現在リリース中のエディションは下記二つが全てです。

https://schedule-nurse.blogspot.com/2025/12/qprivate.html

上記以外のサポートは全て停止しました。

恐れ入りますが、移行手続きをお願いいたします。

グラフのフォワードとバックワードスキャン

 前回は、ボトムアップに構築しましたが、トップダウンで、構築する方法もあります。

ボトムアップと、トップダウン、Forward/Backwardという呼び名もあります。どちらが正解ということはなく、どちらでもよいです。

二つの方向から、計算するのは、ノードを削減するときです。

そのノードを通ると最適値を上回ることが分かっているなら、そのノードを削減出来ます。

ダイカストラのアルゴリズム

 下図は、グラフアルゴリズムの様子です。

親ノードは、T枝とE枝があります。T枝は、Then,E枝は、Else.　T枝、E枝の先は、子ノード

になります。子ノードの値（浮動小数）をval0,val1とするとき、親ノードの値は、

tval=val1+coeff1

eval=val0

if (tval≦eval) val=tval;

else val=eval;

最小化・最大化を≦の向きを変えることで、求めることが出来ます。

動的計画法とダイカストラのアルゴリズムは同じ意味？

 結論から言うと、これらは同じものではありません。

アルゴリズム３で中核となすアルゴリズムは、ダイカストラのアルゴリズムです。簡単に言うと、グラフがあって、その最短重み和の経路を求めたいとき、一度計算した結果をメモしておくやり方です。この考え方は、深宇宙通信で使われる符号化方式、ビタビアルゴリズムに本質的に似ています。と言うよりも、ビタビ教授自身、類似性を認めています。

ダイクストラ法は、動的計画法（DP）の考え方を利用したアルゴリズムの一つ、という関係性です。 っくりとした違いは以下の通りです。

• 動的計画法（DP）：大きな問題を小さな部分問題に分けて解く、「考え方の枠組み（手法）」のことです。
• ダイクストラ法：グラフの最短経路を求めるための、具体的な「手順（アルゴリズム）」のことです。
• イメージとしては、「料理（動的計画法）」という大きなジャンルの中に、「カレーの作り方（ダイクストラ法）」という具体的なレシピがあるような関係です。

ダイクストラ法は、「今の地点から一番近いところを確定させる」という手順を繰り返しますが、これは「過去の計算結果（確定した距離）を使って次の計算をする」という点で、動的計画法の仕組みに基づいています。 

Tiny Mip Solver

 Reduced Cost Fixing を各ブランチで適用していくTiny MIP Solverを作り評価しました。

しかし、解けたのは、Instance2位までで、その他は全く解けませんでした。

Highsや、COPTは、偉大と思った次第。

Reduced Cost Fixing

 数理最適化の文脈における Reduced Cost Fixing（縮小コストによる固定）は、混合整数計画問題（MIP）などの難しい問題を解く際に、「最適解においてその変数が取るべき値を事前に確定（固定）させる」ことで探索範囲を絞り込む手法です。

UBが既知のときに、

bitを反転させるコストがUBを上回るならば、bitを反転させることは、必ずUBを上回ることを意味するので、bitを反転させることはできない、→bit固定化できる、

LB＋反転ReducedCost＞UB　→ビット固定

ということになります。GAP＝UB-LBが小さくないと、UBを上回ることはないので、この手法が有効なのは、GAPが小さいときに限られます。逆にLB＝UBとなれば、極小さいReducedCostでもビットを固定化できるので、大量のFixedBitsを得ることが出来ます。そうなれば、MIP/SAT　ソルバ共簡単に解けるようになるので、出来る限りLBを上げること目指している訳です。

以下の説明では、Simplexを念頭に置いたBasic変数と非Basic変数に関する説明がされていますが、Simplexに限定されるものではなく、PDLP（FirstOrder）法、内点法等でも、成立します。

1. Reduced Cost（縮小コスト）とは

線形計画法（LP）において、ある変数が現在の最適解で 

$$

 であるとき、その変数を 

$$

 単位増やすために必要な「コストの増加分（または利益の減少分）」を指します。 

• 基本変数の場合： 縮小コストは常に 
  

  $$
   です。
• 非基本変数の場合： その変数が最適解に含まれていない理由（＝どれだけ損か）を数値化したものです。 

2. Fixing（固定）の仕組み

MIPを解く際、まず整数制約を無視した「LP緩和問題」を解きます。このとき得られる縮小コスト 

$$

 と、暫定解（現在見つかっている最も良い整数解）の目的関数値 

$$

、およびLP緩和の目的関数値 

$$

 を用いて以下の判断を行います。

• 論理： 「もし変数 
  

  $$
   を 
  

  $$
   にした場合、目的関数値が 
  

  $$
   よりも悪化することが確実であれば、その変数は最適解で 
  

  $$
   になることはあり得ない」
• 判定式： 
  
  
  
   （最小化問題の場合）
  • この条件が満たされる場合、変数 
    

    $$
     を 
    

    $$
     に固定（Fix）して以降の探索から除外できます。

3. この手法のメリット

• 探索空間の削減： 枝分かれ限定法（Branch and Bound）において、調べるべきノードの数を劇的に減らすことができます。
• 高速化： 特に変数の数が多い大規模な問題において、計算時間の短縮に直結します。

この手法は、多くの商用ソルバー（Gurobi, CPLEXなど）やオープンソースのソルバーにプリソルブ（前処理）やノード内での絞り込み戦略として標準的に組み込まれています。

C++疑似コードで。

2026年2月24日

C++ソルバー（Gurobi, CPLEX, SCIPなど）を想定した 

Reduced Cost Fixing の疑似コードを以下に示します。

この手法は、暫定解（現状の最高スコア）とLP緩和解（理想的なスコア）の差を利用して、逆転不可能な変数を切り捨てます。

C++ 疑似コード

cpp

#include <vector>
#include <iostream>
#include <cmath>

// 変数の状態を定義
enum class VariableStatus { FREE, FIXED_TO_ZERO, FIXED_TO_ONE };

struct Variable {
    int id;
    double reduced_cost; // LP緩和解から得られる縮小コスト
    double current_value; // LP緩和解における変数の値
    VariableStatus status;
};

/**
 * Reduced Cost Fixing を実行する関数
 * @param variables 変数リスト
 * @param z_lp LP緩和問題の目的関数値 (下界)
 * @param z_best 現在見つかっている最良の整数解の目的関数値 (上界)
 * @param is_minimization 最小化問題ならtrue
 */
void applyReducedCostFixing(std::vector<Variable>& variables, 
                             double z_lp, 
                             double z_best, 
                             bool is_minimization) {
    
    // ギャップ（あとどれだけ改善の余地があるか）
    double gap = std::abs(z_best - z_lp);

    for (auto& var : variables) {
        if (var.status != VariableStatus::FREE) continue;

        // 最小化問題におけるバイナリ変数の判定例
        if (is_minimization) {
            // 変数が現在 0 で、1 に変えた時のコスト増(reduced_cost)が 
            // ギャップを超えているなら、1 になることは絶対にない
            if (var.current_value < 1e-6 && var.reduced_cost > gap) {
                var.status = VariableStatus::FIXED_TO_ZERO;
                std::cout << "Variable " << var.id << " fixed to 0\n";
            }
            // 変数が現在 1 で、0 に変えた時のコスト増(-reduced_cost)が
            // ギャップを超えているなら、0 になることは絶対にない
            else if (var.current_value > 1.0 - 1e-6 && -var.reduced_cost > gap) {
                var.status = VariableStatus::FIXED_TO_ONE;
                std::cout << "Variable " << var.id << " fixed to 1\n";
            }
        }
    }

キャパシティカットの効果

 前回のキャパシティカットをScheduling Benchmarksのインスタンスに適用してみました。

LBとは、LowerBoundで、LPソルバが出力するObjValueになります。一般にはFractionalな値になります。適用前、適用後でどのようにこの値が変化するかをまとめたのが下表です。

例えば、インスタンス７では、キャパシティカット適用前32だったLBが926に急上昇していることが分かります。厳密解UBに近くなってきていることが分かります。

キャパシティカット適用前instance7、Highsは、1日廻しても解けませんでしたが、適用後は、447秒で解けています。

COPTに至っては、僅か18秒で解けました。

このように、絶大な効果を発揮するインスタンスがある一方で、殆どLBが上がらないインスタンスもあります。この違いは何でしょうか？　

恐らくは、エラー発生箇所の違いによるものでしょう。このキャパティカットは、スタッフの土日の休み数制限、言い換えるとスタッフ側勤務可能キャパシティをカバー制約に伝える働きがあると考えられます。土日勤務に関するカバー制約に対するスラックが0でなくなることの理由付けになります。土日勤務で発生するカバー制約エラーに対して作用します。つまり、土日カバー制約エラーが発生しているインスタンスでは効果がありますが、元々、発生していないインスタンスでは効果がない、と考えられます。

＜LBを上げることは正義＞

一般に厳密解を得る上で、重要なのは、LBを上げる操作です。極論を言えば、LBがUBに限りなく等しければ、解けたも同然です。LBがUBに近ければ近い程、打てる手は多くなります。

＜数式だけでは推測しにくい、インスタンス構造に応じたカットを見つける＞

MPSとかLPとかあるいは、CNF/WCNF とか数式モデル化してしまうと、もはや土日の勤務数という、問題構造由来視点での効果的なカットを見つけることは困難です。MIPソルバは、自動でカットを適用しますが、問題構造は分かっていないので往々にして、やみくもカットになることが多いです。もっと効果的なのは、問題自体を作成した作成者自身がインスタンス特性を知っているはずなので、作成者自身がカットを適用することです。

キャパシティーカット

 オリジナル問題で、LBが上がらない原因の一つは、カバー制約（スケジュールナース用語では、列制約）で、緩和解が満足してしまうことです。通常、簡単な資源であれば、LPソルバは、資源が足りない、人が居ない、(←スラックが０でない)を理解してくれますが、制約が複雑だと、理解するところまで行ってくれません。(←スラックが０になってしまう。人が足りていないはずなのに、足りているという結論になってしまう)

次の制約は、インスタンス記述のAutoRosterのrosファイルの記述になります。

    ここで、青部に、パターン記述があります。この記述は、スケジュールナース上では、Python制約に自動変換され、

となります。（rosファイル読み込み時）これらの形式は、SchedulingBenchmarks  instance1-instance24で、同じです。制約の意味は、

土日に一回でも勤務したなら、１カウントとして、総計MAX以内に収める（ハード制約）

というものです。

ここでパターンを見て頂きたいのですが、3つのパターン

～YY

Y～Y

～Y～Y

のORを取って、総計制約（SEQLE）しています。Yは、やすみ（休み）のYシフトです。～Yは、休みの否定で、勤務を表します。

つまり、

土日    |

------------------------------

～YY　：土勤務　日曜休み

Y～Y　：土休み　日曜勤務

～Y～Y：土日共勤務

のいずれかだったらを1カウントとして総計カウントして制約、が上になります。この演算では、3AND項と１OR 項が演算として使われています。Y～Yの2種類が2つあるので、全部で4パターンが存在します。4パターンのうち、3パターンを使いました。

しかし、それだったら、

土　　｜　日

～Y　｜　～Y　：土曜日勤務もしくは、日曜日勤務

をカウントした方が、OR項が1項だけで済みます。これは、残りの1パターンYYを否定したもの(＝既述3パターン)です。～（YY) →　～Y ｜～Y　（ドモルガンの法則）　

これをPython制約にしたのが、次です。

プログラムでそのようにしたのではなく、エディタで置き換えたました。（プログラム化するのは難しい）

このように問題のモデル化（モデリング）を分かり易くすると、LPソルバも余計な演算をしなくてよいので、LBが上がる（スラックが0でなくなる）可能性があります。

上の制約は、各スタッフ毎に決まるMAX値になります。各Dayでは、各スタッフの各Shiftを累計して、[Max,Min]に制約しますが、上のような書き方をすることで、LPソルバに資源の制限をより分かり易く伝えることが出来ます。資源の供給側である各スタッフは、Max回までしか土日勤務はできないんだよ。とLPソルバに分かり易く伝えることができます。

一方カバー制約側では、各スタッフ累計[Max,Min]要るんだよ、と言う要求を満たすように各スタッフに勤務を割り当てます。ここで、LPソルバは、緩和という技を持っているので、Fractinalな値(0.5とか）を使って、表面上取り繕う([Max,Min]を満たす）動きをしてきます。

このような人的資源に関わる制約に絡んできます。今回の場合、追加ではありませんが、明示的な資源制約追加を一般に、キャパシティカットと呼んでいます。

出来る限りFractionalな値を持ち出されないようにする、というのがその真意です。

モデル作成時（問題作成時）にそこまでやってくれれば、苦労が減るのですが、一般の実務問題でも、上のような簡単化（ユーザヒアリング→モデル化）をすると、問題が簡単になるのは、良く遭遇します。

Q. 表示用シフト集合の作り方

 Q.

１．シフト集合にシフト集合名「宿直カウント用」、ラベル「宿直集合」、演算子「または」、

シフト名「宿直」、「30分遅・宿直（終了日が休日）」、「60分遅・宿直（終了日が休日）」

及び「30分遅・30分早上がり宿直（終了日が平日）」を追加する。

２．行制約グループ1の宿直回数の「宿直」を「宿直集合」に変更する。

とすれば、ひょっとしたらうまくいくのでは？と思いましたが、2の設定ができませんでした。

Ans.

シフト集合の要素は、「シフト」である必要があります。シフト集合の要素をシフト集合とすることは出来ません。エントリしたいシフト集合のシフトに分解してエントリしてください。

演算子は、または（非自動含む）を選択してください。（自動割り当てされないシフトも含むので。）

制約は、≧０とすることで、実質制約することはしません。表示Only目的での制約の書き方になります。

以上です。最後に動作を確認して終了です。

Q. カウント表示がおかしいのでは？

Q. 2内Aに宿直が1回割り当てられていますが、2内Aの宿直回数はゼロ回になってしまっています。

Ans.

当該部を拡大してみると、宿直60分遅となっており、同じ青色の常勤医師の宿直とは異なるラベルになっています。

実際、にシフト定義を見ると、シフト宿直とは異なり、派遣医師用の特殊シフト（自動割り当てされない、予定入力専用シフト）であることが分かります。

実際の制約は、宿直のみに作用しています。

結論として、宿直回数0になっているのは正しい、です。

＜考察＞

同じ青色でしたので、誤解を招く結果となりました。対策として、

１）宿直60分等の色を少し変える

２）例えば、総合宿直のような合成集合シフトを作って、≧0で制約する

等が考えられます。

Q. アルゴリズム１は、過去に比べてどのくらい良くなってますか？また、今後の見通しについては？

 Ans.　

最新のSAT Competitionを推移を見ると、確かに僅かずつではありますが、性能向上が認められます。が、必ずしも、ナーススケジューリング問題用に向上している訳ではありません。むしろ、１世代前の方が良い場合もありえます、というよりもその場合の方が多いです。

過去との比較、スケジュールナース1/2との明確な比較結果はありませんが、体感できるくらいの性能向上は出来ていると思います。

現在リリース中のソルバは、１世代前のCryptiminisatのあるバージョンを修正したものを使用しています。最近、最新ソルバに置き換えたものを比較してみましが、全く最新ソルバは、現行リリース版に勝てませんでした。従い、現在リリース中のものが、アルゴリズム１としては、過去現在において最高性能であることの裏付けが取れました。

推測になりますが、アカデミックな関心がSAT　competitionで優勝することに向いていて、実務的な性能向上から離れてしまっていることに原因があるような気がしています。具体的には、incremental solvingに関する向上が殆どない、ことに起因します。

今後については、アルゴリズム１単独での性能アップはあまりなく、他の種類のソルバとの連携において力を発揮する、と考えています。そのための統合化作業を現在進行中です。

MDDサイズは、Kに比例する

幅０の係数制約について考えてみます。幅0とは、

ΣCoeff[i]＊Ｘ[i]≦K、ΣCoeff[i]*X[i]≧K

と、最大・と最小がKに一致した問題です。

K＝0のMDDグラフです。幅１であることが分かります。選択肢がありません。

X[i]＝0　∀i

であることを要求しているので当然です。

K＝１のMDDグラフです。0または１の2種選択肢があります。

K＝４のMDDグラフです。定常状態では、5つの選択肢（幅）となります。

K＝10のMDDグラフです

一般にイメージされがちなのは、最大・最小が同じなら、K＝１でも、K＝１０でも同じ解空間では？と思いがちですが、実態は、全く異なり、ほぼKに比例するということです。

幅0が効くのは、最後だけであって、そこから離れれば離れる程、幅は広くなり最終的にK幅となります。ざっくり、問題の難易度は、Kに比例するということです。

これを勤務表作成問題に当てはめると、

■制約日数が長ければ長い程難しくなる

■スタッフ人数が多ければ多いほど難しくなる

ということが理解されると思います。

例えば、夜勤人数１名（１名以上１名以下）と夜勤人数１０名（１０名以上１０名以下）では、夜勤人数１０名の方が１０倍程度、上で見たようにノード変数数が増えるので、それだけ解きにくくなる、ということです。月数が12カ月になれば、さらにノード数は、12倍となります。全体としては、120倍難しくなります。これが、combinatorial explosion組み合わせ爆発の源です。

ナーススケジューリング問題は、NP困難であることが証明された問題であり、問題が大規模になれば、やがてReasonableな時間内に解くことは出来くなる、ことが分かっています。しかし、数学が証明しているのは、それだけであり、この規模なら解けない、と断じている訳ではありません。私達研究者は、神様が決めた限界を突破することはできませんが、解ける限界範囲を出来る限り伸ばそう！と日々努力しているということです。