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