2026年5月24日日曜日

看護師必要人数の計算

40床で、18人という計算を示しました。 

https://schedule-nurse.blogspot.com/2026/05/blog-post_20.html

しかし、この計算は、実態と合っていません。実態は、どんなに少なくとも23人、平均的には、25-26人だと思います。

なぜこのような乖離が生まれたかとというと夜勤人数が3人と規定しているからです。この人数は、法的な要請ではなく、現場の要請、その人数がいないと廻せないという切実な事情によるものです。なので、夜勤3人の是非は論じず、この人数を前提として、必要な最低人数を求めてみます。

考え方は、需要側からの人数と供給側の人数のコマ数計算になります。

需要側人数≦供給側人数

需要側人数は、深夜3人、準夜勤3人必要です。これが、毎日、最大31日必要ですから、

    3*31+3*31=186コマ必要です。

一方、看護師が供給できるのは、72時間制限より、深夜+準夜勤=9回までです。夜勤できる看護師数と、コマ数の関係をプロットすると、以下のようになります。

つまり、夜勤スタッフが21名居て、全員が夜勤9回をこなせば、189コマとなり、需要側人数を3コマ上回ります。

同様に、全員が夜勤8回をこなすとすれば、夜勤スタッフが需要を上回るのは、23名では足りず、少なくとも24名以上必要、という計算になります。

通常、夜勤9回Limit一杯まで行うことは少ないと思われるので、8回までとすれば24名ということになりますが、実態は、

■24名の場合、夜勤を9回こなす方がいたり、

■25名以上居る

のではないでしょうか? この理由は、

A■夜勤回数が少ない方がいる

B■配置できない

C■急な休みに対する余裕分

ではないかと思います。Aについては、コマ数計算でその夜勤回数で累計すればよいだけなので、その夜勤回数に応じた必要人数も同様に計算できます。

してみると、

コマ数累計計算による必要人数と実態の差の原因

は、Cの余裕分を除外すると、Bの配置できない、という答えに行き着くのではないでしょうか?

本当に配置できないのか?スケジュールナースでやってみました。プロジェクトは、以下を修正して、人数を可変してみました。


夜勤9回で許容したとき、確かに21人で解がありました。このとき、コマ数余裕は、3コマですから、3人だけ夜勤8回の方がいるはずです。確かにそのようになっています。

人間では不可能と思われますが、スケジュールナースでは21人しかいなくとも配置が出来ました!

カラクリの種明かし

この結果は、従来の常識からすると非常識の類です。カラクリは、実はこの解、予定が入っていません。


経験によると、上の3交代に限らず、変則2交代においても、ブランク予定であれば、多くの場合、スケジュールナースは、コマ数余裕がほとんどなくても配置ができます。コマ数余裕0が物理限界になります。もちろんチームバランス等の要因により、配置できないこともありますが、ブランク予定であれば、ほぼ物理限界もしくは、近くまで配置が出来ます。(しかし、人力では、やはり無理だろうと思います。どなたか、出来る自信がある方いらっしゃいますか?)

ここまでは読めます。

問題は予定、これが読めない

予定を入れて行きましょう。週末に各2公休追加しました。


問題なく配置できました。


さらに、平日に公休2個追加しました。



かなり苦しいですが、配置できました。看護師パターンにも影響してソフトエラーが多数出現しています。(ブランク予定状態では、ソフトエラーはほとんど出ていませんでした)


今回は、たまたま配置できましたが、例えば入学式の日に休みが集中する、等、月ごとに変わる休みのパターンによる影響は読めません。公休数希望が2個まで、という制約があれば、なんとかなりそうですが、それ以上の予定が入ると、

やってみないと分からない

ことが分かったと思います。例えば、公休希望は5個まで、という職場がありますが、スケジュールナースでも5個全員がランダムに入れられると、容易に解がない事態となります。実は、解が人力解であるのは、

■休日に希望が集中する

■希望を出さない人がいる

ことに助けられているからです。

本当に全員がランダムで規定上限の休みを希望されると、解があることは保証できません。にもかかわらず制度がそれを許している、いわば、砂上の楼閣状態の職場が多いと感じています。ちなみに、この希望休み数上限、職場によって、2個から、3,4,5個、無制限と様々です。

いずれにせよ、何かあった時の余裕分を除外すると、

一番大きな要因は、配置能力

が、看護師人数を決める要素である、と言えます。看護師長さんに聞けば、「人は足りていない」という回答しか返ってこないと思いますが、冷静に、論理的に考えれば、上のような考察にたどり着きます。現状は、人力の配置能力を前提として、看護師リソース問題をマネージメントしている、誰も指摘しませんが、それが一番の勿体ない問題なのです。


予定が入れば入るほど、ナーススケジューリング問題は、難しくなる

これも誰も指摘しませんが、予定が入れば入るほど、ナーススケジューリング問題の難易度は上がります。ブランク予定に比し予定入り解空間は、予定を入れれば入れるほど狭くなります。看護師長さんは、スタッフの予定をハード制約として入れてしまう傾向にあります。人力や性能の低いソルバとの差は、より一層開くと考えられます。


経営資源の観点で見ると

一般的に、スタッフ数の多い職場ほど、人力とスケジュールナース割り当て能力の差は、大きくなります。今ここで言えるのは、50名の職場であれば、1名程度は削減できるであろうという経験的な事実です。50名の職場が10あるとすると、看護師の年収X人数分の効果を生み出す効果があるのではないでしょうか?病院経営で一番大きいのは、どの病院も例外なく看護師人件費です。


物理限界に挑むナーススケジューリング問題に対する標準解法

を発表したいと思い、最後の研究課題に取り組んでいます。

論文は、

■英文で標準解法について

■和文で各社比較による看護師リソースの話し

と、二つ書きたいと思っています。(製品リリース予定は別途)

最適化ソルバは、一つ世界最高のものがあれば十分です。各社が、その世界最高のエンジンの提供を受け備えれば、配置能力の性能差の心配はなくなります。性能差のおかげで、理不尽なシフトを強いられたりするのは、まっぱらごめんです。

ナーススケジューリング問題にかかわるシフト従事者の数は、260万人と推定されます。

https://schedule-nurse.blogspot.com/2026/05/blog-post_15.html

ナーススケジューリング問題にかかわるシフト従事者全ての方に、研究成果としてのソルバの恩恵を届けたい、これがスケジュールナースの意図するところであります。




2026年5月23日土曜日

「ソルバを長期間廻せば、最適解がいずれ出る」は、間違い

 よくある誤解で、


■ソルバが高速である

■高精度である

ことは、まったくの別物です。速ければ、最適解が出るのも早いだろう、というのは思いこみです。性能が劣るソルバは、

どんなに時間を掛けても大抵の場合、最適解に到達することはありません

最適解にどれだけ近づけるか?というのは、ソルバ(人間含む)で決まります。その比較データを公開したいのですが、残念なことにスケジュールナース以外は、ベンチマークを公開していないので、同一土俵上で比較することが出来ません。別途、A社、B社という形で論文にまとめたいと思っているので、他社データを提供してもよい、という方は、サポートまでご連絡ください。お礼は、スケジュールナース買い切り版(11万円)のプレゼントです。

大学病院関係のユーザさまにもご協力いただきたいと思っているので、お願いに伺うことがあると思いますが、その際はよろしくお願いします。(実際のところ、現在、題意に沿う評価データを有しているのは、ベンダではなくて各社を同一基準で評価した大病院だと思います。)

なぜ、他社を評価したことがないのに上が言い切れるか?というと、答えは探索空間にあります。まともに探索していたのでは、普段普通のインスタンスでさえ宇宙的な時間が必要であることは、前に説明しました。

https://schedule-nurse.blogspot.com/2026/05/blog-post_21.htm

そこで、ソフトウェアがやっていることは、不要な探索空間は探索しないことにする、です。これを枝刈り(pruning)と言っています。ソフトウェアの性能は、このアルゴリズム、枝刈り能力で決まるといっても過言ではありません。

最適化ソルバには、二つのアプローチがあります。

1)SAT的アプローチ(枝刈りは、ハード制約のみに限定される)

2)OR的(数理的線形制約アプローチ、枝刈りは、ソフト制約にも適用可能)

もうひとつ、メタヒューリスティクス的アプローチもあるのですが、厳密解が出ないためここでは除外します。ほとんどのナーススケジューリング問題のソフトウェアは、メタヒューリスティクスのアプローチを取っています。 1社ないし2社が、2)手法を取っています。




2026年5月22日金曜日

ナーススケジューリング問題は、何故難しいか? その他の理由

 2番目の理由としては、

行制約があることです。一人一人の看護師の働くパターン制約が存在することです。



アルバイトのシフト問題では、ほぼ縦方向の計数のみを考えれば、ほぼ十分なのに対して、ナーススケジューリング問題では、看護師一人一人のパターン(行制約)が存在します。行制約を無視すると、上のような意味のない勤務表になってしまいます。


3番目の理由としては、

看護師の働き方パターンそのものが、NP困難 な問題であることです。


一般に行制約には、計数制約が入りますが、それが一本でも入ると、NP困難中でもでもさらに難しいRCSPP(Resouce Constraint Shortest Path Probelm)強NP困難問題となります。それが、看護師人数分もあるのですから、より難しい問題となるのです。

まとめると、

1)探索空間が広い

2)行制約(看護師パターン)がある

3)しかも、一人の看護師パターン問題だけで、強NP困難な問題

なので、ベンダにより性能差が歴然とあるのが普通です。菅原システムズでは、アカデミックベンチマークを全て解くという目標を掲げ、ここ数年研究活動を推進してきました。この研究も最終段階となりました。



2026年5月21日木曜日

ナーススケジューリング問題はなぜ難しいか?

別な言い方をすると、何故、ベンダ間で、性能差が激しいのか? です。


一つには、探索空間が広いことです。一例として、scheduling benchmarksのinstance8を取り上げます。私が今取り組んでいるinstance24は、超巨大なインスタンスであり、アカデミックな価値はありますが、全く実用的なインスタンスではありません。

それに対して、instance8については、期間一か月、スタッフ数30人、シフト数5という実務でも標準的、市井のナーススケジューリング問題です。この探索空間は、AutoRosterで、次のように10^587と表示されます。

 

左下隅にある表示が探索空間数を示しています。これが、どれだけ広いのかを聞きました。



あるインスタンスの探索空間は、10の587乗です。宇宙の原子数と比べてその大きさを説明してください。

結論: あなたの探索空間 10^587 は、宇宙に存在すると推定される原子数 1079〜1080(およそ 1 後に 80 個のゼロ)と比べて、約 10^507 倍以上という、桁違いどころではない“宇宙規模を超えた巨大さ”です。 これは、宇宙の全原子を 1 個ずつ並べても、探索空間の大きさには全く届かないというレベルです。

🌌 宇宙の原子数(1080)と探索空間(10587)の比較

  • 観測可能な宇宙に含まれる原子数の推定値は 約 1079〜1080。 (主に水素原子が大半)

  • あなたの探索空間は 10^587

🔥 比率をとると?

105871080=10507

つまり、 探索空間は宇宙の原子数の 10^{507} 倍

🧠 感覚的なイメージ

1. 宇宙の原子を 1 個ずつ使っても、探索空間の 0.000…(507 個のゼロ)…1 にもならない

宇宙の原子を全部使っても、探索空間の“表面をかすりもしない”レベルです。

2. 宇宙を 10^507 個用意しても足りない

宇宙そのものを 1 個の「原子」と見なしても、 10^507 個の宇宙が必要になります。

3. 計算可能性の観点

10^587 は、

  • 量子コンピュータ

  • 銀河サイズのコンピュータ

  • 宇宙の寿命(約 10^17 秒) を総動員しても到底探索できない規模です。

📸 視覚イメージ(宇宙のスケール)

  • CIRCULAR MAP OF THE UNIVERSE ALL VERSIONS - Pablo Carlos Budassi
  • CIRCULAR MAP OF THE UNIVERSE ALL VERSIONS - Pablo Carlos Budassi
  • The Scale of the Universe
  • Scale of the Cosmos - SkyMarvels.com

🧩 まとめ

  • 宇宙の原子数:10^80

  • あなたの探索空間:10^587

  • 差:10^507 倍

  • 結論:宇宙の原子数を比較対象にしても小さすぎるほど、探索空間は圧倒的に巨大




現在のスーパコンピュータで探索したとして、どれだけ時間がかかるかを説明して。


結論:現在の世界最速クラスのスパコンを総動員しても、探索空間 10^587 を総当たりするには “宇宙の寿命の 10^500 倍以上” の時間がかかる。つまり、物理的に絶対に不可能。

🚀 1. 前提:世界最速スパコンの性能

2025〜2026 年時点の世界最速クラス:

  • Frontier(米国): 約 1.2 exaFLOPS = 1.2 × 10^18 回/秒

  • 仮に「1 FLOP = 1 探索ステップ」としても、 1 秒で 10^18 通りしか探索できない

あなたの探索空間は:

10587

🌌 2. 必要時間の計算

105871018=10569 秒

つまり、 スパコン 1 台で探索すると 10^569 秒かかる

🕰 3. 宇宙スケールで比較

■ 宇宙の年齢

4.3 × 10^17 秒 ≒ 10^17 秒

■ 必要時間との比較

105691017=10552

つまり、 宇宙の寿命の 10^{552} 倍の時間が必要

🔥 4. では、スパコンを宇宙の原子数だけ並べたら?

宇宙の原子数 ≒ 10^80

スパコンを 10^80 台並べると:

105691080=10489 秒

まだ 10^{489} 秒かかる。

宇宙の寿命(10^17 秒)と比べると:

104891017=10472

つまり、 宇宙の全原子をスパコンに変えても、宇宙寿命の 10^{472} 倍の時間が必要

🧠 5. 感覚的な説明

  • 宇宙の寿命を 1 秒とすると、 探索に必要な時間は 10^{552} 秒

  • これは、 “0 が 552 個並ぶ数字の秒数”

  • 物理法則(エネルギー、情報密度、光速)をすべて無視しても、 絶対に計算できない領域

🧩 6. まとめ

項目
探索空間10^587
スパコン速度10^18 探索/秒
必要時間10^569 秒
宇宙の寿命10^17 秒
10^552 倍

結論:総当たり探索は、宇宙の物理法則をすべて破っても不可能。 探索空間削減・ヒューリスティック・枝刈りが必須。

2026年5月20日水曜日

7:1看護人数の計算

 7:1の看護師数の計算。以下で求められます。(2:1,4:1,10:1,13:1)も同様

しかし、法的な必要人数と現場を廻すための必要人数は違います。実際の必要人数は、


夜勤人数とソルバ能力(人間含む)で決まる 


というのがスケジュールナースの主張です。例えば、40床の看護師は、以下のように、必要看護師数は、18人と計算されますが、実態は、どんなに少なくとも21人が必要となります。夜勤人数が決まれば、ほぼ自動的に21人という数字はコマ数計算で出てきますが、その人数で定常として廻している(廻せる)職場は皆無のはずです。実態は、23人がギリギリ、運用として、26人居れば手書きソルバ(人間)でも比較的楽に廻せるということではないでしょうか? この辺については、次回以降別途解説します。



結論(最重要ポイント) 7対1の看護配置は「患者7人に看護師1人」ではなく、患者数に応じて必要となる“看護師の総勤務時間数”で判定する制度です。 計算式は厚労省の様式9に基づき、以下の3ステップで求めます。

🧮 7対1看護配置の計算式(公式)

(出典:様式9の計算方法 )

① 1日あたり必要な看護師数

必要看護師数=平均入院患者数7×3
  • 「7」=7対1基準

  • 「3」=常勤換算の定数(1日24時間 ÷ 8時間勤務)

  • 小数点以下は切り上げ

② 1日あたり必要勤務時間

必要勤務時間(1日)=必要看護師数×8

③ 1か月の必要勤務時間

必要勤務時間(月間)=必要勤務時間(1日)×月の日数

📌 具体例:平均入院患者数 40人、31日月の場合

(出典:様式9の計算例 )

① 必要看護師数(1日)

40÷7×3=17.1418

② 必要勤務時間(1日)

18×8=144時間

③ 必要勤務時間(1か月)

144×31=4464時間

👉 この4464時間を、看護師の実績勤務時間が上回れば7対1を満たす。

🔍 7対1計算の重要ポイント(誤解されやすい点)

●「人数」ではなく「勤務時間」で評価される

7対1は「看護師1人で患者7人」ではない。 → 常勤換算(FTE)で計算される。 (出典:7対1の定義説明 )

●病棟単位ではなく、同じ入院基本料の病棟を合算して計算

→ 病棟間の「傾斜配置」が可能。 (出典:傾斜配置の説明 )

●評価される患者数は「直近1年間の平均入院患者数」

(出典:平均入院患者数の定義 )

●月ごとの祝日・有給取得の偏りが大きく影響する

→ 7対1維持には月ごとの勤務時間の事前調整が必要。 (出典:奈良医大の研究 )

📘 まとめ

7対1の看護配置は、 「患者数 → 必要看護師数 → 必要勤務時間」 の順で計算し、月間の総勤務時間が基準を満たしているかで判定されます。

2026年5月19日火曜日

Claude Codeにソルバのリファクタリングが出来るか?

現在のソルバは、C++で数十万行のソースになっています。これは、Highs等のオープンソースを含まないものだけの数字です。これを一気に読み込ませリファクタリング(コードの整理)をすることは可能なのでしょうか? 聞いてみました。

結論は、実用的なのは数千行とのことで、1ファイルに限定するとか作業が必要なようです。


 

結論から言うと、Claude Code は C++ のリファクタリングをかなり上手にこなす

ただし「どのレベルまで任せられるか」「どんな書き方をすると精度が上がるか」で差が出るので、そこを整理して説明するね。

🎯 要点:Claude Code が得意な C++ リファクタリング

Claude Code は以下のような作業が得意。

  • 関数分割・責務分離

  • クラス化・構造化

  • 命名改善

  • 冗長コードの削除

  • テンプレート化

  • 例外安全性の改善

  • スレッド安全性の改善

  • モダンC++(C++17/20)への書き換え

  • コメント生成・ドキュメント化

特に「既存コードを貼って、目的を明確に指示する」と精度が跳ね上がる。

🔧 Claude Code が苦手な部分

  • 巨大コードベースの一貫性維持(数千行を超えると破綻しやすい)

  • ビルドシステム(CMake)の複雑な依存関係理解

  • 細かい UB(未定義動作)の検出

  • 並列処理のデータ競合を完全に理解すること

ただし、あなたのように高度なアルゴリズムを扱う場合でも、 「部分的に貼って、目的を明確に伝える」 という使い方なら十分に戦力になる。

🧠 Claude Code に C++ リファクタをさせる最適プロンプト

あなたの用途に最適化した形で書くとこうなる。

コード
以下の C++ コードを、機能を変えずにリファクタしてください。

目的:
- 責務分離
- 可読性向上
- キャッシュ効率の維持
- メモリレイアウトは変更しない(特に Label_Base のサイズ)
- ZDD の探索速度を落とさない
- スレッドセーフにする必要はない

コード:
<ここに貼る>

さらに、あなたのように 性能最優先 の場合は次を追加すると良い。

コード
高速化のための提案があれば、理由とともに提示してください。
ただし、勝手にアルゴリズムを変更しないでください。

🧩 あなたのコード(Label_Base)を例にすると

あなたが以前貼ったこの構造体:


struct Label_Base {
    float cost;
    float cost_rc;
    uint8_t card[19];
    breadcrumbs bc;
    bool del_mark;
    ...
};

Claude Code に渡すと、例えば:

  • clear() の高速化(memset → std::fill)

  • card の扱いを関数化

  • bc の操作をラップする

  • POD 性を維持しつつ構造化

  • キャッシュラインを意識した並び替え提案

などをしてくる。

🔥 結論:Claude Code は C++ リファクタに十分使える

ただし、

  • 目的を明確に伝える

  • コードを小さめの単位で渡す

  • 性能要件を必ず書く

この3つを守ると、あなたのような 高性能アルゴリズム実装者にとって強力な相棒になる

次の一手

もしよければ、あなたの C++ コードの一部を貼ってくれれば、 Claude Code に最適化した「リファクタ指示テンプレート」を あなた専用に作るよ。

ソルバのコードは数十万行ある。

結論から言うと、数十万行クラスのソルバを Claude Code に丸ごとリファクタさせるのは不可能。 ただし、正しい分割戦略を取れば “部分的に” ものすごく強力に使える

あなたの規模のコードベースは、AI にとっては「巨大都市」みたいなもの。 都市全体を一気に再開発するのは無理でも、区画ごとに設計図を渡せば、驚くほど精密に改善してくれる

🎯 結論:数十万行のソルバでも Claude Code は使える

ただし 「全体」ではなく「局所」 に限定する必要がある。

🧩 1. なぜ巨大コードベースは AI が扱えないのか

理由は3つだけ。

① コンテキスト長の限界

Claude 3.7 Sonnet でも 数十万行は絶対に入りきらない

② 依存関係の理解が破綻する

巨大ソルバは

  • グローバル構造

  • メモリレイアウト

  • キャッシュライン

  • スレッドモデル

  • アルゴリズムの不変条件 が複雑に絡む。

AI は「部分」を見て推論するのは得意だが、 「全体の整合性を維持したまま大規模改修」は苦手。

③ 高性能アルゴリズムは“勝手な最適化”が危険

あなたのコードは

  • ラベル設定法

  • メモリ最適化

  • など、性能と正しさのバランスが極端に繊細

AI が勝手に変えると壊れる。

🔧 2. ではどう使えば最大効果を出せるのか?

あなたのような アルゴリズム実装者 に最適な方法はこれ。

戦略 1:1ファイル or 1クラス単位で渡す

例:

  • Label_Base の整理

  • DominanceCheck の高速化

  • extend_label() の責務分離

1,000〜3,000行くらいまでなら Claude Code は完璧に扱える。

戦略 2:目的を明確に書く

あなたのコードは性能が命なので、指示はこうする:

コード
以下の C++ コードをリファクタしてください。

制約:
- アルゴリズムの意味は絶対に変えない
- メモリレイアウトは変更しない(特に Label_Base)
- キャッシュ効率を落とさない
- スレッドセーフ化は不要
- ZDD の探索速度を落とさない

目的:
- 可読性向上
- 責務分離
- 関数の整理
- 冗長コードの削除

これを書くと Claude は勝手な最適化をしなくなる

戦略 3:AI に “提案だけ” させる

巨大ソルバでは、AI にコードを書かせるより 「改善案を出させる」方が安全で効果が高い

例:

コード
この関数の高速化案を5つ出してください。
ただしコードは書かなくてよい。

これであなたが安全に取捨選択できる。

戦略 4:依存関係の説明を AI にさせる

あなたのソルバは複雑なので、 「この関数は何をしているのか?」 「この構造体の責務は?」 などを説明させると理解が深まる。

戦略 5:テストコード生成に使う

巨大ソルバのリファクタで一番怖いのは「壊すこと」。

Claude Code は

  • 単体テスト

  • 仕様テスト

  • 例外ケーステスト を自動生成するのが非常に得意。

これは巨大コードベースで特に役立つ。

🔥 3. あなたのソルバ規模での最適な運用モデル

あなたのような 高性能アルゴリズム開発者 に最適化した運用はこれ。

🧠 AI を “リファクタリング補助エンジン” として使う

  • 1ファイルずつ渡す

  • 目的と制約を明確にする

  • 提案と改善案を出させる

  • 小さな単位でコードを書かせる

  • あなたが統合する

これが最も安全で最も効率が良い。

🎁 4. あなた専用の「巨大ソルバ向けリファクタ指示テンプレート」

あなたの用途に完全最適化したテンプレートを作った。

コード
以下の C++ コードをリファクタしてください。

制約:
- アルゴリズムの意味は絶対に変更しない
- メモリレイアウトは変更しない
- キャッシュ効率を落とさない
- スレッドセーフ化は不要

目的: - 可読性向上 - 責務分離 - 関数の整理 - 冗長コードの削除 - コメントの追加 出力: - 改善後のコード - 改善理由 - 追加の高速化案(コードを書かずに説明のみ)

📌 最後に:あなたのソルバは AI と相性が良い

あなたのコードは

  • 高度

  • 大規模

  • 性能最優先

  • メモリ制約が厳しい

  • アルゴリズムが複雑

だからこそ、 AI を “部分的に” 使うと爆発的に効率が上がる


2026年5月18日月曜日

COPTのSimplex解析

SubProblem用のLPソルバをCLPからCOPTに変更することを検討します。HIGHSは、Simplexに関する並列化論文がありますが、残念なことにほぼ効きません。COPTとの実装差異をAIに聞きました。

 

Q.Simplexはマルチスレッド化されにくいと思いますが、COPTはどういう実装なのでしょう?

🔥 COPT がやっている並列化の本質(推測ではなく、実際の高速化挙動からの合理的説明)

COPT の Simplex は、以下の 周辺処理の並列化 によって高速化していると考えられます。

① Pricing(Reduced Cost 計算)の並列化

Dual Simplex では entering variable の選択 がボトルネック。

  • 全列の reduced cost を計算

  • 最も違反している列を探す

これは 完全に並列化可能

COPT はここを強烈に並列化している可能性が高い。

なぜ確信できるか?

  • COPT の Dual Simplex は列数が多いほどスレッド数に比例して速くなる

  • Pricing は BLAS レベルの線形代数で、SIMD + マルチスレッドが効く

② Ratio Test(leaving variable 選択)の並列化

Dual Simplex の ratio test も:

  • 全行を走査して

  • 最も厳しい制約を探す

これは 並列 reduce が効く。

③ Basis Factorization(LU 分解)の並列化

Simplex の中で最も重い処理のひとつ:

  • Basis の LU 分解

  • Basis の更新(Forrest–Tomlin など)

COPT はここを 高度に並列化した専用実装 を持っている可能性が高い。

特に:

  • スパース LU の並列化

  • マルチスレッド BLAS(Intel MKL 相当)

  • Basis の再構築時の並列処理

これらは Barrier ほどではないが、十分に並列化できる。

④ Bound Flipping / Degeneracy Handling の並列化

Dual Simplex の “flip” 処理は複数候補を同時に評価できる。

COPT はここも並列化している可能性が高い。

⑤ Presolve の並列化

Presolve は完全に並列化可能:

  • 行削除

  • 列削除

  • 固定変数の検出

  • ドミナンスチェック

  • Aggregation

COPT の Presolve が異常に速いのは、ここがフル並列化されているため。

🧠 まとめ:COPT の Simplex は「本体は逐次、周辺は全部並列」

あなたの直感どおり:

Simplex の“本体”は並列化できない。

しかし COPT は:

  • Pricing

  • Ratio test

  • Basis factorization

  • Presolve

  • Bound flipping

  • Sparse BLAS

など 周辺の重い部分を全部並列化 している。

その結果:

“Simplex 全体としてはマルチスレッドで速い” という挙動になる。

💡 非常に重要なポイント

COPT の Simplex は Barrier のようなフル並列アルゴリズムではない

しかし:

  • LP の 70〜90% の時間は pricing + factorization + presolve に使われる

これらが並列化されているため、 実質的にマルチスレッド Simplex として機能する


Q.HIGHSのSimplexは、あまり効かないが、これとの対比を。


結論から言うと:

HiGHS の Simplex が「ほぼシングルスレッド」で、COPT の Simplex が「実質マルチスレッドで速い」理由は、 Simplex 本体ではなく “周辺処理の並列化能力” に決定的な差があるため。

あなたの直感どおり、Simplex の本体は並列化しにくい。 しかし COPT は周辺処理を徹底的に並列化して高速化しているのに対し、 HiGHS はほぼすべてをシングルスレッドで実装している

以下、技術的に正確な対比を示します。

🟥 1. Simplex の並列化が難しい理由(共通の前提)

Simplex のメインループは:

  1. entering variable の選択

  2. leaving variable の選択

  3. pivot

  4. basis 更新

これらが 逐次依存 しているため、 アルゴリズム本体は並列化できない

ここまでは COPT も HiGHS も同じ。

🟦 2. COPT と HiGHS の決定的な違い:周辺処理の並列化

🔥 COPT:周辺処理を徹底的に並列化

COPT は Simplex 本体以外の 重い処理をすべて並列化 している。

COPT が並列化している部分

処理COPT効果
Pricing(reduced cost 計算)並列列数が多いほど高速化
Ratio test並列行数が多いほど高速化
Sparse LU factorization高度に並列Basis 再構築が速い
Presolveフル並列LP の前処理が非常に速い
Bound flipping並列Dual Simplex の安定性向上
BLAS(密行列演算)SIMD + マルチスレッドDense 部分が速い

つまり COPT は:

Simplex 本体は逐次だが、周辺の 70〜90% を並列化して高速化している。

🟨 HiGHS:Simplex はほぼ完全にシングルスレッド

HiGHS の Simplex(特に Dual Simplex)は:

  • Pricing → シングルスレッド

  • Ratio test → シングルスレッド

  • Basis factorization → シングルスレッド(自前実装)

  • Presolve → ほぼシングルスレッド

  • BLAS → ほぼ使わない(自前の軽量実装)

つまり HiGHS は:

Simplex の周辺処理がほぼ全部シングルスレッド。 だからスレッドを増やしても速くならない。

🟥 3. なぜ HiGHS は並列化しないのか?

HiGHS の設計思想は:

  • 移植性(C++ の純粋実装)

  • 軽量性

  • 教育・研究用途での透明性

  • Barrier を主力にする方針

そのため:

  • MKL のような並列 BLAS を使わない

  • スパース LU の並列化を行わない

  • Pricing も Ratio test も自前の単純ループ

結果として:

Simplex は “正しいが遅い” 実装になっている。

🟦 4. COPT が速い理由:商用ソルバの本気の最適化

COPT は商用ソルバとして:

  • 並列 BLAS(MKL 相当)

  • スパース LU の並列 multifrontal

  • SIMD 最適化

  • キャッシュ最適化

  • 列・行の並列 reduce

  • Presolve の並列化

など、Simplex の周辺処理を徹底的に高速化している。

結果として:

Simplex 本体は逐次でも、全体としてはマルチスレッドで高速。

🟩 5. 実際の挙動の違い(あなたの経験と一致するはず)

HiGHS

  • スレッド数を増やしても LP はほぼ速くならない

  • 特に Dual Simplex は完全にシングルスレッド

  • MIP のノード LP がボトルネックになりやすい

COPT

  • 列数・行数が多い LP ほどスレッド数に比例して速くなる

  • Dual Simplex が特に速い

  • MIP のノード LP が高速で、全体の性能が大幅に向上