MIPソルバで解ける規模

 任意の規模が解けるという意味では、スパコンでもバイナリ70変数程度と言われています。これは、１e21程度の探索空間です。（スパコンは、一秒間に一京、1e16程度のオーダで浮動小数演算を行えます）

普通のナーススケジューリングでも、(7shifts+1offstate)**(25staffs*31days)で、

(7+1)**(25*31)=7.8e699 

ですから、スパコンを持ってきても、解けなくて普通のような気がしてきます。それでも、1e15000オーダのナーススケジューリング問題が解ける例が出て来るのは、一体どうしてかというと、「そこに制約があるから」ではないでしょうか？　

任意のというのは、ランダムと言い換えても良いでしょう。私に言わせれば、ランダムの反対語は、偏り、数式、制約だと思います。普通に考えると、制約があると自由を奪われるので、不利なような気がしますが、実際は、そこに制約があると、解けない規模でもなぜか解けるようになるのです。

ΣAi<=RHS[Lower:Upper];

制約は、解空間を減少させます。同時に探索空間も減少させます。

ここでいう制約は、ハード制約の意味です。ソフト制約は、なんら探索空間を減少させないので、嬉しくはないです。

しかし、ハード制約のみだと、しばしば解がない状態を経験します。ですので、度々力説している通り、ハードとソフトを適切に織り交ぜることが良い制約の仕方となります。

この為には、そのインスタンスについての深い理解が必要となります。同じような制約でも、ある職場では、常識的にもハード制約であるのが、別の職場では、ソフト制約的な扱いになることは、よく経験します。そのインスタンス毎にフルカスタマイズ出来ることが理想的です。