Barrior Solverのサーベイ

 大規模でSimplexベースだと、途端に求解時間が長くなります。SchedulingBenchmarksのInstance21以上が実質的に解けない主因になっています。Strandmark さんのようにFirst　Orderを使う手法がありますが、Algorithm4では、厳密解にこだわっていて、Simplexでもない、First OrderでもないとなるとBarrior　Solverに期待をかけるしかないということです。

SCIP品野先生が書かれた

http://www.orsj.or.jp/archive2/or64-4/or64_4_238.pdf

が参考になります。Julian Hall教授のHighsは、以前評価しましたが、Performance的に今ひとつという感じでしたので、もう少しないか探してみました。（Coptも期待したほどではありませんでした。既報）

http://plato.asu.edu/bench.html

こちら、Barrior　Solverのなかで、Tulipという新しいソルバを見つけました。Juliaで書かれています。下記がPaperです。（関係ないのですが、上記LPソルバ中、MindOptにしてしろCoptにしろ中国系企業だと思います。LP Solverは、最適化のみならず、機械学習においても基幹技術だと思いますが、日本系が入っていないのは残念なことです。最適化界隈でなにをするにしても、LP Solverを避けて通れないので、いじっているかいないかで、上位アプリにも影響を及ぼすと考えます。この辺、かってLSIの合成ツールでも同じように日本企業は、入っていけませんでした。LSI設計において、合成ツールの世話にならない設計はない訳で、似たような差を感じてしまいます。）

https://arxiv.org/abs/2006.08814

商用ソルバーとの差は、かなりありそうですが、インスタンスによっては、凌ぐ場合もあるということで、見てみようかなと思います。