Highs LPソルバの評価

 INRC2　8weeksでのLPソルバの使用検討を行いました。

下がその結果になります。現在使用中のCLPでは78sec近くかかっていて、これが為に、

全ての検討がネックになってしまっています。少しでも速いソルバが求められるところです。

これに対してHighsのIPMソルバは、crossoverなしで約7秒ですから、10倍近く速いことが分かりました。数年前に評価したときは、あまり変わらなかったと記憶しています。IPMソルバは、warm startが出来ないのが難点ですが、これくらい違えば、役に立ちそうなので、さらに検討してみたいと思います。（Highsアナウンスによれば2024年中にMT化を行うとありました。MT化がなされるとさらに速度アップが期待できます。2025中に実装されることを期待したいと思います。）

一方、HighsのSimplexは、頂けない結果となっています。数年前はDual Simplexしかなかったのですが、Primalもあったのでやってみましたが、惨憺たる結果となりました。CLPの優位性は揺るぎないです。

Highsは、PDLPのオプションとして使用できるようでしたが、本家の実装と比べて違うようで、結果には記していませんが上の本家の値よりかなり遅かったです。また、PDLPは、IPMと違ってwarm　start出来る筈ですが、そのようなソースになっておらず、まだまだ途上という印象です。

（）の数字が、OpenBlasを適用した結果となっています。少しだけ効果がある印象です。

一方本家のCPU版では、BLASを使うIFDEFも記載されていましたが、これが、かなり間違ったソースとなっていました。例えば、次のソースで、ddotを使うような記述があったのですが、これは、daxpyを使うべきでしょう。（その他幾多の箇所を修正しました。）

void AddToVector(cupdlp_float *x, const cupdlp_float weight,

                 const cupdlp_float *y, const cupdlp_int n) {

#ifdef USE_MY_BLAS

#ifdef USE_CBLASS

    

    //for (int i = 0; i < n; ++i) {

    //    x[i] += weight * y[i];

    //}

    cblas_daxpy(n, weight, y, 1, x, 1);

    //    return;

#else

  for (int i = 0; i < n; ++i) {

    x[i] += weight * y[i];

  }

#endif

#else

#define incx (1)

#define incy (1)

  return cblas_ddot(n, x, incx, y, incy);//BUG

#endif

}

以上見たように、規模が大きくなるにつれて、

Simplex ⇒IPM⇒PDLP（PDHG)

という流れは、確定的だと思います。

2024年は、PDLPに関する論文が色々出ました。2025年は、さらに改善されるだろうと予想します。