ソフト制約にすると何故遅くなる？

 それは、解空間が大きくなり、それだけスキャンするのに時間がかかるからです。

次の図は、INRC2　30W4のあるスタッフの不等式制約をハード制約化した場合のグラフです。不等式制約をハード化するには、許容エラーを0にします。

ソフト化するには、許容エラーを1以上にします。今、±３にしてみましょう。すると、上図は、下のようになります。少し太ったのが分かるでしょうか？

上記のようにすると視覚的に、理解できるのではないでしょうか？解空間が広がれば、それだけ見るべきデータが多くなり、計算に時間がかかります。一般に、ハード制約はグラフを縮小させます。ソフト制約は、グラフを肥大化させます。

上記は数理ソルバの話ですが、ヒューリスティック系にについても同様の議論が成り立ちます。