ラグランジェ緩和再び

新たな発想で再度トライしています。ヒントになったのは、

http://www.bunkyo.ac.jp/~nemoto/lecture/opt-model/2008/duality1-2007.pdf

https://www.jstage.jst.go.jp/article/bjsiam/23/3/23_KJ00008829092/_pdf/-char/ja

https://slidesplayer.net/slide/11198759/

https://www.amazon.co.jp/dp/4320016475/ref=rdr_ext_tmb

です。特に、久保先生の本は、具体的な例題の積み重ねから一般論を導く方式で高度な概念を説明されていて本当に役に立ちます。最適化の本は10冊以上ありますが、この本が一番良いです。

ところで、問題は、規模が大きくなったときにメモリが大きくなりすぎることですが、大体目処がつきました。長い思索が必要でした。

一つの方式を採ったときに、性能はともかくとして、必要なのは汎用性です。「この問題は解けるけども、別な問題では、解が出ない、」では困ります。そこを何とかする必要がありました。どんな問題でも一応は解けるという、汎用性が商用ソルバでは重要となります。

実装は未だですが何とかなるでしょう。（で、やってみると性能が出ないというのが常ですが。）

それが、解決したとして、実務問題への展開には、最後の障害があります。一言でいうとペア制約に関する問題です。よく経験するのは、ペア制約でも、AさんとBさんが一緒に勤務しない、というのは、殆ど影響がなく容易に解が見つかりますが、Aさんが勤務したらBさん（A→B)、あるいは、その逆（B→A)、あるいはその両方（A⇔B)となると、途端に解が難しくなります。この辺、解空間で考えて本当に空間が狭まっているのか、理論的に解析された論文はありません。試しに、ペア制約を外してみてください。簡単に解を見つかるケースが多いことでしょう。理論的にも興味深い問題です

ドメイン移転

長年に渡って使っていたサーバ管理業者が全く連絡が取れなくなってしまいました。毎年契約更新の連絡が来ていたのですが、同時期になっても連絡が来ず、不安になってネット情報を見ると不安が的中してしまいました。最後まで連絡が取れない場合、メールサーバが使えなくなる可能性が生じてしまいました。NurseScehdulingのウェブは、既にXserverに移したので問題ないのですが、sugawara-systems.com のドメインが現在、身動きが取れません。最悪メールアドレスが変更になってしまう可能性があります。その際は、WEBも含めて告知します。ドメインの方は、来年まで有効であり、多分来年までは大丈夫だと思います。（ただ、管理業者が上の状態なのでいつメールサーバがダウンするとも知れません。）

127Bをリリースしました

ペア設定をオフにしているのにオンと認識してしまうバグを修正しました。（１２７Ａで入り込んでしまったようです。）

年末年始ＡＬ４の改善に取り組んだのですが、上手くいきませんでした。もう2年近くこの問題に取り組んでいるのですが未だ解決できていません。ですが、これを解決することなしには、世界に出て行けません。もう少し頑張ってみます。

よくある誤解

https://www.qmedia.jp/misunderstanding-of-qc/

とてもよくまとまっていると思います。
https://www.aist.go.jp/aist_j/press_release/pr2018/pr20181009/pr20181009.html
こちらについても懐疑的な印象を持っています。

二つの課題があると思います。
１）厳密解を出せない
SimulatedAnnealingに限らず、MetaHeuristicsによる解法は、基本的に厳密解を出せません。私の知る限り、厳密解を出せるのは、数理的解法か、SAT解法かのどちらかしかありません。（
その両方を備えたソルバがSC3です。）
２）解がない原因を示せない
制約モデルの設計・開発において、ハード制約とソフト制約を分けて設計を行うのは、人間が行う上では、必須であると思います。ハード制約の解がない原因を知る機構が設計においては、必須になります。（これも私の知る限りSC2/SC3のみの機能です。）

そもそも、通常のNSP問題においても、組み合わせ解空間が宇宙の素粒子数を超えることはよくあります。それでいて厳密解が求まる場合もあります。また、巡回セールスマンの世界記録も数理解法によるものです。同じベンチマークで論じるべきだと思います。

今年は、曲がりなりにもSC3をリリース出来、長年実現できなかったNSP記述の一般化形態をリリース出来ました。お正月にかけて、良い結果を出せるようにソルバAl4の改善を行います。

本年度は、業務終了です。ありがとうございました。

Simulated Annealing 実装の参考

こちらが、参考になります。
https://jetbead.hatenablog.com/entry/20180120/1516387673

いずれにしても問題は、NSPで近傍をどのように表現するかではないかと思います。
こちらも先人の知恵を拝借したいと思います。

D-wavesを用いたNSP

論文が公開されています。残念ながら、既存の方法との比較がないので、評価のしようがありません。

一方
https://www.itmedia.co.jp/news/articles/1911/20/news149.html
https://www.itmedia.co.jp/news/articles/1906/03/news033_3.html

のように否定的な記事もあります。

SchedulingBenchmarkサイトが更新

NurseSchduling問題の他に、Retail問題が追加されています。これが線形モデリングならば、フェーズタスク形式に記述することでSC3でも解けるはずです。しかし、残念ながら、線形モデリングではなく、2次形式によるモデリングなので、線形ソルバでは解けません。

NurseScehduling問題の方は、Instance20の最新BestValueが記録更新されています。しかし、私のソルバは、LB・UB既に確定させており、真の厳密解は、4769です。報告すれば、認められるでしょうが、英語サイトが準備出来ていないこともあり未だ報告していません。SC3による日本独自のベンチマークと、SchedulingBenchmarks及びNRC2のベンチマーク結果が整備出来た後の公開になります。その意味で、Algorithm4の改善は必須です。　鋭意改善中です。