NSPの部分問題である制約付最短経路問題をできるだけ速く解くというのは、NSP最適化において重要です。
二つのアプローチがあります。言い換えるとグラフ解法か、分岐限定法かということです。
どちらが速く求まるか？というのは、問題によります。要因として大きいのは、基数制約の個数です。基数制約Σx(i)<=y がないときは、グラフ解法の方が速く、基数制約の個数が多くなるに従って連続解法の方が速く求まる傾向にあります。グラフ解法では、基数制約の個数が増えると指数関数的に保持する状態メモリが増えてきます。そのためインスタンスによっては破綻する可能性があります。基数制約のない問題というのは考えにくいので、連続解法の方が汎用性があります。一方、基数制約が少なければ、グラフ解法速度は、連続解法を圧倒する場合もあるので、インスタンスにより解法を変えることが理想的です。
連続解法の問題は、分岐限定法の速度です。分岐限定法の前にヒューリスティクスでOpt解に近い解を得ることや、削除平面を使いますが、この分野は、商用MIPソルバの独壇場であり、商用MIPソルバには敵いません。また、絶対的な速度の他に、解が出るまでの時間が一定ではない、という問題もあります。グラフ解ならば、解が出て来るまでの時間はほぼ一定ですが、連続解法では、時間が読めないという問題もあります。
参考リンク
https://speakerdeck.com/umepon/mathematical-optimization-in-60-minutes
https://speakerdeck.com/umepon/approximation-algorithms-for-combinatorial-optimization-problems
0 件のコメント:
コメントを投稿