ラグランジェ緩和再び

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

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)となると、途端に解が難しくなります。この辺、解空間で考えて本当に空間が狭まっているのか、理論的に解析された論文はありません。試しに、ペア制約を外してみてください。簡単に解を見つかるケースが多いことでしょう。理論的にも興味深い問題です