ハード制約とは？

 覚えて頂きたいのは、ハード制約を破った解は存在しない。言い換えると、ハード制約を破らないように制約を記述する必要がある、ということです。

ですから、

必ず守るべき制約でもあり、必ず守れる制約でもある必要があります。

一方で、ソフト制約がありますが、こちらは基本的に破っても解がない、ということはありません。しかし、破ると重みによるコストが発生する仕組みになっています。システムはコストを最小にしようとする系ですので、コスト最小、つまりソフト制約に対して出来る限り守ろうとするように働きます。ソフト制約には重みを指定する部分があり、重い制約を破ることは重いコストがかかるので、システムは重い制約ほど守ろうとする力が働くことになります。

ならば、全てをソフト制約にすればよいでは？解がないというのはまったくもって理不尽だ...

と思われるのはごもっともなのですが、結論から申しますと、適度なハード制約とソフト制約が混在していることが良いシステムです。どの位がよいかというのは、お任せ頂きたいのですが、試行錯誤していくうちに見えてくる部分もあるでしょう。

技術的に言うと、ソフト制約は、全く探索空間を減らしませんが、解空間を大幅に増やします。最適化解の設計者として、実はこのことは、あまり嬉しくありません。一方で、ハード制約があると、探索空間を大幅に減らしてくれることがあります。これだけからすると嬉しいのですが、同時に解空間も減らしてしまいます。解が見つからない可能性も増やしてしまいます。

スパコンをもってしても、ランダムなバイナリ変数が解けるのは僅か、70変数程度として知られています。ナーススケジューリング問題の規模、Search　Space　１googol=1e100を上回る規模が解けるのは、実は、ハード制約のおかげでもあるのです。