新しいAlgorithm1のアーキテクチャ

 従来のAlgorithm1のアーキテクチャは、パラレルSATソルバです。ポートフォリオと呼ばれる形態を取っています。これは、同一の問題を異なるパラメータで解く方式です。この方式の問題は、

■決定的にならないこと

■大して高速化しない。良い場合もあるが、シングルスレッドの方が良い場合もある

内部のソルバ間は、学習節を交換しながら進みます。マルチスレッドであっても、基本的にアルゴリズムは、一つです。つまり多様性に乏しく、実使用時の様々な問題に対して常に最適なアルゴリズムであるとは言い切れない、という問題がありました。

そこで新しいアーキテクチャは、次のようにします。複数のアルゴリズムを並列に走らせます。問題の形態によっては、得意なアルゴリズムは変わってきます。複数のアルゴリズムを一機に走らせます。アルゴリズムを選びません。どの問題に対して、どいうアルゴリズムが親和性があるか？判定するのも時間がかかってしまうからです。アルゴリズム間では、情報を交換しません。先に着いた者勝ちという、単純な構想です。

懸念としては、駆動インスタンス分のメモリがどうしても必要になります。キャッシュヒット率が下がり、シングルスレッドよりも遅くなることが考えられます。この傾向は、規模が大きければ大きい程顕著になります。

これによる効果としては、

■安定度が高い。プロジェクトが決定的になる確率が高い

■求解速度向上

デメリットとして

■解は、一つのみ

■原因解析機構は、後回し

■リニア解の最適値には、必ずしも合致しない（準最適解）

■環境によっては、遅くなる懸念（メモリキャッシュ問題）

なので、Algorithm5として実験的に実装する予定です。Algorithm1は、そのままとします。

目標は、

１）解を決定的にする

２）ICU70人問題の求解時間6分を2分以下にする

３）SchedulingBenchmarksの記録更新

４）INRC2の記録更新

にありますが、これにより１）２）について、ほぼ達成見込みとなりました。

実使用時の改善となります。しかし、本題の３）４）の改善には、全く寄与しません。

学術問題のベンチマークと実使用時の問題とでは、問題の性質が全く異なるからです。言い換えるならば、Algorithm1/5は、実使用時の問題用、ということです。

学術問題には、学術問題用のアプローチが必要であり、Algorithm5では歯が立ちません。

しかしながら、そこも含めて改善しておかないと、記録更新に到底届くものではありません。今回の改善もそのために必要なステップです。