古典アプローチで出来ることは未だある

良質な記事だと思います。 

進化する最適化技術 VOL.2～最適化問題を解決に導くNSSOLの技術と実績 －量子アニーリングは万能ではない－～｜TO THE FUTURE｜日鉄ソリューションズ (nipponsteel.com)

記事から抜粋します。

****

先ほどの巡回セールスマン問題の応用例に「配車計画」というのがあります。配達とか集配とかのスケジュールです。たとえば我々が最初に提示した答えを見ていただいたときに、「このお客さんは午前中に行かなければならない」とか「Aのお客さんのあとにすぐにBのお客さんにいかなければならない」などのより具体的な条件がポロポロと出てきます。

――なるほど。最適化問題は一つひとつ異なるというのはそういうことですね。

山本：そうです。お客様の固有の条件を考慮しないと使えるシステムにならないのですが、最初のヒアリングですぐに出てくるわけではないんですよ。

塩見：最初に大まかな業務の条件をうかがって、その条件で出した答えを見てもらうと当然ダメ出しされます。そこで再度ヒアリングして出た答えを見てもらう、ということを何回も繰り返すんですね。そうするとだんだん使える答えになってきます。

***

これは、お客さまのプロジェクトを私が記述する場合によく似ています。新規のプロジェクトの場合、稼動まで3ヶ月程度は見てください、というのは、こういう背景があります。生産計画みたいなプロジェクトでも同じなんですね。ただし、NSPの難しさは、コストをかけてSEを投入すればよいということではなく、月々の勤務でも制約が刻々と変化するという、コストがらみの独特の問題があります。NSPは、アプリのユーザインタフェースところが大かとは思いますが、最終的にはユーザ自身の教育に行き着くというのが持論です。

また、抜粋です。

***

そうです。ただ、単にアルゴリズムを用いれば解が出るというものではありません。まず、それぞれの最適化問題に向いているアルゴリズムを選定する、その見極めが難しいのです。言い方を変えると、適さないアルゴリズムを使うと、最適な解は出ません。

樋川：私たちの強みのひとつでもあるのですが、どういう問題にどういうアルゴリズムが合うかを知っていることがとても重要です。

――確かに専門家じゃないと選定は難しそうですね。

山本：最適化問題は一つひとつ異なりますし、すべての問題を解ける万能なアルゴリズムはないですからね。

***

私の場合、アイデアからアルゴリズムをひねりだし、実装、評価してみると上手く行かないことが殆どです。失敗の連続と言ってもよいと思います。今まで100を越えるアルゴリズムを考え、試し、没にするということを繰り返してきました。そんな工房の木屑の中でも光るものは、数点あります。ORに取り組んで4年足らずの私がやってもそうなので、未だ未だ古典アプローチで出来ることは沢山あると思います。

＜厳密解に拘る＞

古典的ベンチマーク中、GPOST-Bや、WHPPは、厳密解を得るのが難しい問題です。

Algorithm3は、当初NearOptimalなソルバという設計でしたが、上記を正しく解くには、やはり厳密解ソルバでないと無理という結論に達しました。なので、厳密解ソルバに作り直しました。

これらは、あるNSP特有の特徴を持ったインスタンスであり、実は現実のユーザのインスタンス中にも、希少な事象ではない頻度で出現します。私的には、NSPにおける根源的な問題の一つであると認識していますが、この難しさはまたの機会にお話したいと思います。