スケジュールナースのブログ

2026年3月26日木曜日

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

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

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

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

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

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

2026年3月24日火曜日

Tiny Mip Solver

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

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

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

2026年3月23日月曜日

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

2026年3月22日日曜日

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

前回のキャパシティカットを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ソルバは、自動でカットを適用しますが、問題構造は分かっていないので往々にして、やみくもカットになることが多いです。もっと効果的なのは、問題自体を作成した作成者自身がインスタンス特性を知っているはずなので、作成者自身がカットを適用することです。

2026年3月21日土曜日

キャパシティーカット

オリジナル問題で、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な値を持ち出されないようにする、というのがその真意です。

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