2026年3月14日土曜日

Q.入力ラベルの配置を変えたい

 Q.入力ラベルを入れ替えたい。


Ans.まず、ラベルの順番について説明します。次のような順番に固定されており、順番を変えることは出来ません。

  シフト名→ 別名1→ 別名2..

     ↓

  シフト名→ 別名1→ 別名2..

         .....

         シフト集合名

     ↓

         シフト集合名

         .....

方策1) シフト別名で使っていないものは、削除します。結果的に右のラベル群はスライドして上がってきます。

方策2) シフト別名をシフト集合で定義し直します。 シフト集合内での順番は、変えることが出来ます。不要なものは、後ろに配置することで、結果的に右のラベル群はスライドします。

方策3) キーボードのbinding使用

  https://schedule-nurse.blogspot.com/2023/11/blog-post.htm
 

  頻繁に使用するラベルを側に置きます。慣れれば圧倒的に速いです。

  なお、名前は、Excel等でと短冊シートを作ってキーボード上部に貼っておくと、慣れるまでの間重宝します。




2026年3月13日金曜日

ReducedCostとは?

 HIGHSソルバで、LPを解くと、4つの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でスラックに余裕があるとき、その行は削除してよいか?

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

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


❗ 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では、僅かに効果があるものの、殆どあり得る最大・最小値に張り付いてしまっています。全く期待通りにはなっていません。係数4,5,6が各々最大・最小に張り付いているというということは、全く範囲を絞れないということです。


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

原因は、

1)UBでカットオフしていない

2)LBとUB GAPが大きすぎる

3)緩和解

が、考えられます。

割に小さなインスタンス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";
    // ... (以下略) ...
}