RC Fixingにより、目的関数値は変化するか？

Q.RC FixingによりRMPのOBJが変化することはあるか?

 Iterativeに解いていくこのアルゴリズムは、自然にOBJが上昇することを期待しています。一応、AIの意見を聞きました。

結論から言うと：

Reduced Cost Fixing（RCF）そのものは RMP の OBJ 値を変化させません。 ただし、RCF によって “変数の上限・下限が固定される” ことで、 RMP を解き直したときの LB（＝RMP の OBJ）は変化することがあります。

つまり：

• RCF = OBJ を直接いじらない（安全）

• RCF の結果として RMP の feasible set が縮む → LB が上がることはある

• LB が下がることは絶対にない（soundness の理由）

この 3 点が本質です。

◆ Reduced Cost Fixing が「OBJ を変えない」理由

RCF は次のような操作です：

• ある変数 x を 0 に固定（UB=0）

• または 1 に固定（LB=1）

これは 目的関数の係数（重み）を変更する操作ではない。

したがって：

• OBJ の式は変わらない

• 目的関数の係数も変わらない

• RMP の線形構造も変わらない

RCF は 制約（bounds）を tighten するだけ です。

◆ ではなぜ LB（RMP の OBJ）が変わることがあるのか？

理由はシンプルで：

変数を固定すると、RMP の feasible region が縮むから。

LP の性質として：

• feasible region を縮める → LB は 上がるか同じ

• feasible region を広げる → LB は 下がるか同じ

RCF は feasible region を 縮めるだけ なので、

$$L{B}_{\text{new}}\ge L{B}_{\text{old}}$$

が常に成立します。

これが soundness の根拠でもある。

◆ 重要：LB が下がることは絶対にない

RCF は「増やす方向の Fixing」しか行わないため、

• 最適解を排除しない（sound）

• LB が下がることはない（安全）

LB が下がる Fixing は 危険（unsound） であり、 あなたの方式では絶対に起きません。

◆ まとめ（最重要）

• RCF は OBJ の式を変えない → OBJ は変化しない

• ただし、変数固定により feasible region が縮む → LB が上がることはある

• LB が下がることは絶対にない（soundness）