OR学会の最適化まとめ

https://togetter.com/li/1193739

が最適化の参考になります。数理最適化を突き詰めていくと、ヒューリスティクス的な部分がどうしてもでてきます。これは、SATソルバー内でも同じで、NP困難な部分をやろうとすると避けて通れないのではないでしょうか。

たとえば、SATソルバーでは、長らくVSIDSというヒューリスティクスのー択しかありませんでした。
http://www-erato.ist.hokudai.ac.jp/docs/seminar/nabeshima.pdf

しかし、最近のSAT　Competitionを見ると新しいヒューリスティクスの実装が見られます。
これに対して、MIPの世界では、商用が主流でありBlackBoxで実装は分からないのですが、なにか改善を加えようとしたときは、やはり独自のヒューリスティクスによるケースが多いように思います。

私が現在やろうとしているのは、SATソルバー以外の第2エンジンです。

書籍は、次を所持していて参考にしました。いずれの入門用です。

１）組み合わせ最適化とアルゴリズム　久保
２）組み合わせ最適化　　穴井
３）最適化の手法　茨木
４）アルゴリズム・サイエンス　出口からの超入門　岩間

勿論MIPソルバーを作ろうという話ではないのですが、ある種のスケジューリング問題には、強いということを目指しています。一口にスケジューリング問題とはいっても、非常に広く、実インスタンスから、学術ベンチマークとインスタンス的にも幅広いものです。これはひとつのソルバーだけでカバー出来るものではない、と思っています。いつか、　海外の学術系ベンチマークと私が持っている実インスタンスを総合した結果を公開するサイトを作ろうと思います。