INRC2 8WEEKS LBの改善が必要

 ２００時間廻しても解が得られないのが大半であることが分かりました。正確には、厳密解証明が出来ていません。約１０日計算機を廻しても解が得られないというのは、何か方法論からして間違っているような気がします。

どういう問題かというと、BranchingTreeの爆発という現象が生じて、調べるのが困難になるということです。Branching Treeを全て調べて、現在のUBを下回る解が存在しない、ということを言いたいのですが、調べれば調べる程、調べるべきNodeが増えてくる現象です。つまり、恐らくこの値は最適値であろうが、これより良い解が存在しない、という証明が出来ないのです。

そんなこと、どうだっていいじゃん？ほぼ最適値が分かっているんでしょ？と言われそうですが、アカデミックの世界で重要なのは、厳密解です。これが言えるかどうかで、その価値に雲泥の差が生じます。厳密解が分かれば、その後、高速なヒュリスティクスを開発することも有利になります。しかし、それが分からないと、現在の解がどれだけ最適値に近いのかが分からないということになります。量子アニーリングがどれだけ早くかつ精度よく問題を解けるのかは？最適値が分かっている最も困難な問題分野で、比較評価されるべきでしょう。そういった評価をする上においても重要です。量子アニーリング自体は、厳密解を求めるものではありません。厳密解を得るのは、依然としてクラシカルな方法によります。

NP困難な世界に挑むとは、そういうことだと思います。

この手の問題に対して一般的なMIPの対処方法は次の３つがあります。

■Strong Branch

■Reduced Cost Fixing

■Cut　Generator

です。代表的な組み合わせ最適化問題、例えば、VRP(Vehicle Routing Problem)問題では、Cut　Generatorが有効であることが報告されていますが、NSPに関しては殆どありません。

どのようにするか、するべきか考え中です。