Experimental Analysis 9

あたらしい数理最適化 -GurobiとPython言語で解く- (近代科学社) 2012年 久保幹雄,ジョア(ジョアン)・ペドロ・ペドロソ,村松正和,アブドル・レイス 著では,実験の結果は示していない.今回は,実験的解析の9回目であり,時間枠付き巡回セールスマン問題に対する実験的解析である.

実験に用いたのは問題例は2種類ある.1つは,以下の論文で用いられた135個の問題例である.

Dumas et al. 1995. An Optimal Algorithm for the Traveling Salesman Problem with Time Windows. Operations Research, 43, 367 – 371

もう1つは,以下の論文で用いられた140個の問題例である.

Gendreau et al. 1998. A Generalized Insertion Heuristic for the Traveling Salesman Problem with Time Windows. Operations Research, 43, 330 – 335

問題例は時間枠の広さによって数種類に分けられる.Gendreauらの問題例の方が時間枠が広く,より難しい問題例となっている.以下は,時間枠の広さが20のDumasらの問題例に対する Intel(R) Xeon(R) CPU E5-2687W 0 @ 3.10GHz RAM: 64 GB でのCPU時間である.

比較したのは2種類の定式化である.mtz-twは通常のポテンシャル(Miller-Tucker-Zemlinタイプの)定式化であり,mtz_strongはその強化版である.また,mtz_2idxは2添え字の変数を用いたポテンシャル定式化である.

意外にも,通常のポテンシャル定式化が最も良く,強化版も同じ程度の速度であり,下界が強いはずの2添え字定式化は計算時間の増大が早く,最も悪い結果になっている.時間枠が広い場合には,強化版のポテンシャル定式化が,通常のポテンシャル定式化より多少良い性能を示す.以下に,時間枠の広さが80のGendreauらの問題例の結果を示す.

より詳細な実験結果については,サポートページを参照されたい.

Experimental Analysis 8

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

実験に用いたのはTSPLIBと呼ばれるベンチマーク問題集であり,その中の配送計画問題例に対して実験を行った.以下に示すのは Intel(R) Xeon(R) CPU E5-2687W 0 @ 3.10GHz RAM: 64 GB でのCPU時間である.

vrpは,整数解が得られた後で部分巡回路除去制約ならびに容量制約を表す切除平面を付加する簡易法であり,lazyは分枝ノード内で整数解が得られたときに切除平面を追加する分枝カット法である.
これから分かるように,配送計画問題に対しては,分枝カット法の方が優れていることが分かる.

Experimental Analysis 7

あたらしい数理最適化 -GurobiとPython言語で解く- (近代科学社) 2012年 久保幹雄,ジョア(ジョアン)・ペドロ・ペドロソ,村松正和,アブドル・レイス 著では,実験の結果は示していない.今回は,実験的解析の7回目であり,対称巡回セールスマン問題に対する実験的解析である.

実験に用いたのはTSPLIBと呼ばれるベンチマーク問題集であり,その中の対称問題例に対して実験を行った.以下に示すのは Intel(R) Xeon(R) CPU E5-2687W 0 @ 3.10GHz RAM: 64 GB でのCPU時間である.

図中で,tspは,整数解が得られた後に部分巡回路制約を追加する簡易法,lazyIは,分枝ノードで整数解が得られたときに分枝子問題に対して部分巡回路制約を追加する分枝カット法,lazyIIは,分枝したときに部分巡回路除去制約を追加する分枝カット法である.

意外にも簡易法が最も良く,整数解が得られたときに分枝子問題に対して部分巡回路制約を追加する分枝カット法(lazyI)が次いでいる.

以下に示すのは,問題の大きさが instance size 以下の問題例で最適解を得ることができなかったインスタンス数である.

これから,lazyIが最も安定したアプローチであり,次いで簡易法であることが分かる.lazyII(分枝ごとに切除平面を加える方法)はあまり推奨できない.

Experimental analysis 6

あたらしい数理最適化 -GurobiとPython言語で解く- (近代科学社) 2012年 久保幹雄,ジョア(ジョアン)・ペドロ・ペドロソ,村松正和,アブドル・レイス 著では,実験の結果は示していない.今回は,実験的解析の6回目であり,Gurobi/Pythonのロットサイズ決定問題に対する実験的解析である.

実験に用いたのはTrigeiro’s random instancesと呼ばれるベンチマーク問題集である.このベンチマーク問題集には,制約のきつさを変えた3種類の問題例が含まれており,以下に示すのは,きつい制約の問題例に対するCPU時間である.

図中でstdは標準定式化を示し,cutは(L,S)不等式と呼ばれる切除平面を追加する分枝カット法の実装であり,flは施設配置定式化と呼ばれる強化された定式化である.

最も良い結果を示しているのは施設配置定式化である(当然!)が,驚くことに標準定式化の法が分枝カット法より良い.切除平面を加えることによる下界の強化より,加える手間のオーバーヘッドの方が大きいためであるが,理論的には分枝カット法の方が良いので,実験をしてみなければ分からない事実である.

以下に同じサイズの問題例において制限時間(3600秒)以内に求解失敗した回数を示すが,これを見ても施設配置定式化,標準定式化,分枝カット法の順序は変わらないことが分かる.

Experimental analysis 5

あたらしい数理最適化 -GurobiとPython言語で解く- (近代科学社) 2012年 久保幹雄,ジョア(ジョアン)・ペドロ・ペドロソ,村松正和,アブドル・レイス 著では,実験の結果は示していない.今回は,実験的解析の5回目であり,Gurobi/Pythonの非対称巡回セールスマン問題に対する実験的解析である.

実験に用いたのはTSPLIBと呼ばれるベンチマーク問題集であり,その中の非対称問題例に対して実験を行った.以下に示すのは Intel(R) Xeon(R) CPU E5-2687W 0 @ 3.10GHz RAM: 64 GB でのCPU時間である.

mtzは,Miller-Tucker-Zemlinによるポテンシャル定式化の結果であり,mtz_strongはそれを持ち上げ操作によって強化したものである.
scfは単品種定式化(single commodity formulation),mcfは多品種定式化(multi-commodity formulation)である.

最も高速なのは,強化されたポテンシャル定式化であり,最大で1000点の問題例まで解くことに成功している.一般にランダムに生成された非対称巡回セールスマン問題のインスタンスは,比較的容易であり,より大規模な問題例まで解けると思われる.最も悪いのは多品種定式化であり,下界は良いが退化した大規模な線形最適化問題を解く必要があるので,使うべきではない.

一方,求解に失敗した回数を示したのが次の図である.

これから最も安定しているのは単品種定式化で,次いで強化されたポテンシャル定式化であることが分かる.

Experimental Analysis 4

あたらしい数理最適化 -GurobiとPython言語で解く- (近代科学社) 2012年 久保幹雄,ジョア(ジョアン)・ペドロ・ペドロソ,村松正和,アブドル・レイス 著では,実験の結果は示していない.今回は,実験的解析の4回目であり,Gurobi/Pythonのグラフ彩色問題に対する実験的解析である.

比較したインスタンスはランダムグラフでありに,使用した計算機は Intel(R) Xeon(R) CPU E5-2687W 0 @ 3.10GHz RAM: 64 GB である.
枝の発生確率を0.5としたランダムグラフの結果を以下に示す(他のグラフに対する結果はこちらを参照されたい).

枝の発生確率が0.5のランダムグラフは最も難しい問題例のクラスである.gcpは通常の(それでも多少強化された)定式化の結果である.これは30点くらいでダウンする.

gcp_lowは対称性を除去するために番号の小さい色を優先するための制約を付加した定式化である.これで多少改善する.さらにSOS(Special Ordered Set)を加えるとちょっとだけ改善するが微々たるものである.

bs-gcpは枝数を固定した問題をサブルーチンとして使い,最適な彩色数は二分探索で求めるアプローチの結果である.これがGurobiを用いるという前提の下での最も望ましい解法であるが,それでも60点くらいでダウンする.それ以上の大きさの問題例に対しては,メタ解法が望ましい.詳しくは,「メタヒューリスティクスの数理」久保-ペドロソ著を参照されたい.

Experimental Analysis 3

あたらしい数理最適化 -GurobiとPython言語で解く-」 (近代科学社) 2012年 久保幹雄,ジョア(ジョアン)・ペドロ・ペドロソ,村松正和,アブドル・レイス 著では,実験の結果は示していない.今回は,安定集合問題に対する実験的解析の結果を示す.以下に示すのは,枝の発生確率が0.05のランダムグラフに対する結果である.

SPP 0.05

これから分かるように,点の数が200近辺で組合せ爆発が起こっていることが分かる.他のランダムグラフにの結果を見ると,枝の密度(発生確率)が0.1付近で問題例が難しくなり,小さくなると(疎になると)簡単になり,大きくなっても簡単になることが分かる.

詳しくは著書とそのサポートページhttp://www.logopt.com/book/gurobi.htmを参照されたい.

Experimental Analysis 2

あたらしい数理最適化 -GurobiとPython言語で解く- (近代科学社) 2012年 久保幹雄,ジョア(ジョアン)・ペドロ・ペドロソ,村松正和,アブドル・レイス 著では,実験の結果は示していない.今回は,実験的解析の2回目であり,Gurobi/Pythonのグラフ分割問題に対する実験的解析である.

比較したインスタンスはランダムグラフでありに,使用した計算機は Intel(R) Xeon(R) CPU E5-2687W 0 @ 3.10GHz RAM: 64 GB である.
枝の発生確率を0.1としたランダムグラフの結果を以下に示す(他のグラフに対する結果はこちらを参照されたい).

図中のgppは二次の目的関数を線形化した(本の中に記載してある)定式化である.

gpp_qoは,二次の目的関数をそのまま記述した定式化の結果である.これは,x*(1-y)+y*(1-x) の目的関数を持つ最適化である.Google で x*(1-y)+y*(1-x) を検索すると3次元グラフが表示されるので確認して欲しいが,これは非凸関数である.Gurobiではこれを凸関数に変換して解いていると思われる.x^2+y^2-2*x*yをGoogleで検索すると出てくる図を見て分かるように,変数を自乗すると凸になる(0-1変数は自乗しても値は同じである).その結果がこれである.

gpp_socoは二次錘最適化として定式化したものである.これは共著者の村松教授が提案したもので,サポートページにあるプログラムにあるように,結構凝った定式化である.

結果から分かるように,現状のGurobiの性能では,普通に線形化したものが最も良い.そういった技法が分からない場合でも,非凸二次の目的関数として定式化してもちゃんと解いてくれる.凝った二次錘最適化は多少良いが,線形最適化にはかなわない(これは他のランダムグラフでも同様である).

これをみると,最適化の理論が分かっていない人でも,ある程度まではGurobiで安直に最適化ができることが分かる.最新の理論(多面体論)を勉強して側面定義不等式(facet defining inequalities)を加えると,余計悪化することを付記しておく.

Experimental Analysis 1

あたらしい数理最適化 -GurobiとPython言語で解く- (近代科学社) 2012年 久保幹雄,ジョア(ジョアン)・ペドロ・ペドロソ,村松正和,アブドル・レイス 著では,実験の結果は示していない.今回を含めて何回かに分けて,実験的解析の結果を示す.

最初に示すのは,Gurobi/Pythonの施設配置問題に対する実験的解析である.
比較したのはk-median問題とk-center問題で,インスタンスは平面上にランダムに配置したEuclid問題例であり,使用した計算機は Intel(R) Xeon(R) CPU E5-2687W 0 @ 3.10GHz RAM: 64 GB である.

k-mendian問題に対してはGurobiは強い定式化を用いれば,比較的大きな問題例まで解けるが,k-center問題(min-max型の最適化問題)に対しては100点あたりで組合せ爆発が起きることが分かる.k-center問題に対しては,k-cover問題を用いてmin-sum型の問題に変形し,閾値を二分探索で求めるアプローチを用いることによって250点を超える問題例まで組合せ爆発が起きないことが示される.

詳しくは著書とそのサポートページhttp://www.logopt.com/book/gurobi.htmを参照されたい.