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　支配する

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

複数の累計制約があると、各ノードには、複数の累計状態を覚えている必要があります。たとえば、次は、インスタンス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が解ける筈がない）