Q. 2内Aに宿直が1回割り当てられていますが、2内Aの宿直回数はゼロ回になってしまっています。
Ans.
当該部を拡大してみると、宿直60分遅となっており、同じ青色の常勤医師の宿直とは異なるラベルになっています。
Ans.
最新のSAT Competitionを推移を見ると、確かに僅かずつではありますが、性能向上が認められます。が、必ずしも、ナーススケジューリング問題用に向上している訳ではありません。むしろ、１世代前の方が良い場合もありえます、というよりもその場合の方が多いです。
過去との比較、スケジュールナース1/2との明確な比較結果はありませんが、体感できるくらいの性能向上は出来ていると思います。
現在リリース中のソルバは、１世代前のCryptiminisatのあるバージョンを修正したものを使用しています。最近、最新ソルバに置き換えたものを比較してみましが、全く最新ソルバは、現行リリース版に勝てませんでした。従い、現在リリース中のものが、アルゴリズム１としては、過去現在において最高性能であることの裏付けが取れました。
推測になりますが、アカデミックな関心がSAT competitionで優勝することに向いていて、実務的な性能向上から離れてしまっていることに原因があるような気がしています。具体的には、incremental solvingに関する向上が殆どない、ことに起因します。
今後については、アルゴリズム１単独での性能アップはあまりなく、他の種類のソルバとの連携において力を発揮する、と考えています。そのための統合化作業を現在進行中です。
幅０の係数制約について考えてみます。幅0とは、
ΣCoeff[i]＊Ｘ[i]≦K、ΣCoeff[i]*X[i]≧K
と、最大・と最小がKに一致した問題です。
K＝0のMDDグラフです。幅１であることが分かります。選択肢がありません。
X[i]＝0 ∀i
であることを要求しているので当然です。
K＝１のMDDグラフです。0または１の2種選択肢があります。
K＝４のMDDグラフです。定常状態では、5つの選択肢（幅）となります。
K＝10のMDDグラフです
一般にイメージされがちなのは、最大・最小が同じなら、K＝１でも、K＝１０でも同じ解空間では？と思いがちですが、実態は、全く異なり、ほぼKに比例するということです。
幅0が効くのは、最後だけであって、そこから離れれば離れる程、幅は広くなり最終的にK幅となります。ざっくり、問題の難易度は、Kに比例するということです。
これを勤務表作成問題に当てはめると、
■制約日数が長ければ長い程難しくなる
■スタッフ人数が多ければ多いほど難しくなる
ということが理解されると思います。
例えば、夜勤人数１名（１名以上１名以下）と夜勤人数１０名（１０名以上１０名以下）では、夜勤人数１０名の方が１０倍程度、上で見たようにノード変数数が増えるので、それだけ解きにくくなる、ということです。月数が12カ月になれば、さらにノード数は、12倍となります。全体としては、120倍難しくなります。これが、combinatorial explosion組み合わせ爆発の源です。
ナーススケジューリング問題は、NP困難であることが証明された問題であり、問題が大規模になれば、やがてReasonableな時間内に解くことは出来くなる、ことが分かっています。しかし、数学が証明しているのは、それだけであり、この規模なら解けない、と断じている訳ではありません。私達研究者は、神様が決めた限界を突破することはできませんが、解ける限界範囲を出来る限り伸ばそう！と日々努力しているということです。
Q.入力ラベルを入れ替えたい。
Ans.まず、ラベルの順番について説明します。次のような順番に固定されており、順番を変えることは出来ません。
シフト名→ 別名１→ 別名２..
↓
シフト名→ 別名１→ 別名２..
.....
シフト集合名
↓
シフト集合名
.....
方策１） シフト別名で使っていないものは、削除します。結果的に右のラベル群はスライドして上がってきます。
方策２） シフト別名をシフト集合で定義し直します。 シフト集合内での順番は、変えることが出来ます。不要なものは、後ろに配置することで、結果的に右のラベル群はスライドします。
方策３） キーボードのbinding使用
https://schedule-nurse.blogspot.com/2023/11/blog-post.htm
頻繁に使用するラベル順に定義します。慣れれば圧倒的に速いです。
なお、名前は、Excel等でと短冊シートを作ってキーボード上部に貼っておくと、慣れるまでの間重宝します。
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を駆使しています。
インスタンス２４は、制約が重すぎて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 は不要
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 は次のように役立ちます。
• 勤務回数制約の実際の使用量を確認する
• 連続勤務制約がどの程度「ギリギリ」かを見る
