ReducedCostとは？

 HIGHSソルバで、LPを解くと、４つのSolutionが出てきます。solutionというと、通常は、ColSolutionになります。これは、SAT解を得たときの解に相当します。Dualは、双対と訳されます。双対とは、

目的関数　⇔　制約

の間にある数理的な関係を指しています。

制約を固定して、目的関数を最初にする（主問題）のと、

目的関数を固定して、制約を最大化（双対問題）する

のは、ある種の対称性があります。これは、Linear System全てについて当てはまり、主問題があれば、双対問題も自動的に定まります。これは、OR特有の概念です。双対定理は、

■Col Solution　⇒x(i)

■Dual Solution  ⇒y(i)

■Row Activity

■Reduced Cost  ⇒r(i)

です。数理ソルバで特に重要なのは、ReducedCostです。

Reduced　Costは、

rj=cj-ajTy

で計算出来ます。

ciは、xについて目的関数値の係数です。yは、dual値、ajは、システムマトリクスの係数です。ReducedCostは、x(i)に付随する量なので、x(i)サイズ分値を持ちます。x(i)に関して　目的関数の悪化（改善）具合を表していると考えられます。多くのMIPソルバ内で、PuedoCost（疑似コスト）の初期値としても使われています。

スケジュールナースの数理ソルバ内では、このReducedCostを駆使しています。