https://github.com/COPT-Public/COPT-Release
Firstオーダを評価したことがあるのですが、今回の論文を見てもやはり精度に難があり使えそうにはない、という風に見ます。精度が要求されないなら、例えばPageRankクラスのとんでもない規模や、機械学習には、その用途があるかもしれないのですが、NSPでは難しいと見ます。ジュリアンホール教授のHighsソースにも実装されていました。Highsソースを読んでいで、cuPDLPに気づきました。
商用ソルバとの性能差を指摘されるとすぐにお金の話が出てくるのは、いつもの事です。ジュリアンホール教授は、将来的には、有償のプレミアムバージョンを考えているようです。
HIGHSのIPMパラレル実装が今年度末までに予定されているので、そちらの期待の方が未だ高いです。
余談ですが、Highsチームには、MIPソルバ開発者が現在いないはずなので、今後の進捗にはあまり期待できないのですが、最近のソースを見た限り一応の形には、整いつつある印象です。ノードTreeのパラレル化を考えているようですが、これはさほど効果がないと思います。商用MIPソルバの最大差は、恐らくHeuristicsにあります。これは問題ごとに多くの最適化手法が存在するので、物量がものを言います。NSPもそのうちの一つです。しかし、これだけの少ない行数で、ここまで性能が出るとは、私も思っていなかったで、大したものだと思います。CBCのソースに比べれば圧倒的に読みやすいです。その中身については、何故かMatlabで解説がありました。
ともあれ、現在実装中のアルゴリズム５にHighsを入れようか迷っています。殆どのNSPでは不要なのですが、オールランドに構えるには、入れた方が良い結果になるかもしれません。とりあえず、入れ込んでみて評価してみようと計画中です。
既にLPソルバでは、GurobiをしのぎCOPT(中国)が世界を席巻しています。Gurobiがこのままでいるはずはないとは思いますが、LSIツールにせよ、最適化ツールにせよ、今まで米国が世界をリードしてきた構図が変わろうとしている時代の変革期だと思います。産業基盤の核になる技術は、そのまま国力に比例すると思うので、日本の若手研究者に頑張ってもらいたいと思います。
で、上記が何の役に立つかというと、実際的なNSPには関係しません。しかし、世界記録を更新するうえで、上記のLPソルバの向上は、至上命題です。今までCOPTのライセンスを一時的に借用しようと思っていたのですが、やはりそうなることになりそうです。
0 件のコメント:
コメントを投稿