Heuristics, SAT Solver,Mathematical Solver

 高精度かつ高速に最適化問題を解くには、各々得意な領域があり、問題に応じて使い分ける必要があります。高精度の極致が、厳密解です。

SATSolverは、言わば、2値に対する厳密解です。SATとUNSAT、これしかありません。ですので、ソフト制約がない、ハード制約のみの制約については、問題の性質とよく符合します。

ところが、一般には最適化問題というのは、SATとUNSATつまり０/1のデジタルではなく、0~1間のアナログ的なものです。0/1問題ならば、人工的に作られた問題（コンピュータで作成された問題、恣意的に極端に解スペースが小さい問題）でないなら、探索スペースに対して解スペースの比率もそれなりに大きいことが期待できると思います。そういう問題に対してSATは、強いと考えられます。

これに対して一般の最適化問題というのは、探索スペースに対して、最適解スペースは、狭いと考えられます。たとえば、通常のNSP問題でも、探索組み合わせ空間が、宇宙に存在する全原子数にを超えることは、珍しいことではありません。事実、SchedulingBenchmark　Instance15における最適解というのは、1個ないしXX個程度だと思います。（証明した人はいませんが、実際にソルバを数日廻してもないのでそのような感触です。）

地球上にある一個の砂粒を探し出すよりも、遥かに難しい問題、であることが理解できると思います。このような解スペース/探索スペース比が非常に小さい問題については、SAT的手法よりも数理的ソルバの方が有利である、ということは言えると思います。

どのレベルの最適化を狙うからは、ユーザ毎に違うと思います。問題と求める最適化レベルにより、選択するソルバも異なる、ということは言えます。多くの場合Algorithm1が実務的です。厳密界もしくは、下界を知りたい場合は、Algrithm3が有用です。SC3で搭載しているアルゴリズム群は次の通りです。

Algorithm1　汎用、SAT、原因解析用

Algorithm2　厳密解用　MIPソルバ。Highs

Algorithm3　厳密解用、数理ソルバ＋SAT

Algorithm4　厳密解用、数理ソルバ

ヒューリスティクスは、搭載していません。正確には、SAT内および数理ソルバ内に、多くのヒューリスティクスアルゴリズムは搭載されていますが、NSP用としてのそれは搭載していません。問題規模が小さい内は、MIPソルバの独断上で、それ以上ではSAT、そしてAlgorithm3の順で有効です。これは、SATソルバ内では、学習機構によるフィードバックにより探索空間を狭める手法を取っていることが、ヒューリスティクスからの改善になります。ところがある程度規模以上に大きくなると、とてもフィードバックでどうなる規模でもなくなってきます。そうしたところでヒューリスティクスの出番、と考えられますが、未だその必要性に出会ったことはありません。

まとめると、NSPに関して、下のような得意領域グラフになります。インスタンス規模が小さいとき、精度が高いのは、MIPソルバです。SATソルバは、精度は劣るものの、とても広い問題領域に対応します。汎用的と言ってよいでしょう。AL3は、ある意味でMIPソルバとSATソルバのHybridと言ってよいと思います。MIPソルバよりも大きなインスタンスが可能で、精度も高いのですが、全ての問題に対応できるという訳ではありません。

なので、まずはAL1で、しっかりプロジェクト構築することをお勧めします。AL1は、原因解析機構もあるので、プロジェクト開発に向いています。

なお、NSPに関して、これまで4件の特許査定を取得しています。国内はもとより国際的にもこれだけNSP　Solverの知的所有権を有している機関はないのではないか？と思います。（アプリの類や、MIPソルバの使い方の面で有している企業は沢山あるかと思いますが、ソルバそのものの特許を保持している企業は、日本では極端に少ないです。問題の核心に挑む企業が少ないことが杞憂に終わればよいのですが、最近の中国企業の旺盛(COPTやMindOpt)を見るにつけ、技術的にも遅れを取るようになった、と思うのは私だけでしょうか？）