gurobi7.5で多目的最適化がやりやすくなった?
お久しぶりです
ごたごたしている間にgurobi7.5がリリースされていました.
(って結構前か・・・)
このgurobi7.5になってから,多目的最適化をするのに便利なメソッドが追加されたようです.知らんけど.
私もざっと見ただけなんでよくわからんのですが
これまで多目的最適化をするためには変数の係数をいちいち与えなければならなかったのか何なのか,分からんのですけど(何もわかってない),このsetObjectiveNメソッドによって,いつも使ってるsetObjectiveみたいなノリで複数の目的関数を設定できるようなんですね.
というわけで遊んでみました.
次のような整数混合線形計画問題を考えます.
min α*a+β*10*b
s.t. a>=1
a+b >= 2
(aは連続,bは0-1変数)
(α,βは重み)
この問題でパラメータαに大きな値を置く(aを優先する)と,最適解は
{a,b}={1,1}
になり,逆にβに大きな値を置く(bを優先する)と,最適解は
{a,b}={2,0}
になります.他の解はパレート最適でないので出てきません.
具体的には,αがβの10倍を超える値になれば,上の解に,下回る値なら下の解になります.そのはずです.
このαとかβとか重みをおいて自分で普通に最適化してもいいんですが,今回はそれをgurobiにやってもらおうというやつになります.
setObjectiveNメソッドの第一引数は,目的関数の式になります.
第二引数はindexといいます.多目的最適化は名前の通り複数の目的関数を扱うわけですが,その複数ある目的関数に固有の番号を付けて管理するためのものと思います.知らんけど.
第三引数がわかりません.上に貼り付けたgurobiのサイトを見ると,priorityのようですが...
priorityは優先,weightは重みです.
第三引数がpriorityなら,数字の大きい方の最小化を最優先し,それを邪魔しない範囲で数字の小さい方の最小化をするはず.
weightなら,前述のαとβのように扱われるはず.
一方は何の値か指定せずに与えました.もう一方はweightをこの値にするよと伝えてみました.
上段の何の値か指定しない場合はaを優先した解になりました.このことから,第三引数は通常priorityであろうことが伺えます.
下段の場合はbを優先した解になりました.α=2,β=1として扱ってもらえたものと思われます.この場合αがβに対して10倍以下なので,解はこうなりました.
本当にweightが重みとして機能しているのか?という確認もしてみました.
重みを10と1にすると,解は2と0,つまりbの最小化を優先した解になりましたが,
重みを11と1にすると,解は1と1,つまりaの最小化を優先した解になりました.
αがβの10倍より大きいかどうかで解が切り替わっています.
というわけで,重みとして扱ってもらえていると思えます.
まとめると
- gurobi 7.5 になって,多目的最適化がやりやすくなったらしい
- setObjectiveNの第三引数はpriority
- その第三引数をweightとして与えることも可能
そんな感じです.
自分の気になるところだけざざっと調べた内容をそのままレポートしましたんで,オチはないんです.
tuneして求めたparamsをそのまま即座に使って最適化する
tuningツールがgurobiにはあって.
っていきなり話しても急ですね.
gurobiでは計算するにあたって,いろいろいじれるパラメータがあります.どんな解き方しますか~?みたいなもんです.具体的には,
model.params.~~ = ??
みたいな形で与えます.
で,そのパラメータなるものが膨大にあってわけわからんので,tuning toolというものがあり,
model.tune()
ってやってやると,そのmodelを解くのにいい感じのパラメータの組み合わせをgurobiが求めてくれる,というものでございます.
tuningの結果を出力するのに,model.getTuneResult()というメソッドを使います.そしてmodel.write("~~.prm")とやってやると,パラメータの組み合わせが書き込まれたprmファイルを出力してくれるわけです.
で,私は誤解してたんですが,このgetTuneResultメソッド,modelにパラメータを反映させる,というものなんですね.
これは,パラメータの組み合わせは複数あったりするんですが,そのパラメータの組み合わせのリストのうち何番目をmodelに反映させますか?というものです.
[パラメータの組み合わせ0,パラメータの組み合わせ1,・・・]
みたいなやつの何番目を選びますか?ということです.ちなみに1つめのパラメータの組み合わせが,一番よさそうだったパラメータの組み合わせになります.
というわけで
model.getTuneResult(0)としてやれば,一番よさげだったパラメータの組み合わせをmodelに反映させてくれるので,あとはそのままmodel.optimize()してやれば,求まったばかりほやほやのパラメータの組み合わせで計算を開始してくれるわけです.writeしてるのは,あれですね,記念みたいなもんですね.
ではまた.
コードの変更箇所をハイライト|atom split diff
Pythonの話でもGurobiの話でもなくて恐縮ですが,最近知って重宝しているatomのパッケージがあるので共有したいと思います.
split-diffというやつなんですが,(まあ有名なんでしょうが)コードを比べて違うところを教えてくれます.
ちょっとずつ違う設定の計算したりしていると,何を変えたんだか忘れてしまいがちなので,これはとても助かります.間違いが防げます.
こんな感じで,何かの初期条件っぽいぐちゃっとしたものを用意しました.実は左と右とは二か所だけ違うんですが,それをぱっと見で探すのはつらいですし間違いの元です.
それがsplit-diffにかけると,こんな具合に教えてくれます.違う行はもちろん,その中でも何が違うのかを更にハイライトで教えてくれています.
あと2年早く知りたかったよ.
最適化計算のヒントになる情報っぽい各ファイルを比較
一度計算した最適解を次の計算でも使いたいな〜というのは誰しも思うものかと思いますが.gurobiのマニュアルを見ていると,mstやらsolやらhntやら,いくつか種類があってよくわかりません.
ですので,いろいろ試してみました.結論からいうと,
- write("~.sol) : 計算で得られた解を出力
- write("~.mst) : 計算で得られた解のうち整数変数の値を出力
- write("~.hnt) : 何も出力されない
という感じのようです.以下,ためした結果です.
solはsolutionの略でしょうから,変数のタイプに関わらず計算で得られた解が出てくるのは自然でしょう.
mstはMIP Startの略でしょうか,整数変数がいくつ?という情報です.ですので連続変数は無視されます.
そしてhntはヒントという意味で,変数ごとに値と優先順位を指定し,gurobiはそれを参考にして整数混合問題を解きます.(これは私の解釈ですが)mstやsolの場合は ”最適化の初期解" として解釈されるのに対して,こちらはあくまでヒントです.計算する前に「最適解はたぶんこんな値だと思うよ.その優先順位としてはこんな感じね」という情報を与えて,それを参考にしながらgurobiが計算することになるんだと,いうことのようです.
solをmodel.read( )すると,それが実行不可能(infeasible)だった場合に,無視されて普通に計算がなされますが,hntだと実行不可能だとしても参考くらいにはしてくれるのかな?
しかしhntファイルはgurobiではwriteで出力できないようですんで,手打ちするしかないのか?そんなバカな.いくら変数全部の情報を入力しなくてもいいとはいえ.(hntファイルはモデルに含まれるすべての変数の情報を与えなくてもgurobiはそれを参考にしてくれます.情報のない変数については無視され,普通に計算が始まります.)
なんとかならないかなっと思って強引にやったのがこちら.
我ながらひどいことをすると思います.
gurobiは拡張子を見てそのファイルがなんなのかを判断するようなので,拡張子だけ変えてしまえばsolファイルをhntファイルとしてreadしてくれるわけです.各ファイルの一行目に書いてあることはコメントであって無視されるのできっと大丈夫.
やってみて意味があったかどうか,今ちょっと時間がないので,後ほどレビューしたいと思います.ではまた.
ーーーーーーーーーーーー
追記
拡張子を変えてhntファイルとして読み込ませることには成功しました.
Found heuristic solution: objective ○○○
と出てきました.heuristic solutionを見つけた,ということは,ヒントをもとに実行可能解を見つけたということで,solファイルのように与えられた解をそのまま初期解として使いますよ,というのとは若干違うんじゃないかなと思います.
(すみません見間違えてました.)
hntファイルとsolファイルの違いについては,gurobiのこちらのサイトに詳しく記載がありました.
VarHintValというのは,変数のattributeで,変数のヒントの値のことですね.こちらによると,ざっくり言えば
solファイルとhntファイルは似てるように思うかもしれないけど,与えた後の振る舞いが違うよ,solファイルは初期解だけど,hntファイルは解き方に影響を与えるよ,だからいいhntだったら意味あるけどよくないhntだったらむしろ与えないほうがいいよ,
みたいな感じらしいです.(英語得意じゃないんで違ってたらごめんなさい)
ではまた.
最適化の途中で戦略を変えるパラメータ
最適化の途中で戦術変えたら早くなるのでは?と思ってCallbackを使ってMIPFocusなんかを変えることを考えたことがありました.
strep-ik-gurobipy.hatenadiary.jp
そんなことしなくたって,戦術を途中で変えてくれるパラメータがGurobiさんにはあるんですね.
ImporveStartGapというもので,Gapがいくつ以下になったら,解の改善に力を入れるように戦術を変える,というもののようです.解の改善ってなんだと言われると,私も,さぁ?,という感じなんですが.
これを例えば0.1なんかにしますと, Gapが10%以下になったら戦術が変わるわけですが,何に変わるんだろうと思ってやってみますと
Heuristics = 0.5
RINS = 10
に変わりました.Heuristicsでかくない...?デフォルトは0.05だったような.Heuristicsがデフォルトより大きいほうが,ささっとGapが縮まるんですか?わかりません.まぁこういうモノがあるということは,設定するとなかなか計算の最後の方でGapが縮まらない問題なんかには有効なんじゃないかと思います.
すみません,別に数理最適化の専門家じゃないもんで...
Python2.7+gurobiの環境構築手順備忘録
Windows上でのgurobi+python2.7の環境構築手順(アカデミックライセンス)の備忘録を。gurobiのサイトに書いてある手順はこちらです。(https://www.gurobi.com/documentation/6.5/quickstart_mac/the_gurobi_python_interfac.html)
ここでは日本語で説明し、かつ陥りやすい罠を回避できるようにしたいと思います。
※私がこの手順でインストールした、というだけですので、この手順で必ずインストールできると保証できるものではありません。参考程度にお願いします。
1.Python2.7.11をインストールします。
64bitのPCなら64bit用を、32bitのPCなら32bit用をインストールしてください。
インストーラーにて、コマンドプロンプト上でpythonを呼び出せるようにするか?という項目があると思いますのでそちらをチェックしておきます。
※最新はPython2.7.12ですが、Python2.7.11でないとgurobiと繋がらないようです。
※Pythonのページのわかりやすいインストールボタンを安易に押すと思ったのと違うものがダウンロードされる場合がありますので、ご自分のPCにあったものを探してください。
2.gurobiのサイトでアカデミックライセンスを取得します。
3.gurobi7.0.2をインストールします。
64bitのPCなら64bit用を、32bitのPCなら32bit用をインストールしてください。
4.gurobiのライセンスを取得します。
gurobiのサイトのDownload Center→Academic Lincence→Request Licenceの順でクリックし、keyを取得します。
5.gurobiのライセンスの認証をします。
gurobiのサイトのLicenceDetailでgrbgetkey ****...なるコマンドが青字で表示されると思いますので、こちらをコピーしてコマンドプロンプト上に貼り付け実行します。
6.C:\gurobi702\win64\bin 内にあるpysetup.batをダブルクリックで実行します。
32bitのPCならC:\gurobi702\win32\binになると思います。
7.コマンドプロンプトでC:\gurobi702\win64のディレクトリに移動(cd C:\gurobi702\win64)し、「python pysetup.py install」と打ち込み実行します。
32bitのPCならC:\gurobi702\win32になると思います。
(180305追記)python setup.py install でした.失礼しました.
8.完了のはずです。
コマンドプロンプトでpythonと打ってpythonを呼び出し、「from gurobipy import *」と打ってエラーがでなければ成功です。
コマンドプロンプトでpythonを呼び出すと、64bitのつもりでインストールしても「on win32」と不穏な字が書いてありますが、[~ 64bit]の文字があれば気にしなくてOKです。
64bitのPCであれば32bitのgurobi+Pythonでも動きますが、サイズの大きいMILP等を解くときには64bitの方が当然のことながらずっと速いのでおすすめです。逆に32bitのPCで64bitのPythonは動かないはずですので、その場合は32bitを入れるしかないと思われます。
macの場合については、書けたら書きます。(書くとは言っていない)
【2017/10/30更新】 macならこの通りにやれば問題ないのかなと思います. http://www.gurobi.com/documentation/6.5/quickstart_mac/installing_the_anaconda_py.html
callbackで途中で戦術を変える
MIPFocus=2にすると厳密解を慎重に計算してくれるけれども,大規模な問題だとちっとも進まない...それなら,はじめはMIPFocus=3 でざっくり解いて,gapが縮まってきたら2にしたらいいじゃない,という思いつき.
そんなことをしてちゃんとした解が出てくるのかは...ちょっとまだ分からない.そもそもMIPFocusの解釈からして自信はない.
倍速い!大丈夫かこれ