CuPDLPの高速化は難しい

 ソースを詳しく検証してみました。

GitHub - COPT-Public/cuPDLP-C: Code for solving LP on GPU using first-order methods

PDLPは、メジャーループとマイナーループをもっています。

マイナーループでは、下で示したブロックが時間を食います。

＜時間計測する場合は、DeviceSynchronoize（）で挟む＞

最初に嵌ったのは、ボトルネック部を見極めるための時間計測の誤りでした。

各ブロック間に、DeviceSynchronoizeを入れないと、時間計測が正しくありません。上図は、DeviceSynchronoizeを各ブロックにいれたものですが、トータルの時間が大きくなってしまいます。 cudaSetDeviceFlags(cudaDeviceScheduleSpin);は、行ってもこれは効いていないようで、終了を待たずに次のブロック処理に入るためのようです。

で、各ブロックを自分なりに手を入れてみたものの、速くなるどころか、オリジナル（COPT)の数分の１の速度にしか出ず、既に最適化したソースになっている、ということが分かりました。

＜double /singleは、２倍程度以下＞

次に行ったのは、double ⇒single float にすることでした。これによる効果は２倍以下でした。

<ボトルネックは、DOTとSPMV>

DOT処理部は、別に検討することにして、メジャーループ・マイナーループ共に必要なのは、SPMVです。余談ですが、PDLPの前身は、PDHGです。

Primal-Dual Hybrid Gradient Algorithm (PDHG) — odl 0.8.1 documentation

PDHGにAdptiveStepSize等を加えたのが、PDLPになります。

2501.07018

＜SPMV時間の検討＞

SPMV処理に関わる転送時間を計算してみます。

　(ＮＮＺ数ｘ３＋ＸＣｏｌｓ数x2 +YRows数x2)*sizeof(cupd_float)

これにＶＲＡＭ帯域

Ｐ１０００：８０ＧＢ／Ｓｅｃ

４０６０：２７０ＧＢ／Ｓｅｃ

を考えると、数us以下になるはずです。しかし、実際に観測されるのは、この10倍程度以上の値です。CUDAの起動時間もあるのですが、それにしてもキャッシュミス等、未だ何かあると考えざるをえません。

ということで、未だ検討の余地は、あると考えます。ＣＯＰＴが使っているＳＰＭＶは、NVidia cusparse で、これ以上に高速でないと意味がありません。

＜高速ＳＰＭＶの検討＞

サーベイ論文が参考になります。

A Systematic Literature Survey of Sparse Matrix-Vector Multiplication

具体的な実装例は、次です。

https://github.com/PAA-NCIC/AlphaSparse/tree/main

https://github.com/KaHIP/HeiStream?tab=readme-ov-file

いずれも、グラフパーティションテクニックを駆使して、キャッシュが効く程度のブロックに分割するというところは共通です。そうなると、コンパイル時間がプラスされるので、普通に考えると使えません。が、その発想は、使えると思います。

とりあえずは、上記の発想が正しいか？検証してみようと思います。

Q.変則2交代の制約を一から作れるようにしたい

 Ans.

一から作れるようなレクチャ資料をPDFと動画で作成して行きたいと思います。もし、何か

「こういう場合は、どう書いたらよい？」

という具体的な質問がありましたら、それを盛り込んで作成してみたいと思います。サポートまで質問をお寄せください。期間は、４月末日までです。

背景：

一昨年、ある大学病院で、スケジュールナースを導入して頂いたのですが、この説明会の資料にあるようなスタイルにして行きたい、とのご要望を頂きました。

https://www.nurse-scheduling-software.com/japanese/publications/Schedule_Nurse_Presentation_materials_for_multi-ward_hospitals.pdf#page=40

そこで、レクチャ資料を作ることにしたのですが、その主旨から、特定の病院向けではなく、一般の自習したい方々にとって役に立つ資料の作成を思い立ちました。

また、２年ほど前から、変則２交代勤務パターンが増え、特に昨年は制作した看護師勤務表の全てが変則２交代でした。潮流は、変則２交代にあるのは間違いないですが、元来の長入明休パターンを阻害するシフト、遅番や３交代といった例外的な事情も考慮せざるを得なことも散見されます。元来的な意味では、それらは考慮されていなかったと思いますし、必ずしもリーズナブルなパターンとは言い難いと思いますが、既に出来上がってしまったパターンは、考慮せざるをえません。

そういった例外的な事も含めて、あらゆるパターンを制約化出来る力を養う講座にしたいと思います。

さらに、長日明に伴う実際的かつ特有の問題が二つあります。これらは、現在問題視されていませんが、具体的なデータで、その問題点を指摘したいと思っています。（人力で作っている師長さんは、薄々気づいていると思いますが。）

定性的な指摘が出来るのは、物理限界・近くまで配置可能なスケジュールナースだけです。ソフトウェアの性能の問題でそれらの問題が起きているのではない、と言い切れるだけの実力が備わっていないと指摘することはできないからです。

⇒資料は、以下にまとまっています。全400ページ近くあります。動画による解説は、現在サポートが非常に混んでいまして、しばらく先になります。

https://schedule-nurse.blogspot.com/2025/04/2_24.html

顧客メンテナンスマニュアル（変則2交代）

ある公立病院病棟の顧客用メンテナンスマニュアルです。顧客に関わる情報は伏せています。

 こちらはある程度定型ですが、公休数のカウントに半日を含める点と、夜勤専従の扱いに特徴があります。

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

医師当直表・拘束表 メンテンナンスマニュアル

顧客向けのメンテナンス用マニュアルです。（個人名等は伏せています。）

このプロジェクトは、スケジュールナース史上、最難度です。地方の公立病院であり大学病院からの派遣医師によって成立しています。それもあって、とても複雑です。　

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

ご覧になると分かる通り、プロジェクトは作成して終わりではなく、数々のメンテナンスをしながら、リファインしています。この道１０年の私ですら、バグなしには、稼働できませんでした。また、このような複雑な仕様を

■それまで作成していた医師から聞き取り

■まとめる事務屋さん

の力なしには、実現できなかったと思います。仕様を他人に正確に伝えるのは、本当に難しいことです。このことについては、次で書きました。

https://schedule-nurse.blogspot.com/2025/01/blog-post_6.html

このプロジェクト作成を通じて、複雑な仕様に対しては、AIで何とかなる問題ではなく、隅から隅まで人間があるべき姿を理解していないと、システムは構築できない、ということを実感しました。何が正しい、ということを言えなければ、AIにしても人間にしてもどのようにしてよいかは分かりません。ところが、これを言葉でいうのは、難しいのです。

プロジェクトの中には、このような難しいプロジェクトもあります。大抵のプロジェクトは、フレームワーク的な一定の型にあてはまり、サンプルを見ながらお客さま自身が、構築できると思います。しかし、中にはこういう、お客さまが一から作るのが不可能に近いプロジェクトもあります。そうした場合には、プロジェクト作成サービスをご利用頂きたいと思います。

多病棟向けスケジュールナース説明会資料

ある病院での説明会資料です。

 スケジュールナースを 使った勤務表作成 ご提案資料

特に説明会時から加工していません。

難問を解くことには意味がある

 ずっと解けない問題INRC2　８WEEKSに取り組んでいますが、果たしてこんな事をしていて意味があるのだろうか？　と自問自答することがあります。

その難問は、無数にある世の中に存在するインスタンスの1問に過ぎません。つまり特殊な事例でしかないのです。それを1問解いたところで何になるというのでしょう？それよりは、使いやすいUIの開発や、モデリングのAI化を実装した方が人のためになるのでは？　という人もいるでしょう。

今回、難問を解くにあたって二つの技術開発を行っています。

１）数理ソルバ用のSoftCardinality実装アルゴリズムの開発　

２）CUPDLPの中規模用途での高速化　

１）については、前回述べました。２）については、その方針を示しました。

https://schedule-nurse.blogspot.com/2025/02/pdlp.html

これにより、INRC2とSchedulingBenchmarksの未解決問題を全て解く、という野心的な試みの最中です。その結果として、

■NSPにおいて、決まった手順によって、解ける問題領域が増える

ということだろうと思います。特殊な事例を解く技術を開発することによって、一般化した実務問題にも適用できます。大袈裟な言い方をすると人類の知をほんの少しだけ広げる意味があると思います。

The illustrated guide to a Ph.D.

NSPに関して、それが出来る..最も近いところに居る人間は、私である、ということです。無数とも言える失敗の先に最適なアルゴリズムがある、と信じて取り組んでいます。技術開発は、出来るか出来ないかは、出来るまで分かりません。しかし、最も近い人間がやらないで、誰が出来るというのでしょう？それが、拘り続ける理由です。

アルゴリズム３ ソフトCardinality制約の改善

 Cardinalityとは、数を数える制約のことです。基数制約とか不等式制約とか、言い方の変遷がありますが、皆同じです。制約の範疇を分けるものとして、

Cardinalityか、NonCardinalityかの２種類があります。

■Cardinality　　　ー数を数える制約

■NonCardinality　ーブール演算制約

一般に数理ソルバの制約は、全てCardinalityで記述されます。従い、数理ソルバは、Cardinality制約が得意です。というより、数理ソルバは、Cardinality制約でしか記述できません。ブール演算は得意ではありません。一方アルゴリズム１系のソルバは、ブール演算が得意で、Cardinality制約は苦手です。Cardinalityのスケジュールナースの特徴は、常に、許容範囲というソフト範囲が明示されていることです。ソフト範囲が限定されて、ある値を境にハード制約になる、というのは、恐らくは、スケジュールナースユニークであり、他のソフトでは扱わないと思います。便利な反面、初心者には、とっつきにくく,これで苦労された方も多いのではないでしょうか？実は、ブール演算で、数を数えようとすると、必然になるのですが、これについては、別の機会に。

余談ですが、情報は全て0/1だけで表現できることを示したのは、シャノンという学者です。0/1が最もプリミティブな表現です。そこから出発するのがブール演算です。なので、数を数えるということもブール演算で表現可能です。つまり、コンピュータの動作の最も基礎は、０/1であり、その合成集合は、AND/NOT/ORの３つのブール演算オペレータでどんなものでも合成出来ます。

一方、制約は、２種類しかありませんという話はよくします。一つは、ハード制約、もう一つはソフト制約です。

数理表現への橋渡しは、グラフ理論上のグラフになります。制約理論で言えば、リソース制約下の最小パス問題(RCSPP)、になります。実装という観点でみると、下のような難易度になります。

                    　 ｜　Hard　 |   　Soft

ーーーーーーーーーーーーーーーーーーーーーー

Cardinality　　　｜　　難　|　　超難

NonCardinality　｜　　超簡単　|　　簡単　　　　

つまり、Soft　Cardinalityの実装は超難しいのです。上のHard　Cardinality制約については、2022年に特許化しましたが、そのときは、Soft Cardinalityについては解決していませんでした。

今回INRC2の難問を解くに当たって、副産物として出てきたのは、このSoft Cardinalityに対するアルゴリズムです。

未だ解けてはいないし、改善も進行中なのですが、ドラスティックな変化があるので、中間報告しておきます。

下は、池上ベンチをアルゴリズム３現行スケジュールナースで解いた様子です。

アルゴリズム１は、数秒で解けるのに対して、このように時間がかかっているのは、Soft　Cardinalityのコンパイルに時間がかかっているからです。

それが、現在開発中のソルバでは、

となっています。これは、Soft　Cardinalityのコンパイル時間を削減出来たからです。（それでもこの問題に対してAL1の優位は変わりませんが。）

例えば、多数のCardinlaityがScheduling　Benchmarks　Instance13では記述されていますが、これを全てソフト制約にした場合は、現行スケジュールナースではコンパイル出来ません。しかし、この技術を使うとコンパイル出来るようになります。数理ソルバに取り組んで以来、長年の研究によりようやく満足できる性能を発揮できるようになりました。

これにより、数理ソルバを用いて解ける可能性が高まることを意味します。Al1/3共、各々得意な領域はあるのですが、使用比で、現状100:1から100:10位になる位になるのではないかと思います。特に厳密解を知りたい場合に有用になる筈です。

また、Al1とAl3を融合した万能ソルバも視野に入っています。これにより最終目標である、常に厳密解にもっとも近い解を示すアルゴリズムを提示できる可能性が高まりました。

アルゴリズムというのは、問題の解き方です。ソフトウェアの基礎になります。分岐とループ(IF文、For文）さえあれば、何でも処理できるを示したのは、チューリングという学者です。

NSPに関して、このアルゴリズムを使えば、常に最適もしくは、最も最適に近い解が得られる、というのは分かっていません。というか、そもそもNP困難なのでそれを示すことは不可能であろうと思いますが、実用的な意味で、今後数十年は使えるアルゴリズムを示せたらそれは、NSPにおいてプリミティブな事だろうと思います。