機械学習動向について

少しサーベイしてみました。

 2012.13349.pdf (arxiv.org)

MIPソルバーのBranch and Boundについて、

Neural Divingと、Neural Branchingについて提案しています。

[2110.14053] NeuroBack: Improving CDCL SAT Solving using Graph Neural Networks (arxiv.org)

CNFをGNN構造に展開して機械学習によりInitial　Phaseを予測しようというもの。

アルゴリズム3,4に関して、少しアイデアが浮かんできたので、今年前半で実装してみようと思います。組み合わせ最適化で最も重要、かつ難しいのは、整数解を如何に速く発見できるか？です。LBを推定するだけなら、かなり大きな問題でも１分もあれば、出来てしまいます。しかし、そこからUBを近づけるには、現状かなり時間がかかってしまいます。

上記に挙げた方法も無くはないと思いますが、NSPに関しては、未だ本質的改善が出来る可能性があると思います。