2019年7月5日金曜日

量子アニーリング

とても勉強になるサイトがあります。なるほど、整数計画もSATを介してイジングモデルに変換できるのですね。 組合せ最適化に対する新しいアプローチです。

今までの組合せ最適化のアプローチは、大きく分けて次の3つです。

■MIP
 Simplex・内点法をベースとした線形ソルバをベースにCuttingPlaneで整数化を図る古典的なアプローチです。Cplex/Gurobi等、商用ソルバが圧倒的に強い分野です。

■SAT
 SATソルバーベースのアプローチです。

■Simulated Annealing
  に代表されるメタヒューリスティクス的アプローチです。

これに量子アニーリングが加わることになるのでしょう。ハードウェアの並列性を生かした解法
と認識しています。

全ての問題を一つのソルバが凌駕するということには、恐らくならないと思います。例えば、ブランク数独は、SATの独壇場で100x100でも難なく解けますが、MIPやメタヒューリスティクスでは、そうではないでしょう。1000人のナーススケジューリングという問題がもしあったとしたら、私ならMIPやSATは使わず、Simulated Annealingを採るでしょう。(というよりも、まともに解けない規模です。) ということで、問題分野・規模で、採るべきソルバーは変わってくると思います。


 
 





0 件のコメント:

コメントを投稿