FirstOrderは、確かに速いのですが、収束の安定性に問題があることが分かりました。そこで、FirstOrderはDropし再びBarrierSolverを検討しようと思います。
＜Highsの高速化＞
HighsのIPXは、マルチスレッド化がされていません。Julian Hall教授にどうしてなのか聞いてみました。現在の実装では、部分的にマルチスレッド化は、容易に出来る部分はあるけれども、アムダールの法則により効果が出にくい、とのことでした。特に変数が制約数を大幅に上回ることがなければ、難しいとのことです。（開発に資金提供する気があるか？とも聞かれました。。）
これによれば、the crash basis (black bar at the bottom), for updating the basis during the interior point solve (dark grey), for running the linear solver (light grey) and for crossoverBasisに分類されるようです。なので恐らく、この全ての部分で並列化できないと効果が薄いという意味なのでしょう。
C++ソースを見ると、Eigenも使っていませんし、AVX２によるベクタライズも見当たりません。
IPXに手を加えることは難しそうなので、別にBarrierSolverを作ることにしました。アルゴリズムは、同じMehrotra のプレディクタ・コレクタ法です。
ボトルネックは、コレスキー分解で、
■解が近くなったときのランク落ち
■ベクタライズ（SIMD化）
■マルチスレッド化
がポイントになります。コレスキー分解については、Lapackの実装が最も速そうなのですが、ランク落ちについては、特にケアしていないので、やはり自分で書くしかなさそうです。（ちなみにLapackは、Fortranで書かれていますが、LLVMを使ってVisual Studioでもコンパイルすることが出来ました。良い時代になりました。）また、SuiteSparseについても見ましたが、対象とする超巨大NSPのインスタンス郡については、SuiteSparseを使用する意味が見いだせませんでした。まとめると、以下が設計仕様です。
■超巨大NSPインスタンス専用(それ以外は、Simplex使用)
■AVX2によるベクタライズ(それ以外はサポートしない）
■マルチスレッド
■クロスオーバは行わない
■Instance21で、10秒以下
0 件のコメント:
コメントを投稿