Symmetry Breaking

 数理ソルバ的解法で問題となる現象で、対称性が求解スピードを悪化させたり、最悪の場合、誤収束してしまうことがあります。NSPの場合、無縁だと思っていたのですが、実は、結構な頻度で、その現象が観測されることが分かりました。

具体的には、

（A)ハード予定制約が全くないインスタンス

（B)結構ハード予定制約が詰まったインスタンス

をの求解速度を比較してみます。Algorithm1の場合は、Bが速くなることは殆どありません。このことは、探索空間の減少より解空間の減少が大きいことが原因と考えています。

しかし、Algorithm3の場合、Bの方が速くなることが結構あります。（ただし、Version１５２から、Algorithm3のStabilization方法を変えているので、目だった差にはなりません。）

同じテストインスタンスなのに挙動が反対になるReasonableな説明としては、Symmetry　Breakingによる補償効果があったのではないかと思います。