Feasibility とは？

 Feasibility PumpのFeasibilityとは何でしょうか？　実現可能性と訳されますが、OR用語でなじみがないと思います。これは、スケジュールナース用語にすると、「解がある」ということです。

「解が存在する」とは、ハード制約の全てを満足しているという状態を指します。スケジュールナースでは、よく「解がない」状態が出現します。ハード制約が一つでも満たせなければ、解は存在しません。この逆で、ハード制約の全てを満足しているという状態が、feasibleです。feasibleの反対が「解がない」です。

特に開発時には、見たくはないのですが、出てくる経験をした方も多いのではないでしょうか？まとめると、

「解がない」　⇔　「解が存在する」＝Feasible

ということになります。シフト最適化を行う場合に、数理ソルバは一般に、

⇒Feasible ⇒最適化（コストの最小化）

という2段構えのプロセスとなります。最初に、ハード制約を全て満足する解を見つけて、其の後にコスト最小化となります。

数理ソルバの場合は、Feasibleと言い、SAT業界の場合は、

「解がない」＝UNSAT　⇔　「解が存在する」＝Feasible　＝SAT

と言う対応になります。同じことを違う言葉で言っています。

ところで、スケジュールナースの場合、Feasibleは、どの時点で分かるのでしょうか？

実は、赤字がなくて o　xxxが出たならば、既にfeasibleです。

上の例で、最初のo は、0.396secで出ています。この時点で、feasible、つまり全てのハード制約を満たしていて、以降は、ソフト制約の割り当て最適化を行っています。スケジュールナースの場合、このfeasibleに要する時間は、大抵の場合数秒以下です。もし10秒を超える規模のプロジェクトでしたら、それはかなりの大規模プロジェクト、ということが出来ます。時間のかかるのは、コスト最小化プロセスです。こういう風に解改善の様子が目で見て分かるシフト最適化ソルバは、スケジュールナース以外多分ないと思います。