超大規模問題に対してのこれまでの状況

 ■メインリニアソルバ

Defaultは、CLPです。

INRC2　８Weeksの規模に対しては、明らかにHighs　IPMが有利です。ソフト制約が基数制約にある場合は、より有利に働くと見ています。

Instance23/24については、今のところ、Highs PDLP一択です。（近い将来　Highs　IPMがGPUを使ったコルスキー分解をサポートするようになれば、PDLPを使わない可能性はあります。）

■サブ問題(RCSPP)

Defaultは、Complete　Graph方式です。Instance22では、Graph化が困難で、部分グラフ方式となります。それ以上の規模では、部分グラフの計算時間がネックとなります。サブ問題用にHighs　MIPソルバも実装しましたが、問題外に遅いです。

CLP＋CompleteGraphをグラフを使えば、例えば上の求解時間は、十数秒で済みます。

小・中規模では、PDLPは、思いのほか遅いのです。それに、Highs　MIPを使えばさらに遅くなってしまうので、選択肢からは除外せざるを得ません。

現状の課題は、超大規模問題の想定求解時間（一週間）内に解を求められる速度のサブ問題ソルバが無いことです。この規模では、Algorithm1も使えません。ひたすらBranch＆Boundしなければならないため、余計に時間がかかってしまうことから、より高速なサブ問題ソルバの開発が必要となります。

最近の論文関係では、ラベリングアルゴリズムがあるのですが、これについても遅すぎると、見ています。

A Labeling Algorithm for the Resource Constrained Elementary Shortest Path Problem

まとめると、超大規模問題では、今までに全く知られていない高速RCSSPソルバの開発が必要になる、ということです。