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

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

＊＊＊

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

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

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

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

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

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

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

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

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

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

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

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

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

＊＊＊

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

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

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";
            }
        }
    }