サブロウ丸

主にプログラミングと数学

線形計画問題における、とある条件を持つバイナリ変数の表現方法について - その2

この記事の続きです。 inarizuuuushi.hatenablog.com

この記事の中で2通りの方法を載せていますが、どちらの方が良いか調べてみたのでその報告です。
f:id:inarizuuuushi:20170816111716p:plain:w600
上の問題を解きます。
それぞれ制約の入れ方は

f:id:inarizuuuushi:20170816111814p:plain:w600

以前の記事では、2つ目のパターンでは分数の形で記述していましたが、実際にソルバー(cbc)に問題を入力する際は分母を払った方が劇的に実行時間が早くなりました。(他の高級なソルバーだと特に影響はないかもしれませんが…)


それぞれ計算時間は

n 1 2
1000 0.735s 0.465s
10000 5.95s 3.20s
100000 59.9s 33.3s
500000 5m03s 3m02s


ということで、2つ目の定式化の方が高速に行えることがわかりましたね!
やはり変数と制約が少ない方が早いということでしょうか。
以上、報告でした。