INRC2は、行き詰まっているので、気を取り直して、SchedulingBenchmarksを検討してみることにしました。
SchedulingBenchmarks残りの未解決問題は、2問あり、instance23/24です。この問題の課題は、２点あり、
１）超大規模につきコンパイルできない(128GBメモリでも不可）
２）リニアソルバが、遅すぎる
１）については、strandmarkさんの方法があります。
First-order Linear Programming in a Column Generation Based Heuristic Approach to the Nurse Rostering Problem
ヒューリスティクスな方法を取っているために、厳密な下界が求められないという問題があります。厳密解を求めようとすると１）がネックになります。また、リソース制約下の最短距離問題は、一般にラベリングアルゴリズムが用いられますが、検討するまでもなく遅すぎて使い物にならないでしょう。１）については、ひとまず置いておいて、２）について検討してみます。
First Orderの検討
これと、Simplex Solver CLPとの比較をしてみました。誤差は、1e-5に設定しています。
cPDLPCPU cuPDLP(Quadro P1000) CLP
instance19 46.7sec 21.6sec 2.6sec
instance20 14.8sec 6.7sec 9.6sec
instance21 41.5sec 16.2sec 78sec
規模が小さいとき（instance19以下）は、明らかにCLPが速いです。しかし、規模が大きくなってくるinstance20以上から、逆転する傾向となります。「大規模では、SimplexではなくIPMで」、がこれまでの定石でしたが、これからは、GPUも選択肢の一つになる、ということです。OR業界でのイノベーションです。
instance22/23の規模は、instance21の数倍以上なので、CLPでは、数分以上という値となり、もはや現実的ではありません。高性能CPUにすれば、2倍までは期待できますが、Simpilexは、マルチスレッドの恩恵が殆ど得られないことが分かっているので、CPUで何とかすることは出来ません。
cPDLPCPUは、FirstOrderのCPUバージョンで、GPUではなくCPUでFirstOrderを実行した値になっています。
ソースでは、cupdlp_def.hで、定義してコンパイルしたときの値です。
#ifndef CUPDLP_H_GUARD
#define CUPDLP_H_GUARD
#define CUPDLP_CPU 1
今のGPUを使用したとしても、instance23/24では、1分を超えてしまうので、やはり遅すぎます。出来れば、数秒以内、最悪でも１０秒以内としないと、現実的な時間内に解くのは難しいと思います。
ところが、Paper/MIPソルバのベンチマークで使われているのは、H100等であり、50万以上します。
なので、価格的にフェアな比較にはなっていないと思います。
現実的な路線で、クラウドで使用可能なのは、4090クラスです。
一方、P1000という上記GPUのCUDA数は、６４０、ベースクロックが1.3GHzです。GPUを最近の高性能の物に置換するとすると、
後述の理由によりメモリ16GBは、欲しいので、RTX 4060Ti
を考えると、CUDA数・クロック数比から、
4352/640*2.31/1.3=12倍
P1000に対して、最大で12倍の性能向上が見込める計算にはなります。よって目標の10秒以内を見込むことが出来ます。最悪、クラウドを使えば、4090を使用できるでしょう。いずれにせよ、GPUを使用することにより、リニアソルバ問題は、目途がついた、と考えています。COPTを使用しなくても、GPUで代替え可能であろう、と結論します。
一方でLLMの検討用にクラウドではなく、ローカルでそこそこ動くGPUが欲しくなります。AIが作成した記事のようですが、
これによれば、VRAM16GBは、必須です。よって、RTX4060Ti 16GBを選定しました。
次の課題は、超大規模問題を如何にコンパイルするか？です。
0 件のコメント:
コメントを投稿