カテゴリー別アーカイブ: 実験的解析

Knapsack Problem

複数制約ナップサック問題は比較的MIPソルバーで解きやすい問題である.比較的古い論文でChu-Beasleyが遺伝的アルゴリズムを, Glover-Kochenbergerが禁断探索法のテストをするために作成したベンチマーク問題例は,Gurobiである程度までは解くことができる.

計算時間のグラフを以下に示す.
問題のサイズと計算時間

これを見ると,変数の数が2500を超えるようになると厳密解を出すのに多大な時間を要することが分かる.しかし,どの問題例も短時間で上界と下界のギャップは比較的小さくなっており,途中で計算を打ち切って得られる近似解は,十分に実用に耐えうると考えられる.

最大の問題例であるmk_gk11_100x2500(この問題例は250000個の変数を含む!)と呼ばれる問題の計算ログの一部を以下に示す.

Found heuristic solution: objective 93813.000000
Root relaxation: objective 9.527749e+04, 1007 iterations, 0.37 seconds
Nodes | Current Node | Objective Bounds | Work
Expl Unexpl | Obj Depth IntInf | Incumbent BestBd Gap | It/Node Time

0 0 95277.4913 0 100 93813.0000 95277.4913 1.56% – 0s
H 0 0 95155.000000 95277.4913 0.13% – 1s
H 0 0 95218.000000 95277.4913 0.06% – 5s
0 2 95277.4912 0 100 95218.0000 95277.4912 0.06% – 12s

これによると分枝の前のヒューリスティクスで93813という解を見つけ,分枝開始から12秒後に誤差0.06%の解を得ている.

他のメタヒューリスティクス(詳細については,「メタヒューリスティクスの数理」(共立出版)を参照)との比較はまだ行っていないが,近似解法としてのGurobiに対抗するのは難しいと考えられる.

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らが提案した定式化もあるが,やはり論外であり,実務的には使うべきではない.

Experimental Analysis 11

Weber問題と呼ばれる施設配置問題は,二次錘最適化問題として定式化できる.

平面上に一様ランダムに発生させた点に対するWeber問題に対する実験を以下に示す.

Wer問題に対する計算機実験

点の数は10から10万まで増やしているが,計算時間はほとんど線形に増加していることが見て取れる.Gurobiの二次錘最適化は高速であり,ポートフォリオ問題も同様に,ヒューリスティクスなどに頼るべきではないと考えられる.

Experimental Analysis 10

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

実験に用いたのはランダムに生成した1機械リース時刻付きの納期遅れ最小化問題である.すべてのデータは[1,99]の一様乱数にしたがって生成した.以下に示すのは Intel(R) Xeon(R) CPU E5-2687W 0 @ 3.10GHz RAM: 64 GB でのCPU時間である.

スケジューリング問題に対する計算時間の変化

図中で,lopは線形順序付け定式化,tiは時刻添え字定式化,disjは施設定式化を表す.結果から,最も良いのは線形順序付け定式化,次いで時刻添え字定式化,最も悪いのは大きな数(M)を用いた離接定式化である.

ただし,時刻添え字定式化は,時刻を表す数字が大きくない場合には,より高速になることが予想される.

いずれにせよ,1機械の簡単な問題に対してもGurobiでは比較的長い計算時間がかかることから,スケジューリング問題に対しては,制約プログラミングや専用のメタ解法に基づくソルバー(たとえばSCOPやOptSeq)が実務的に推奨されることが分かる.

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点くらいでダウンする.それ以上の大きさの問題例に対しては,メタ解法が望ましい.詳しくは,「メタヒューリスティクスの数理」久保-ペドロソ著を参照されたい.