離散解は、リニア解の近傍にある

 前回、SATソルバで最適化しようとしても限界があることを示しました。SATソルバの解は離散解です。有体に言えば、(0,1)のどちらかです。これをどのようにシフトを表現するか？という話は、こちらでしました。

https://www.nurse-scheduling-software.com/japanese/publications/lecture_notes_for_basic_project_file_description.pdf#page=23

ところで、MIPソルバでは、リニアソルバの解⇒離散解にしています。SimplexやIPMでリニア解を得て、Branch＆Bound　または、CUTTING PLANEの手法で、離散解を得ています。

この手法の根底にあるのは、リニア解（0.0～１.0）の近くに離散解があることです。そんな保証はどこにもないのですが、何故か実務問題は、そういう事象が多い、ということです。

同じような例は、SATソルバでも観測されています。ランダム系列をSATソルバに食わせても、全くと言ってよいほど解けません。しかし、実務問題をエンコードして食わせてみると、思いの他、良く解ける、ということはあります。

（つまり、私達の生命活動はエントロピーに反する側、何がしら秩序だっている、ということではないでしょうか？）

そこで、リニア解から、離散解への変換ヒュリスティクスを考えます。最も単純には、四捨五入です。

話は飛びますが、ビタビアルゴリズムは、最尤復号方法と言って、A/D変換したアナログ値を確率的に最もあり得るデジタルビットに変換するアルゴリズムです。これは、ダイクストラ法の一変形であることが、ビタビ氏自身も認めていることです。

そこで、単純な四捨五入ではなく、最もありえそうなビットへ復号する変換を考えても良いと思います。で、その候補が、前回の手段となります。