TTS2

 このサイトは、WEBアプリと思っていたのですが、単にブラウザの音声合成機能を使っているだけのようです。ならばと、Windows１０の音声合成も使ってみたのですが、ブラウザとはなぜか雲泥の差です。IBM　Watsonも使ってみたのですが、WEBデモの質が何故か得られないので止めました。

制約付最短経路問題 離散解法か連続解法か

NSPの部分問題である制約付最短経路問題をできるだけ速く解くというのは、NSP最適化において重要です。 

二つのアプローチがあります。言い換えるとグラフ解法か、分岐限定法かということです。

どちらが速く求まるか？というのは、問題によります。要因として大きいのは、基数制約の個数です。基数制約Σx(i)<=y がないときは、グラフ解法の方が速く、基数制約の個数が多くなるに従って連続解法の方が速く求まる傾向にあります。グラフ解法では、基数制約の個数が増えると指数関数的に保持する状態メモリが増えてきます。そのためインスタンスによっては破綻する可能性があります。基数制約のない問題というのは考えにくいので、連続解法の方が汎用性があります。一方、基数制約が少なければ、グラフ解法速度は、連続解法を圧倒する場合もあるので、インスタンスにより解法を変えることが理想的です。

連続解法の問題は、分岐限定法の速度です。分岐限定法の前にヒューリスティクスでOpt解に近い解を得ることや、削除平面を使いますが、この分野は、商用MIPソルバの独壇場であり、商用MIPソルバには敵いません。また、絶対的な速度の他に、解が出るまでの時間が一定ではない、という問題もあります。グラフ解ならば、解が出て来るまでの時間はほぼ一定ですが、連続解法では、時間が読めないという問題もあります。

参考リンク

https://speakerdeck.com/umepon/mathematical-optimization-in-60-minutes

https://speakerdeck.com/umepon/branch-and-bound-algorithm-and-cutting-plane-algorithm-for-integer-programs

https://speakerdeck.com/umepon/approximation-algorithms-for-combinatorial-optimization-problems

基数制約とソフト許容エラー数との関係

 基数制約とは、数を数える制約のことで、一般に不等式になります。（LP制約としては、基数制約しかないとも言えます。ORから見ると、AND・OR制約は、基数制約の特殊形です。）

Σxi <=Max

Σxi <=Min

単純な例で、30日中休みを8回だけ取る制約を考えます。この場合の探索空間（ありえる状態空間）は、どうなるでしょうか？

計算方法は、30C8-30C7です。30個から、8個取る組み合わせ、つまり

Σxi <=8から

Σxi <=7を引き算すれば、Σxi>=8 && Σxi<=8となります。

これをExcelで計算したのが上のテーブルです。組み合わせ数が、381万程度となります。

ソフト許容を1とした場合は、(8,8)→(9,7)に拡大されます。以下同様です。

ソフト許容を３とした場合は、探索空間が14倍に増えることを意味します。ソフトエラーまで含めれば、それだけ満たす可能性が増えることを意味しますが、同時に探索負荷が重くなる（時間がかかる）ことを意味します。

ちなみに、日数を31にしただけでも結構な違いがあります。これが月ごとの難易度の違いの原因です。

また、それ以上に休み数の違いがドラスティックな違いを生むことが分かります。

基数制約単体に限れば、上のように組み合わせ数は計算できますが、現実の制約は、制約郡であり複雑です。その総数を計算するのは容易ではありませんが、離散解法（グラフ解法）により個々のRoster（個々人）毎に正確に求めることは可能です。しかし、Rosters全体でみたときに、現実時間内に総数を求めることは、小さなインスタンスを除けば大変に難しいです。（出来ないと言った方がよいかもしれません）。

ソフト許容を無限に許せば、探索負荷が重くなるのは、想像できると思います。一方で、全てをハード制約にすれば、簡単に解のない事態になってしまいます。適度なソフト制約化が、Reasonableな時間で解を得る鍵となります。