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

2026年3月13日金曜日

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を駆使しています。

2026年3月12日木曜日

Daul==0でスラックに余裕があるとき、その行は削除してよいか？

インスタンス２４は、制約が重すぎてLPソルバが遅いので、一時的に削除できないかを検討しました。

結論的には、上記条件でも以下の議論の通り削除することは出来ません。それ以前に、オリジナルLPで、お目当ての行群中、DUAL＝０の行が存在しなかったので、それも意味がなく、削除不能という結論です。

❗ DUAL値 = 0 でも制約を削除してはいけない理由

DUAL値が 0 というのは、**「最適解においてその制約が binding ではない」**というだけです。

• binding ではない → 余裕がある

• 余裕がある → 緩めても目的関数は改善しない

• しかし → 削除すると可行領域が広がり、別の解が出てしまう可能性がある

つまり、

制約は「最適解を規定する」だけでなく、「不適切な解を排除する」役割も持つため、

DUAL値だけで削除判断をするのは危険です。

🧭 では、どんなときに削除してもよいのか？

以下の条件が揃うと、削除しても安全な場合があります。

1. 制約が常に冗長（redundant constraint）であると証明できる

例：

他の制約の線形結合で表せる、または常に他の制約により厳しく支配されている。

これは数学的に確認できる場合のみ。

2. 制約の右辺を大きくしても可行領域が変わらない

DUAL値 = 0 の制約には「許容範囲（allowable increase/decrease）」があります。

• allowable decrease が無限大

• allowable increase が無限大

のように、右辺をどれだけ動かしても可行領域が変わらない場合は、削除しても影響がありません。

3. 制約が論理的に不要であることが問題構造から明らか

例：

• 上限 100 の制約と上限 80 の制約が両方ある → 上限 100 は不要

• x ≥ 0 と x ≥ -5 → x ≥ -5 は不要

2026年3月11日水曜日

Row　Activityとは？

Row Activity は、**「その行（制約）の左辺が、最適解で実際にどの値になっているか」**を表す量です。

LP の感度分析や制約の状態を理解するうえで基本になる指標で、Primal 解から直接読み取れます。

Row Activity と Slack の関係

Σa(i)*x(i)≦b

のとき、Slackは、Σa(i)*x(i)です。

なので、Row Activity を見ると制約がどの状態かが分かります。

• Row Activity = b → Slack = 0 → 制約は binding（効いている）

• Row Activity < b → Slack > 0 → 制約は非 binding（余裕あり）

Row Activity が示すこと

Row Activity は、次のような情報を与えます。

● 1. 制約が最適解でどれだけ使われているか

勤務回数制約なら「何回勤務しているか」など。

● 2. 制約が binding かどうか

Slack と組み合わせて判断できます。

● 3. 制約の削除・緩和の影響を考える材料

Row Activity が b に近いほど、その制約は効いている可能性が高い。

シフト最適化の場合、Row Activity は次のように役立ちます。

• 勤務回数制約の実際の使用量を確認する

• 連続勤務制約がどの程度「ギリギリ」かを見る

2026年3月10日火曜日

Dual値が意味するもの

OR理論を駆使して問題を解くときの基礎です。

DUAL値 = 制約を 1 単位だけ緩めたとき、目的関数がどれだけ改善するかを示す感度係数。

• 最大化問題なら：制約を緩めると目的値がどれだけ増えるか

• 最小化問題なら：制約を緩めると目的値がどれだけ減るか

つまり、DUAL値は制約の価値を表します。

📌 1. DUAL値の直感的な意味（影の価格）

DUAL値は、経済学では shadow price（影の価格）と呼ばれます。

• ある制約が「資源の上限」を表す場合

→ DUAL値は「その資源を 1 単位追加できたら、目的関数がどれだけ良くなるか」を示す。

例：

制約Aを緩めると、目的関数が△減少する

その減少量が DUAL値。

📌 2. 数学的な意味（双対問題の最適解）

LPには必ず双対問題（DUAL problem）が存在し、

DUAL値はその双対問題の最適解の変数値です。

• primal：変数 x

• dual：変数 y（これが DUAL値）

双対問題は「制約の重み付けによって目的値を評価する問題」で、

DUAL値はその最適な重み付けを表します。

📌 3. 実務での解釈（制約の重要度）

DUAL値は、制約がどれだけ「効いているか」を示します。

● DUAL値 ≠ 0

→ その制約は binding（効いている）

→ 制約を緩めると目的値が改善する

→ 資源が不足している状態

● DUAL値 = 0

→ 制約は余裕がある（非binding）

→ 緩めても目的値は変わらない

→ 資源が余っている状態

📌 6. 注意点

• DUAL値は「制約の右辺を微小に変化させたとき」の効果

→ 大きく変えると線形性が崩れ、DUAL値は使えない

• 整数計画（MILP）では DUAL値は一般に意味を持たない

→ LP緩和でのみ有効

2026年3月9日月曜日

LPソルバで、時間制約係数和を制約する

失敗しました。

インスタンス23では、僅かに効果があるものの、殆どあり得る最大・最小値に張り付いてしまっています。全く期待通りにはなっていません。係数４，５，６が各々最大・最小に張り付いているというということは、全く範囲を絞れないということです。

インスタンス24に至っては、その傾向が一層激しくなりました。

原因は、

１）UBでカットオフしていない

２）LBとUB　GAPが大きすぎる

３）緩和解

が、考えられます。

割に小さなインスタンス14では、

狙い通りの効果を発揮することが出来ます。LBとUB(1278)GAP差が小さいことが効いているように思えます。

暫定UB値でカットオフする、or CutGeneratorを導入すれば改善する可能性がありますが、そもそも、それが出来ないので苦労している訳で、別なアプローチを取ることにしました。

2026年3月8日日曜日

Lpソルバの構築方法の見直し

下記問題が発生しました。

x1, x2,x3.. 等の定義順とソルバの定義順が異なるので、変換テーブルが必要になる。この後の操作で、いちいち変換テーブル参照が必要となりバグの温床になる。

https://schedule-nurse.blogspot.com/2026/02/cnf2lp.html

原因

Highs/COPT等では、出現順に変数を設定してしまう

解決策

目的関数記述時に全変数をなめる。

Minimize

obj: 0 x1 + 0 x2 + 0 x3 + 0 x4 + 0 x5 + 0 x6 + 0 x7 + 0 x8 + 0 x9 + 0 x10 + 0 x11 + 0 x12 + 0 x13 + 0 x14 + 0 x15 + 0 x16 + 0 x17 + 0 x18 + 0 x19 + 0 x20 + 0 x21 + 0 x22 + 0...

のような感じです。これで変換テーブルが必要なくなり、LPファイルを読み込ませた後のAPI操作が楽になります。

void writeToFile(const std::string& filename) {
    std::ofstream out(filename);
    
    // 1. 目的関数ですべての変数を順番に「宣言」する
    out << "Minimize\n obj: ";
    for (int i = 1; i <= max_idx; ++i) {
        double coeff = 0.0;
        if (weights.count(i)) {
            coeff = weights[i];
        }
        
        // 符号と項の出力
        if (i > 1) {
            out << (coeff >= 0 ? " + " : " - ");
        } else if (coeff < 0) {
            out << "- ";
        }
        
        out << std::abs(coeff) << " " << getVarName(i);
    }
    out << "\n";

    // 2. 制約式
    out << "Subject To\n";
    // ... (以下略) ...
}

2026年3月5日木曜日

個々のRosterの時間計数和の最大・最小を求める

問題を解く前のPreconditionを求める問題です。時間制約は、MDDで解くことにしましたが、未だ規模が大きすぎるので、小さくすることを検討しました。個々の時間計数和で規制できれば、大幅にMDDサイズを小さくできます。

https://schedule-nurse.blogspot.com/2026/02/mdd_14.html

１）個々のRosterの簡易モデルをMIPソルバで解く

詳細モデルまで含めてHighsMIPソルバで厳密解を求めるのは難しいです。仮に求まったとしても、個々のRoster空間しか見ていないので、最小0、最大時間制約値となってPreconditionの意味をなさない可能性があります。

２）全体LPの最大・最小問題として解く

前回の検討で、GPUを用いたPDLPXであれば、全体目的関数値AがReasonableな時間内に求まることが分かりました。