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な時間内に解くことは出来くなる、ことが分かっています。しかし、数学が証明しているのは、それだけであり、この規模なら解けない、と断じている訳ではありません。私達研究者は、神様が決めた限界を突破することはできませんが、解ける限界範囲を出来る限り伸ばそう！と日々努力しているということです。