Experimental Analysis 12

あたらしい数理最適化 -GurobiとPython言語で解く- (近代科学社) 2012年 久保幹雄,ジョア(ジョアン)・ペドロ・ペドロソ,村松正和,アブドル・レイス 著では,実験の結果は示していない.今回は,実験的解析の12回目であり,非線形の設置費用を持つ施設配置問題に対する実験的解析である.

非線形関数は規模の経済や安全在庫費用を近似した平方根の関数であるが,これを区分的線形で近似して扱っている.個々での目的は,様々な区分的線形近似の手法の中で,どれが最も高速化を現実的な問題で調べることである.

以下に,区分数を100とした場合の結果を示す.

非線形施設配置問題に対する実験(区分数100)

図中の記号は,以下の通りである.

mselect 多重選択定式化(multiple selection model)
cc_dis 非集約型凸結合定式化(disaggregated convex combination model)
cc_dis_log 対数個の変数を用いた非集約型凸結合定式化(disaggregated convex combination model with a logarithmic number of variables)
cc_agg 集約型凸結合定式化(aggregated convex combination model)
cc_agg_log  対数個の変数を用いた集約型凸結合定式化(aggregated convex combination model with a logarithmic number of variables)
sos タイプ2の特殊順序集合を用いた定式化 (model using sos constraints of type 2)

結果としては,単純なタイプ2の特殊順序集合を用いたものが最も良いので,これを推奨する.以前の研究では,対数個の変数を用いた定式化が良いという結論を出しているものもあるが,Gurobiのようなモダンなソルバーでは,単純にSOSと宣言する方が,良い結果を出すと考えられる.

次いで,対数個の変数を用いた集約型凸結合定式化,対数個の変数を用いた非集約型凸結合定式化(であるが,これらは複雑な制約を付加する必要がある.3変数以上の(分離不能な)非線形関数の近似の際には,これらの定式化も推奨される(SOSは使えないからだ).ほぼ同じ性能で,集約型凸結合定式化も有効である.この定式化は下界が弱いので使うべきではないと,従来の研究では結論づけられていたが,変数の少なさや簡潔さがそれを補うらしい.

良い下界を算出し,理論的に優れていると言われていた非集約型凸結合定式化は,点数200を超えると解けなくなる.多重選択定式化も同じである.他にも線形最適化の生みの親であるDantzigらが提案した定式化もあるが,やはり論外であり,実務的には使うべきではない.