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

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

この記事の中で2通りの方法を載せていますが、どちらの方が良いか調べてみたのでその報告です。

上の問題を解きます。
それぞれ制約の入れ方は

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

それぞれ計算時間は

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

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