instance24失敗

 instance24の求解に失敗しました。LBを求めるところまでは、目論見通りでした。COPTを使用しても、相当な時間がかかりました。問題は、相当のBranchの後、LPソルバの目的関数値が整数になったときの整数化で失敗しました。

整数化には、AL1アルゴリズムを使用しているのですが、こちらの制御が戻ってこないというものです。原因としては、instance24は、MaxSATでは、巨大すぎるということだろうと思います。

MaxSATの得意領域は、計数制約が少ない範囲で、boolean operationが多数になればなるほど得意になる傾向があります。

ところが、instance24は、150人、365日、32シフトという超超巨大インスタンスであり、多数の計数制約があります。これがメモリを食い数十GBになります。instance22（50人、365日、10シフト）までは、問題なく動作したMaxSATソルバも限界を超えた、と判断しました。

MaxSATソルバが、30日、30人といった程度の通常インスタンスでは、無類の強さを発揮するのは何故かというと、学習機構を持っているからです。逆に言うと、

割り当て⇒エラー⇒原因分析⇒同じ原因のエラーを抑止

という学習機構が有効に働くインスタンス範囲では強い、ということになります。メタヒューリスティクスは、基本的にその機構がありません。

割り当て⇒エラー⇒スコアを上下

という単純な機構です。原因分析機構が無い分、構造は簡単で、メモリも食いません。

ところで、超大規模インスタンスでは、大規模すぎて、そもそも学習が殆ど効かないと思われます。（正確には、学習しても、探索範囲が膨大なので、同じ原因にぶちあたる確率が小さい。）なので超大規模インスタンス領域では、メモリが軽い分、メタヒューリスティクスが有利となります。

＜対策＞

そこで、大規模用メタヒューリスティクスを開発することにしました。で、どうせなら汎用アルゴリズムとしてラインアップしてもよいかな？とも思います。例えば、ローカルソルバをAL4として加えるアイデアです。

■AL1:MaxSAT

■AL2:Highs MIP Solver

■AL3:Mathematical Solver

■AL4:Local Solver

そうなると、全方位のソルバ群が完成することになります。

＜スケジュール＞

2月は、MCPテスト、評価。

3月に、ローカルソルバと、make_feasible_model(別途解説）の実装を予定します。なので、世界記録の更新予定は、4月です。それまで破られなければ。（LBの値は、判明しましたが、それまでは、公開しません。）