ラベル設定法のドミナンスとは？

ラベルとは、RCSPにおいて、経路状態を表現する言葉です。

ドミナンス（Dominance：支配）とは、「ある経路（ラベル）が別の経路よりも明らかに優れているため、劣っている方を探索から除外する」という判断基準のことです。

不要な探索の削減（枝刈り）

あるノードに至る2つのラベル  とを比較したとき、全ての指標において、同等以上に優れていて、少なくとも一つが上回るとき、Pruningできます。

もし  がすべての指標（コスト、時間など）において  以上に優れており、かつ少なくとも1つの指標で  を上回っている場合、「 ｘは  ｙを支配(Dominate)する」と言います。

支配されたラベル  は、その先をどのように延長しても  を延長した経路より良くなることはないため、それ以上探索する必要がなくなり、破棄されます。

＜Min制約をどうする？＞

ラベル設定法や動的計画法において、MIN制約（「〜以上でなければならない」という下限制約）をMAX制約（「〜以下でなければならない」という上限制約）に変換する一般的な手法は、「残りの必要量」に着目する、または「変数の反転」を行うことです。Max制約になれば、「とにかく小さいほうが良い」というDominate　Ruleで枝刈り出来ます。

具体的には、以下の2つのアプローチがよく使われます。

1. 「残りの必要量」を状態変数にする（推奨）

「現在の蓄積量」を管理するのではなく、「目標達成までにあとどれくらい必要か」をリソース（ラベル）として管理します。

変換前（MIN制約）:

状態：現在の合計値 

制約： （ 以上のリソースが必要）

変換後（MAX制約）:

状態：残りの必要量 

初期値：

各ステップ：リソースを消費するごとに  を減らす（0以下になったら目標達成）

制約：なし（または  が 0 になることを目指す）

これにより、「下限値を突破する」という条件を、「初期値（上限）から減らしていく」というMAX制約に近い形に落とし込めます。

2. 変数の反転（ネガティブ変換）

単純に符号を反転させる方法です。

変換前: 

変換後: 

ラベル設定法のアルゴリズム内で「リソース消費量」を正の数で扱いたい場合は、「余裕（スラック）」を定義します。

＜問題はMIN-MAX制約＞

MIN-MAX範囲がある場合は、注意が必要で、同じリソースに対して、異なる方向にドミナンスが働くことになります。そのまま実装すると矛盾した枝刈りとなり最適解を失い、最悪は、Infeasibleな結果となります。

単純に、MINまでは、大きいものが強い、MIN以降は、小さいものが強い

とすれば、良いような気がします。しかし、そのロジックで単純に片方を捨ててしまうと、厳密解（最適解）を失う可能性が非常に高いです。

なぜなら、ラベル設定法におけるドミナンスの鉄則は「将来のいかなる拡張に対しても、一方のラベルがもう一方より必ず良い結果をもたらす」と言い切れるときだけ、劣る方を捨てるというものだからです。「Minまでは大きい方が強く、Min以降は小さい方が強い」という切り替え方式では、「将来どちらの制約がネックになるか」が場所によって変わるため、厳密解が消えるリスクがあります。

なので、同じリソースに対してMax-Min制約が同居する場合は、ドミナンス出来ず、「同じである」ことだけになってしまう場合が多いと思います。特にScheduling Benchmarksにおいては、Max-Minの幅が異常に狭く、殆どドミナンスが効きません。結果、ラベルの爆発がinstance13程度で生じ、一般的なラベル設定法では、解くことが出来ません。

A dedicated pricing algorithm to solve a large family of nurse scheduling problems with branch-and-price

RowActivityの計算方法

 Σai(xi)≦b[min:max]のとき、row price(dual)は、どちらを指すか？　悩ましいのですが、それは、Row Activityをみて判別するということのようです。LPSolver毎に、この辺の扱いは異なるようで、注意が必要です。LPSolverに依存しない形ならば、bのMIN/MAXを分離して記述すればよいでしょう。

判別は、bを見て、bになっている方が効いている制約になります。

Q.病欠時の設定２

 Ans.前回、病欠時のエラーを安直は方法で回避しましたが、今回は、恒久対策の方法を述べます。

問題の発端は、公休ラベルが以下のように多数、使用されていることにあります。

本来は、「病欠」で休んでいるのですから、公休ではなく、「病欠」というシフトにした方が良いように思います。

これを行うには、有給の別名としています。この有給は、自動シフトがチェックされていないので、予定を入れなければ出現しません。つまり、他の制約で使用されていない可能性が高いと考えられ、余計なエラーが出にくいであろう、という理由です。

しかし、実際に求解してみると以下の制約でエラーとなりました。が、スタッフプロパティシート上、夜勤数と公休数を変更することで対応可能です。

夜勤数を少なくします。

公休数を少なくします。

解が出ました。前回の値より余計なエラーが生じていないことが分かります。

Q.マイクロソフトアカウント名が分からない

Ans.

マイクロソフトアカウント名が分からないと購入履歴が分かりませんし、サブスクを停止することは出来ません。アカウント名が分からない場合は、ググると色々な方法があるようですが、マイクロソフトストアに紐づいているアカウント名であることが必要です。 

今、スケジュールナースを使用出来ているのであれば、必ずマイクロソフトストアに紐づいたマイクソフトアカウント名が存在し、以下の方法で、購入履歴を確認することが出来ます。

スケジュールナースを使用出来ない状態であれば、今から述べる方法は使えません。

１）マイクロソフトストアを出します。

２）サインインのアイコンをクリックすると下のようなダイアログが出現します。

３）サインインをクリックすると、私の場合、複数のアカウントを持っているので、複数のアカウント名が表示されます。表示されているアカウント名のうち、どれかがマイクロソフトストアと紐づいているアカウント名ですが、それがどれかはこの段階では分かりません。

４）なので、1個づつアカウントにサインインして購入履歴を確認していくしかありません。

しばらく、サインインしていない場合は、認証が行われることがあるようです。認証をクリアした前提で話を勧めます。

上のアカウント名をクリックすると、サインインのアイコンが変化します。

アカウントでデバイスの管理をクリックします。注文履歴を見ると、このアカウントでは、サブスクの購入が行われていないことが分かります。３）に戻って次のアカウント名を試します。

このようにして、紐づいたマイクロソフトアカウントが分かります。

紐づいたマイクロソフトアカウントさえ分かれば、サブスクを停止するのは、造作ないことだと思います。

以上です。

Q.病欠時の設定

 Ｑ．病欠者がいる場合の勤務表設定についてご相談です。

ｘｘｘｘが5月10日から病欠となり勤務できないため、公休（22日間）予定として入力しました。

以前のやり取りを参考に夜勤「責任者」を外して求解しましたが、エラーとなってしまいます。

Ans.安直なエラー対策方法と恒久的な対策方法の二つについて説明します。

＜安直なエラー対策＞

１）現象確認

２）当該制約に飛ぶ

休2連は、できれば4回以下の制約がソフト制約レベル１であることが分かります。

３）休みが大量に入力されています。休休で、1回のとカウントしますので、役20個のエラーとなります。

４）ですので、許容エラーを20とすればOKです。

５）求解できました。

Highs Newsletterまとめ

 Highsがまた進歩するようです。Hipoが期待外れだった分、HiPDLPに期待が高まります。

🧭 全体概要

HiGHS 26.0 Newsletter（2026年4月号）は、
第3回HiGHSワークショップの開催案内、HiPO（新IPMソルバー）の進展、MIPソルバーの並列化、GPU版PDLPの刷新、資金調達、Python対応の進行状況、新メンバー紹介
を中心に報告しています。

---

🏛️ 1. 第3回 HiGHS Workshop

• 2026年6月1日（月）・エディンバラで開催（SIAM OP26 の初日）
• JuMP-dev 2026 と併催
• 産業界参加者も継続参加
• 登録は workshop26.highs.dev

---

⚙️ 2. 新IPMソルバー「HiPO」

• Filippo Zanetti による “classical” interior point method の新実装
• 既存の IPX の課題（予測不能な性能、単一スレッド、QP非対応）を補完
• マルチスレッド対応の因子化（augmented system / normal equations）を実装
• v1.12 で初登場、v1.13 で Metis/AMD/RCM を同梱（→ ライセンスが Apache に）
• 2026年2月に QP 対応を追加、v1.14 で公開

---

🧩 3. MIP ソルバーの進展

• Mark Turner が プライマルヒューリスティクスと木探索のマルチスレッド化を開発
• プロトタイプは大幅な高速化を確認
• 現在レビュー中で、v1.15 に搭載予定

---

⚡ 4. GPU版 PDLP：HiPDLP

• Yanyu Zhou が GPU完全実行の PDHG（Primal-Dual Hybrid Gradient）ソルバーを開発
• 既存の cuPDLP-C を置き換え、v1.15 で HiPDLP が正式採用
• NESO（National Energy System Operator）との契約で開発

---

💰 5. Funding（資金調達）

• NumFOCUS と JuMP の協力で
  Breakthrough Energy Foundation から大型助成金を獲得
• オープンエネルギーモデル向けの JuMP/HiGHS の性能改善が目的

---

🛠️ 6. 進行中の作業

• Python インターフェースで HiPO と GPU-LP が未対応
  • Ivet Galabova がビルドシステムを改修中
  • PyPI で利用可能になる見込み
• MathWorks と共同で 不可約非実行可能性（IIS）検出の改善
• 外部コントリビュータにより インジケータ制約対応が進行
  • 当面は MIP への変換が必要
• 特殊順序集合（SOS）対応の基盤も整備中

---

👤 7. 新メンバー：Giovanni Ghisalberti

• 出身：イタリア・ベルガモ
• TU Delft（航空工学BSc）、アムステルダム大学（数学MSc）
• 2026年1月より Edinburgh 大学で PhD 開始
• MathWorks の支援で 大規模QPの解法を研究

---

🔚 まとめ

この号は、HiGHS の 並列化・GPU化・QP対応の強化が一気に進んでいること、
そして v1.15 に向けた大規模アップデートが近いことを示す内容になっています。

---

Ｑ.退会について

 Q.職場に自動作成ソフトが導入される事となり、私自身も部署が変わりリスト作成をしなくなりますので退会をお願いしたい次第です。

Ans.

こちらで、ご案内しています。

https://www.nurse-scheduling-software.com/japanese/service/pausing_subscription/

マイクロソフトアカウントに入って、購入履歴まで確認出来れば、後は造作ないことだと思います。

ところで、

職場で自動作成ソフトを導入はしたものの、

１）スケジュールナースのように休み希望は入らないし、

２）独自ルールは設定できないし、

３）使いものにならなかった、

と言う声を、少なからずお聞きすることがあります。

老婆心ながら、心配していますがその辺の確認は十分されたということでしょうか？

******

職場の説明では希望のあり方に問題があるようですが、1から3くらいで優先度を設けて休み一択という希望の出した方を工夫するようです。

しかし、実際に使ってみないと何とも言えないと思います。
*******

ソフトウェアの性能によって、希望休みが入らなかったりするのは、本当は、あってはならないのですが、依然として他社ソフトとスケジュールナースとの性能差は大きいです。スケジュールナースでは難なく入っていた休み希望が入らなくなる事態は十分に考えられます。

例えば、

■上図右側のスケジュールナースのように、自分の希望休みは全て通ったが、

■他ソフトだと左側の休み予定までしか入らない、

ということはあります。（ソフトウェアの性能差が大きい）

気になるようでしたら、そのベンダ名を教えて頂ければ、スケジュールナースの特許使用権とC++ソルバのソースコードをライセンスして、性能差を無くすアプローチも可能と思います。（今期から、広く求解エンジンのライセンス販売を行うことにしました。永続ライセンスです。）

RCSPの一般解法 ラベル設定法

 この解法は、グラフ中に複数の累計状態（パレート）を維持することにより求めるものです。

私は、これまで実装したことがなかったのですが、計算量の見積もりのために、実装してみることにしました。

この解法で、必要になる概念は、下記の二つです。

■ラベル

■Dominate　支配する→

https://schedule-nurse.blogspot.com/2026/04/blog-post_13.html

ここで、ラベルというのは、累計状態を指す、用語です。今グラフがあるとします。

複数の累計制約があると、各ノードには、複数の累計状態を覚えている必要があります。たとえば、次は、インスタンス13のグラフ状態のデバッグStateです。グラフの要素数は、1711個、ラベルの総数は、534万個、一つのグラフノードで最大のラベル数が18204個であることを示しています。（ラベルの個数が多すぎ爆発状態です）最初の値は、コストで、次の値は、累計状態を表しています。同じコストではあっても、ちょっとずつ累計状態が変わっていることが分かります。

Graph Elements=1711  Label Sum=5348323 Max labels per Node=18204

\tcost=12.0111 67,0,6,2,1,0,0,0

\tcost=12.0111 67,0,5,2,2,0,0,0

\tcost=12.0111 68,0,8,2,0,0,0,0

\tcost=12.0111 68,0,5,1,3,1,0,0

\tcost=12.0111 68,0,6,1,2,1,0,0

\tcost=12.0111 68,0,7,1,1,1,0,0

\tcost=12.0111 68,0,8,1,0,1,0,0

\tcost=12.0111 67,0,5,1,4,0,0,0

この一つ一つの行がラベルという呼称になります。ラベルというのは、最適値を得るために区別が必要な（最小限度の）状態名の呼称です。

グラフエッジをたどることによって、次のノードへと移行していき、最終的には終端します。終端での累計状態が、元々の不等式[最大、最小]にマッチしていれば、feasibleな解となり、マッチするものがなければ、infeasibleとなります。feasibleな解のうち最小のものを最適値（目的関数値）とすることができます。

終端に辿り着くまで、その累計制約を満たすかどうかは、一般には分かりません。直前の状態ならば、明らかに満たさないということは分かりますが、中間点、例えば上記のノード状態で、終端時にどのように累計状態が成長するかは、分からないので、とにかく状態を維持して終端まで進むしかありません。

累計制約の本数が多いと、容易に爆発します。如何に状態、ラベル数を少なくできるか？がこの方式のポイントです。状態を少なくすることを枝刈り(pruning)と呼んでいます。

インスタンス13では、8本程度の累計制約があるのですが、すでにこの段階で、枝刈りなしには、reasbleな時間内に解くことはできません。

RCSPとは、

 Resource Constraint Shortest Path Problemの略です。問題をサブ問題に分割した時に、結局この形となるのがNSPの本質的なところです。

で、何が難しいかというと、この問題自体が、NP困難という問題分野に分類されます。しかも、

結論だけ先に言うと、はい、Resource‑Constrained Shortest Path（RCSP／RSCP）は一般に NP 困難（NP‑hard）です。しかも「最短路＋複数リソース制約」という構造のせいで、強 NP 困難（strongly NP‑hard）に分類されます。

最短路自体は P（多項式時間）で解ける → しかし「累積制約」が入った瞬間に NP-hard へジャンプする

これは RCSP の本質的な性質で、 どんなにグラフが単純でも、累計制約がある限り避けられません。

つまり、Cardinality　累計制約が入っただけで、途端に難しくなる、ということです。子問題が、強NP困難なら、当然子を含む問題NSPは、強NP困難ということになります。子だけでも難しいのにさらにもう一次元加わります。

インスタンス24の求解にこんなにも手間取っているのは、このシフト数32にプラス強烈なCardinality制約のおかげです。

前方グラフと後方グラフによる削減

 単純にFowardとBackwardを使うと上手く行きません。

下図で、前方和と後方和を各々足して、各ノード共、a+b+cにしたいのですが、

単純にすると、そうはならないことが分かります。

どちらか一方の和は、一歩引いて、a+b+c　となるようにします。

Ryan-Foster Branchingとは

 0/1　Branchingだと、1側が重いのに比べて0側は、軽い、と言うかあまり効かないことが多いです。こうした偏りを是正する方法として、Ryan-Foster　Branchingと言う方法があります。

例えば、

休休　A

勤勤　B

休勤　C

勤休　D

A/B とC/DでBranchingします。比較として、通常ブランチ

休

～休み

を考えてみます。休＝１でブランチとすると、これはかなり強い限定になります。しかし、～休=0のブランチは、休み以外を選択するわけで、弱い限定になります。この傾向はシフト数が多くれば多いほど、強まります。１が強い限定を生み、0が弱い限定しか生まない、ということは、Tree構築においてバランスが悪い結果となります。1ブランチの枝は短いのに対して0枝は、長い枝になります。なので、なるべく同じ確率となるようにしたい訳です。これが、Ryan-Foster　Branchの背景になります。

複雑な割には、効果が少ないと判断して、スケジュールナースでは採用していませんが、SCIPでは、割に使っているようです。

SCIP Doxygen Documentation: Ryan/Foster branching

Cumulative Capacity Cut、「MIPソルバに投げる」は、失敗

 またしても、アプローチが失敗しました。

キャパシティカットが良さそうでしたので、

https://schedule-nurse.blogspot.com/2026/03/blog-post_22.html

さらにこの発想を強めて(Tightening)、Day毎の累計制約として抽出しました。具体的には、休み数制約（制約としては存在しないものの時間制約や総勤務数制約に相当）と、土日勤務数制約のDay毎の累計制約として取り出して、LB取得後にMIPソルバに投げるというものです。この方法をCumulative Capacity Cutと命名しました。発想は、Roster毎の資源総計だけではなく、Day毎の資源を明示することによって、Cover制約達成を促進する狙いです。

結果は、

これにより、例えば、インスタンス2/4/14は、Lpソルバの段階で、真のUBに等しくなり、COPTでもHIGHSでも一瞬で解けています。また、真のUBに近接した結果となった、インスタンス10,11,12,20についても速いです。これらの結果は、スケジュールナースが維持する世界最速記録よりも速いのではないかと思います。

この結果、Lpソルバが真のUB値と等しくなったときに、UB値でカットオフしなくとも（MIPソルバは真のUB値を知らない）MIPソルバは一瞬で、UB値を算出できる、←SATソルバより速い、ということが分かりました。

で、問題はインスタンス13になります。このインスタンスに関しては、期間は1カ月であるもののシフト数は19と多く、スタッフ数120人と、いわばインスタンス24のミニチュア版、と見ることもできます。残念ながら、Lpソルバの段階で、真のUB値には遠く、MIPソルバに渡しても、長期の時間がかかっています。ただ、COPTにしても解けなかったインスタンス13が有限時間内に解けるようにはなったので、一定の効果があることは分かります。

まとめとして

１）LpソルバのLBが真のUB値に等しいとき、MIPソルバが最強。SATソルバより速い

２）LpソルバのLBが真のUB値から遠ければ遠い程、MIPソルバが解けない可能性が高まる

３）LpソルバのLBを上げることは正義

ということが分かりました。市井の実務インスタンスは、インスタンス8程度なので、実務インスタンスにおいてMIPソルバを活用できる場面もある、と考えます。(SAT整数化より速い場面もある。)　

いずれにせよ、このアプローチで進んで、インスタンス24が解ける見込みはないと判断しました。（ミニチュア版でこの遅さなら、超巨大インスタンス24が解ける筈がない）

第3世代AL1(SAT)から第4世代AL3(LP)へ

 下記資料中、

Q.　4page 「人的リソースの物理限界まで配置が可能」とは、どういうことか？

質問を頂きました。

 https://www.nurse-scheduling-software.com/japanese/publications/Schedule_Nurse_Presentation_for_AI_modeling_and_state_of_the_art_solver.pdf

Ans.　

誤解を招く表現で申し訳ありません。正しくは、

「世界で一番、人的リソースの物理限界まで配置が可能」

です。絶対的な意味ではなく、相対的な意味になります。

そもそも、ナーススケジューリング問題は、規模が大きくなれば、組み合わせ爆発が生じ、リーズナブルな時間内には、解が求められない、ということが証明された問題分野（NP困難）にあります。このことが意味しているのは、「どんな規模の人的リソースでも物理限界まで配置可能」という命題は数学的には成立しません、ということです。

なので絶対表現ではなく、他と比較して相対的に、ということを意図していました。

では、具体的に何が違うのか？　アルゴリズム上の観点で、説明します。

AL1は、現在のスケジュールナースの基幹アルゴリズムで、SATソルバベースのアルゴリズムになっています。201ｘ年のMAXSAT Competitionで、4カテゴリ中3カテゴリで優勝しましたが、それをベースとして、これまで、進化してきました。

AL3は、現在もリリースされてはいますが、問題分野がアカデミックなベンチマーク専用という意味あいが強く、実務的な貢献は殆どされていません。そのコアアルゴリズムは、数理ソルバあるいは、LPベースのソルバ、世の中にある汎用最適化ソルバ(MIPソルバ）の類と同じ学問分野にあるアルゴリズムで、AL1のSATソルバベースとは全く動作原理が異なります。

AL1 は、通常規模のナーススケジューリング問題については、無類の強さを発揮しますが、規模が大きいかつソフトエラーが多発する問題は、弱いという傾向があります。この弱点がもっとも顕著に出るのがアカデミックベンチマークです。逆にこの弱点を克服するべく、未解決のアカデミックベンチマークを全問解くという目標を掲げ、実際最後の1問を残すのみという研究実績を積み重ねてきました。

この挑戦の過程で、多くの知見を得ることが出来ました。それを現在のAL1と同じく市井の実務問題を解くソルバに技術移転することが次の課題として残っています。この課題解決の後に、ユーザさまは、AL1/AL3、好きなソルバで作業することが出来るようになります。

規模が大きい、あるいは、ソフトエラーが多発する、あるいは、物理限界の極限まで、スタッフの希望休みを詰め込みたい、といった用途には、AL3を使用することになると思います。私の経験則は、ほぼすべての師長さんが、「スタッフの希望休みを全部(極限まで)詰め込みたい」ですので、勤務表リリース前の最終段階では、結局、AL3が使用されることになる、と見ています。

もう一つの誤解は、高速性です。求解が高速であることと、求解品質は、関連がありません。高速だけども低精度、つまり、スタッフの希望予定が切り捨てられる、では話になりません。これからの指標は、高速であることは勿論ですが、どれだけ、「スタッフの希望休みを全部(極限まで)詰め込めるか？」です。

このスケジュールナースのエンジンが広く行き渡れば、100万人いる？日本の全てのシフト看護師・介護師に恩恵があると思うので、1社に限定することなく、広く世の中で使われるように積極的にライセンス展開をして行きたいと思います。

ユーザさまよりメールを頂きました

永くお使い頂いているユーザさまより メールを頂きました。

＊＊＊

思えば、2016年ごろにスケジュールナースを見つけて、

使わせていただいてから、もう10年近くになります。

最初の頃は、記号記述のような制約入力方法と格闘していましたが、

すぐに、わかりやすいUIに進化して、性能も向上して、

次々と新機能も追加され、使いやすさがアップしていきました。

使えば使うほど、こんなこともできてしまうのかと、スケジュールナースの

ポテンシャルの深さには、今でも驚かされています。

幾度となく、厳しく複雑な勤務条件にも遭遇しましたが、

スケジュールナースの性能と柔軟な制約記述方法のおかげで

条件をクリアすることができて、勤務の質も看護の質も落すことなく

ベストを目指した勤務表作成ができています。

スケジュールナースと菅原さんには感謝しかありません。

本当にありがとうございます。

＊＊＊

永くお使い頂きありがとうございます。引き続いて、第4世代（新ソルバ）、第5世代（AIモデリング）を準備中です。現在、世界記録更新で最後の1問に苦闘していますが、この挑戦で得た知見をフィードバックして汎用実務問題で他を圧倒するスケジュールナースがさらに進化した版ソルバを今年中に、リリースしたいと思います。

また、検証・ご評価をお願いできればと思っております。宜しくお願い致します。

Q.6月以降のカレンダーが表示されない

Q. 5月の勤務表作成にあたり、制約日の設定をしようとしたところ

6月以降の制約終了日のカレンダーが表示されなくなりました。

開始日、終了日、表示日すべて６月以降の表示ができないようです。

設定等の変更の必要がありましたら、ご教示ください。

Ans.

古いエディションをお使いのようです。（ご案内が漏れていたようです。）現在リリース中のエディションは下記二つが全てです。

https://schedule-nurse.blogspot.com/2025/12/qprivate.html

上記以外のサポートは全て停止しました。

恐れ入りますが、移行手続きをお願いいたします。

グラフのフォワードとバックワードスキャン

 前回は、ボトムアップに構築しましたが、トップダウンで、構築する方法もあります。

ボトムアップと、トップダウン、Forward/Backwardという呼び名もあります。どちらが正解ということはなく、どちらでもよいです。

二つの方向から、計算するのは、ノードを削減するときです。

そのノードを通ると最適値を上回ることが分かっているなら、そのノードを削減出来ます。

ダイカストラのアルゴリズム

 下図は、グラフアルゴリズムの様子です。

親ノードは、T枝とE枝があります。T枝は、Then,E枝は、Else.　T枝、E枝の先は、子ノード

になります。子ノードの値（浮動小数）をval0,val1とするとき、親ノードの値は、

tval=val1+coeff1

eval=val0

if (tval≦eval) val=tval;

else val=eval;

最小化・最大化を≦の向きを変えることで、求めることが出来ます。

動的計画法とダイカストラのアルゴリズムは同じ意味？

 結論から言うと、これらは同じものではありません。

アルゴリズム３で中核となすアルゴリズムは、ダイカストラのアルゴリズムです。簡単に言うと、グラフがあって、その最短重み和の経路を求めたいとき、一度計算した結果をメモしておくやり方です。この考え方は、深宇宙通信で使われる符号化方式、ビタビアルゴリズムに本質的に似ています。と言うよりも、ビタビ教授自身、類似性を認めています。

ダイクストラ法は、動的計画法（DP）の考え方を利用したアルゴリズムの一つ、という関係性です。 っくりとした違いは以下の通りです。

• 動的計画法（DP）：大きな問題を小さな部分問題に分けて解く、「考え方の枠組み（手法）」のことです。
• ダイクストラ法：グラフの最短経路を求めるための、具体的な「手順（アルゴリズム）」のことです。
• イメージとしては、「料理（動的計画法）」という大きなジャンルの中に、「カレーの作り方（ダイクストラ法）」という具体的なレシピがあるような関係です。

ダイクストラ法は、「今の地点から一番近いところを確定させる」という手順を繰り返しますが、これは「過去の計算結果（確定した距離）を使って次の計算をする」という点で、動的計画法の仕組みに基づいています。 

Tiny Mip Solver

 Reduced Cost Fixing を各ブランチで適用していくTiny MIP Solverを作り評価しました。

しかし、解けたのは、Instance2位までで、その他は全く解けませんでした。

Highsや、COPTは、偉大と思った次第。

Reduced Cost Fixing

 数理最適化の文脈における Reduced Cost Fixing（縮小コストによる固定）は、混合整数計画問題（MIP）などの難しい問題を解く際に、「最適解においてその変数が取るべき値を事前に確定（固定）させる」ことで探索範囲を絞り込む手法です。

UBが既知のときに、

bitを反転させるコストがUBを上回るならば、bitを反転させることは、必ずUBを上回ることを意味するので、bitを反転させることはできない、→bit固定化できる、

LB＋反転ReducedCost＞UB　→ビット固定

ということになります。GAP＝UB-LBが小さくないと、UBを上回ることはないので、この手法が有効なのは、GAPが小さいときに限られます。逆にLB＝UBとなれば、極小さいReducedCostでもビットを固定化できるので、大量のFixedBitsを得ることが出来ます。そうなれば、MIP/SAT　ソルバ共簡単に解けるようになるので、出来る限りLBを上げること目指している訳です。

以下の説明では、Simplexを念頭に置いたBasic変数と非Basic変数に関する説明がされていますが、Simplexに限定されるものではなく、PDLP（FirstOrder）法、内点法等でも、成立します。

1. Reduced Cost（縮小コスト）とは

線形計画法（LP）において、ある変数が現在の最適解で 

$$

 であるとき、その変数を 

$$

 単位増やすために必要な「コストの増加分（または利益の減少分）」を指します。 

• 基本変数の場合： 縮小コストは常に 
  

  $$
   です。
• 非基本変数の場合： その変数が最適解に含まれていない理由（＝どれだけ損か）を数値化したものです。 

2. Fixing（固定）の仕組み

MIPを解く際、まず整数制約を無視した「LP緩和問題」を解きます。このとき得られる縮小コスト 

$$

 と、暫定解（現在見つかっている最も良い整数解）の目的関数値 

$$

、およびLP緩和の目的関数値 

$$

 を用いて以下の判断を行います。

• 論理： 「もし変数 
  

  $$
   を 
  

  $$
   にした場合、目的関数値が 
  

  $$
   よりも悪化することが確実であれば、その変数は最適解で 
  

  $$
   になることはあり得ない」
• 判定式： 
  
  
  
   （最小化問題の場合）
  • この条件が満たされる場合、変数 
    

    $$
     を 
    

    $$
     に固定（Fix）して以降の探索から除外できます。

3. この手法のメリット

• 探索空間の削減： 枝分かれ限定法（Branch and Bound）において、調べるべきノードの数を劇的に減らすことができます。
• 高速化： 特に変数の数が多い大規模な問題において、計算時間の短縮に直結します。

この手法は、多くの商用ソルバー（Gurobi, CPLEXなど）やオープンソースのソルバーにプリソルブ（前処理）やノード内での絞り込み戦略として標準的に組み込まれています。

C++疑似コードで。

2026年2月24日

C++ソルバー（Gurobi, CPLEX, SCIPなど）を想定した 

Reduced Cost Fixing の疑似コードを以下に示します。

この手法は、暫定解（現状の最高スコア）とLP緩和解（理想的なスコア）の差を利用して、逆転不可能な変数を切り捨てます。

C++ 疑似コード

cpp

#include <vector>
#include <iostream>
#include <cmath>

// 変数の状態を定義
enum class VariableStatus { FREE, FIXED_TO_ZERO, FIXED_TO_ONE };

struct Variable {
    int id;
    double reduced_cost; // LP緩和解から得られる縮小コスト
    double current_value; // LP緩和解における変数の値
    VariableStatus status;
};

/**
 * Reduced Cost Fixing を実行する関数
 * @param variables 変数リスト
 * @param z_lp LP緩和問題の目的関数値 (下界)
 * @param z_best 現在見つかっている最良の整数解の目的関数値 (上界)
 * @param is_minimization 最小化問題ならtrue
 */
void applyReducedCostFixing(std::vector<Variable>& variables, 
                             double z_lp, 
                             double z_best, 
                             bool is_minimization) {
    
    // ギャップ（あとどれだけ改善の余地があるか）
    double gap = std::abs(z_best - z_lp);

    for (auto& var : variables) {
        if (var.status != VariableStatus::FREE) continue;

        // 最小化問題におけるバイナリ変数の判定例
        if (is_minimization) {
            // 変数が現在 0 で、1 に変えた時のコスト増(reduced_cost)が 
            // ギャップを超えているなら、1 になることは絶対にない
            if (var.current_value < 1e-6 && var.reduced_cost > gap) {
                var.status = VariableStatus::FIXED_TO_ZERO;
                std::cout << "Variable " << var.id << " fixed to 0\n";
            }
            // 変数が現在 1 で、0 に変えた時のコスト増(-reduced_cost)が
            // ギャップを超えているなら、0 になることは絶対にない
            else if (var.current_value > 1.0 - 1e-6 && -var.reduced_cost > gap) {
                var.status = VariableStatus::FIXED_TO_ONE;
                std::cout << "Variable " << var.id << " fixed to 1\n";
            }
        }
    }