投稿
昨日までだいぶかかってインストールした SCIP に早速データを投入して数値実験。
結果としては、CPLEX のほうが性能が良かった。
このあたりは入力データ依存なので、たまたま SCIP に合わないデータなのかもしれない。
分かった点としては、
１．primal bound (実行可能点）が５時間ぐらいたっても１つも得られない。したがって duality gap も出てきていない。
CPLEX の場合は、数分で実行可能点をとりあえずは発見している。ついでに、dual bound も CPLEX の値のほうがいい。
２．メモリ使用量が劇的に増える。
分枝の方法があってないのかもしれないけど、とりあえず５時間ぐらいで300万ノードぐらいが生成されていて、100GB のメモリを使用。
このままだと「コンピュータに負担はかかるけど、有益な情報が得られない」ということになりそうなので、計算をストップすることにしてみた。
やはり、入力データにどれだけ性能が出せるかはやってみないと分からないものだ。
2017年4月25日火曜日
2017年4月24日月曜日
SCIP を Linux 上の Matlab から呼び出す、ってお話
SCIP を Linux 上 の Matlab から呼び出すのは、あまり推奨されていないのかもしれないが、コンパイルを頑張って、とりあえずはサンプルプログラムまでは実行できるようになった。（ちなみに、Matlab から呼び出すのでなく単純にコマンドラインから使うだけなら、それほど険しい道のりではない。）
ここにはインストールの記録を残しておく。なお、Ubuntu 系の Linux を想定しているので、ディレクトリ名などは適宜変更が必要かもしれないし、apt-get で必要なファイルなどをインストールする必要もあるかもしれない。
また、インストールするディレクトリは、とりあえず $HOME/lib としている。
1. SoPlex をコンパイル
cd $HOME/lib
wget http://soplex.zib.de/download.php?fname=soplex-3.0.0.tgz
tar xzf soplex-3.0.0.tgz
cd soplex-3.0.0
make SHARED=true
(SHARED=true は Matlab の mex にリンクするときに必須なので忘れないように。)
2. ZIMPL をコンパイル
cd $HOME/lib
wget http://zimpl.zib.de/download/zimpl-3.3.4.tgz
tar xzf zimpl-3.3.4.tgz
cd zimpl-3.4.4
make SHARED=true
(このあたりの wget は、ライセンスの関係でうまくいかないかもしれないので、ホームページからダウンロードしたほうがいいかもしれない。）
3. IPOPT をコンパイル
cd $HOME/lib
wget https://www.coin-or.org/download/source/Ipopt/Ipopt-3.12.7.tgz
tar xzf Ipopt-3.12.7.tgz
cd Ipopt-3.12.7
./configure
make
(make install は特に必要なし。）
4. SCIP をコンパイル
cd $HOME/lib
wget http://scip.zib.de/download.php?fname=scip-4.0.0.tgz
tar xzf scip-4.0.0.tgz
cd scip-4.0.0
make SHARED=true
（このあたりのコンパイルで、ZIMPLE や SOPLEX, IPOPT がどこにあるか指定する必要あり。画面上のメッセージは分かりにくいけど、２０回ぐらいトライ＆エラーをすれば、なんとかなった。）
5. OPTI をコンパイル
cd $HOME/lib
wget https://github.com/jonathancurrie/OPTI/archive/master.zip
unzip master.zip
cd OPTI-master/Solvers/Source/scip
ここで、以下のようなスクリプトでコンパイル。
＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊
#!/bin/sh -x
SCIP_DIR=$HOME/lib/scip-4.0.0
SOPLEX_DIR=$HOME/lib/soplex-3.0.0
OPTI_DIR=$HOME/lib/OPTI-master
IPOPT_DIR=$HOME/lib/Ipopt-3.12.7
mex -largeArrayDims -output scip.mexa64 -I$SCIP_DIR/src -I$SOPLEX_DIR/src -I$OPTI_DIR/Solvers/Source/scip/Include \
-I$IPOPT_DIR/Ipopt/src/Common -I$OPTI_DIR/Solvers/Source/opti\
-L$SCIP_DIR/lib/shared \
scipmex.cpp scipeventmex.cpp scipnlmex.cpp -lscip -lnlpi.cppad -lut
6. Matlab でパスを追加
addpath(genpath(getenv('HOME'),'/lib/OPTI-master'));
7. Matlab を以下のスクリプトで起動
lib/shared:$LD_LIBRARY_PATH
LD_PRELOAD=/usr/lib/gcc/x86_64-linux-gnu/6.3.0/libgcc_s.so:/usr/lib/gcc/x86_64-linux-gnu/6.3.0/libstdc++.so:/usr/lib/gcc/x86_64-linux-gnu/6.3.0/libgfortran.so:$HOME/lib/scip-4.0.0/lib/shared/libscip.so:/usr/lib/x86_64-linux-gnu/libreadline.so:$HOME/lib/scip-4.0.0/lib/shared/libnlpi.cppad.so:$HOME/lib/scip-4.0.0/lib/shared/libscipsolver.so /usr/local/bin/matlab -nodisplay $*
ここにはインストールの記録を残しておく。なお、Ubuntu 系の Linux を想定しているので、ディレクトリ名などは適宜変更が必要かもしれないし、apt-get で必要なファイルなどをインストールする必要もあるかもしれない。
また、インストールするディレクトリは、とりあえず $HOME/lib としている。
1. SoPlex をコンパイル
cd $HOME/lib
wget http://soplex.zib.de/download.php?fname=soplex-3.0.0.tgz
tar xzf soplex-3.0.0.tgz
cd soplex-3.0.0
make SHARED=true
(SHARED=true は Matlab の mex にリンクするときに必須なので忘れないように。)
2. ZIMPL をコンパイル
cd $HOME/lib
wget http://zimpl.zib.de/download/zimpl-3.3.4.tgz
tar xzf zimpl-3.3.4.tgz
cd zimpl-3.4.4
make SHARED=true
(このあたりの wget は、ライセンスの関係でうまくいかないかもしれないので、ホームページからダウンロードしたほうがいいかもしれない。）
3. IPOPT をコンパイル
cd $HOME/lib
wget https://www.coin-or.org/download/source/Ipopt/Ipopt-3.12.7.tgz
tar xzf Ipopt-3.12.7.tgz
cd Ipopt-3.12.7
./configure
make
(make install は特に必要なし。）
4. SCIP をコンパイル
cd $HOME/lib
wget http://scip.zib.de/download.php?fname=scip-4.0.0.tgz
tar xzf scip-4.0.0.tgz
cd scip-4.0.0
make SHARED=true
（このあたりのコンパイルで、ZIMPLE や SOPLEX, IPOPT がどこにあるか指定する必要あり。画面上のメッセージは分かりにくいけど、２０回ぐらいトライ＆エラーをすれば、なんとかなった。）
5. OPTI をコンパイル
cd $HOME/lib
wget https://github.com/jonathancurrie/OPTI/archive/master.zip
unzip master.zip
cd OPTI-master/Solvers/Source/scip
ここで、以下のようなスクリプトでコンパイル。
＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊
#!/bin/sh -x
SCIP_DIR=$HOME/lib/scip-4.0.0
SOPLEX_DIR=$HOME/lib/soplex-3.0.0
OPTI_DIR=$HOME/lib/OPTI-master
IPOPT_DIR=$HOME/lib/Ipopt-3.12.7
mex -largeArrayDims -output scip.mexa64 -I$SCIP_DIR/src -I$SOPLEX_DIR/src -I$OPTI_DIR/Solvers/Source/scip/Include \
-I$IPOPT_DIR/Ipopt/src/Common -I$OPTI_DIR/Solvers/Source/opti\
-L$SCIP_DIR/lib/shared \
scipmex.cpp scipeventmex.cpp scipnlmex.cpp -lscip -lnlpi.cppad -lut
＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊
基本的には、リンクで見つからない関数があれば、そのつど nm コマンドで *.so を全解列挙して、grep で検索すればよい。
addpath(genpath(getenv('HOME'),'/lib/OPTI-master'));
7. Matlab を以下のスクリプトで起動
＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊
export LD_LIBRARY_PATH=/usr/lib/gcc/x86_64-linux-gnu/6.3.0:$HOME/lib/
scip-4.0.0/lib/shared:/usr/lib/x86_64-linux-gnu:$HOME/lib/scip-4.0.0/lib/shared:$LD_LIBRARY_PATH
LD_PRELOAD=/usr/lib/gcc/x86_64-linux-gnu/6.3.0/libgcc_s.so:/usr/lib/gcc/x86_64-linux-gnu/6.3.0/libstdc++.so:/usr/lib/gcc/x86_64-linux-gnu/6.3.0/libgfortran.so:$HOME/lib/scip-4.0.0/lib/shared/libscip.so:/usr/lib/x86_64-linux-gnu/libreadline.so:$HOME/lib/scip-4.0.0/lib/shared/libnlpi.cppad.so:$HOME/lib/scip-4.0.0/lib/shared/libscipsolver.so /usr/local/bin/matlab -nodisplay $*
＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊
実行時にうまく行かない場合も、nm と grep で探し当てて、LD_LIBRARY_PATH と LD_PRELOAD に載せれば何とかなる。
（なぜか LD_PRELOAD だけでは、うまく行かない時があるので、LD_LIBRARY_PATH にもフォルダをあわせて書く方がよいようだ。）
7. サンプルソースの実行
あとは、$HOME/lib/OPTI-master/Examples/Global_NonlinearProgramming.m にある SCIP 用のサンプルを実行すればよい。
具体的には、Example 4 - White Box Quartic となっているところである。
途中途中であまりスリムになっていないところもあるが、これでサンプルプログラムを実行できる。
Matlab から $ help scip とすれば使い方も分かるようになっている。
たぶん、Mac でも同じような手順でコンパイルできるかと思うが、Mac は OS 自体が複雑なので、もっと大変なのかもしれない。
2017年4月20日木曜日
SCIP がインストールできずに、てこずる話
どうやら SCIP というのが性能がいいらしい、という話を今更ながらに聞いてきたので、今日インストールしようとし始めた。
扱いたいデータは Linux サーバーのMatlab 上にあるので、SCIP を Linux の Matlab から呼び出すようにしないといけない。
どうやら、YALMIP を使って OPTI 経由で SCIP を呼び出すのが流儀のようなので、インストールしてみる。
今日のところインストールしたのは、
SCIP
Soplex
ZIMPL
YALMIP
OPTI
Ipopt
まで。
で、OPTI は Windows 版はあるけど Linux 版がないので、scip のインターフェイスを直接 mex でコンパイルしようと模索。
すると、なんと libscip.a が -fPIC がついていなかった。
明日のうちに SCIP のコンパイルからやり直さないと。。。
できれば、SCIP が apt-get でインストールできると便利ではあるけど、apt-get でインストールできるようになるのは、現状では難しいと思う。
扱いたいデータは Linux サーバーのMatlab 上にあるので、SCIP を Linux の Matlab から呼び出すようにしないといけない。
どうやら、YALMIP を使って OPTI 経由で SCIP を呼び出すのが流儀のようなので、インストールしてみる。
今日のところインストールしたのは、
SCIP
Soplex
ZIMPL
YALMIP
OPTI
Ipopt
まで。
で、OPTI は Windows 版はあるけど Linux 版がないので、scip のインターフェイスを直接 mex でコンパイルしようと模索。
すると、なんと libscip.a が -fPIC がついていなかった。
明日のうちに SCIP のコンパイルからやり直さないと。。。
できれば、SCIP が apt-get でインストールできると便利ではあるけど、apt-get でインストールできるようになるのは、現状では難しいと思う。
2017年4月12日水曜日
2017年4月7日金曜日
IT Text 数理最適化
世の中には、非常に不思議だと思うこともあって、「IT Text 数理最適化」の Amazon のページにレビューが１件もなかったりする。
数理最適化の基礎を勉強するうえでとてもいい本だと思うし、自分もちょくちょく参考にしていたりするし、他の人から「数理最適化って、どの本で勉強したらいいですか？」って聞かれたら「この本がおススメ」って伝えていたりもするし。
なんでレビューが１件もないのか謎だ。不思議だ。
数理最適化の基礎を勉強するうえでとてもいい本だと思うし、自分もちょくちょく参考にしていたりするし、他の人から「数理最適化って、どの本で勉強したらいいですか？」って聞かれたら「この本がおススメ」って伝えていたりもするし。
なんでレビューが１件もないのか謎だ。不思議だ。
2017年3月31日金曜日
TeX で使われていない数式番号を見つけ出す
TeX で \label をつけて数式番号を振ってあるけど、その数式番号をどこでも使ってなかった、ということが、よくある。
とりあえずは、\label がついているものすべてに \ref が使用されているかどうかを見ればわかるので、Linux なら次のようなスクリプトで \label と \ref の diff を取ることができる。
(ただし、paper.tex は適宜変更のこと）
#!/bin/sh
grep -o -e "ref{[^}]*}" paper.tex | sort | uniq | sed "s+ref{++" | sed "s+}++" > __ref.txt
grep -o -e "label{[^}]*}" paper.tex | sort | uniq | sed "s+label{++" | sed "s+}++" > __label.txt
diff __ref.txt __label.txt
rm __ref.txt __label.txt
とりあえずは、\label がついているものすべてに \ref が使用されているかどうかを見ればわかるので、Linux なら次のようなスクリプトで \label と \ref の diff を取ることができる。
(ただし、paper.tex は適宜変更のこと）
#!/bin/sh
grep -o -e "ref{[^}]*}" paper.tex | sort | uniq | sed "s+ref{++" | sed "s+}++" > __ref.txt
grep -o -e "label{[^}]*}" paper.tex | sort | uniq | sed "s+label{++" | sed "s+}++" > __label.txt
diff __ref.txt __label.txt
rm __ref.txt __label.txt
2017年3月3日金曜日
Optimality condition and complexity analysis for linearly-constrained optimization without differentiability on the boundary
Optimization Online で
Optimality condition and complexity analysis for linearly-constrained optimization without differentiability on the boundary
Gabriel Haeser, Hongcheng Liu, Yinyu Ye
http://www.optimization-online.org/DB_HTML/2017/02/5861.html
というのが掲載されていたので、チェックをしてみた。
基本的には、KKT 条件を epsilon 誤差だけ許容するような条件に拡張した場合にどうなるか、という点が議論されていた。
実際の数値計算では、厳密に（誤差０で）KKT条件を満たせることは、ほぼないので、epsilon-KKT 条件のようなものが計算されているはずで、その理論展開が普通の KKT 条件と似たようなところで展開されている、というのが面白い。
つまり、「KKT 条件が成り立たないはずの数理最適化問題が、KKT条件を想定して作られたソフトウェアでも、なぜか答えが求まっちゃう」ということが実際には良くあるわけだが（例えば、Slater 条件を満たさない SDP の解を SDPA が求めちゃったり）、こういう研究を見てみると、そういう現象の背景が推察できたりする。
Optimality condition and complexity analysis for linearly-constrained optimization without differentiability on the boundary
Gabriel Haeser, Hongcheng Liu, Yinyu Ye
http://www.optimization-online.org/DB_HTML/2017/02/5861.html
基本的には、KKT 条件を epsilon 誤差だけ許容するような条件に拡張した場合にどうなるか、という点が議論されていた。
実際の数値計算では、厳密に（誤差０で）KKT条件を満たせることは、ほぼないので、epsilon-KKT 条件のようなものが計算されているはずで、その理論展開が普通の KKT 条件と似たようなところで展開されている、というのが面白い。
つまり、「KKT 条件が成り立たないはずの数理最適化問題が、KKT条件を想定して作られたソフトウェアでも、なぜか答えが求まっちゃう」ということが実際には良くあるわけだが（例えば、Slater 条件を満たさない SDP の解を SDPA が求めちゃったり）、こういう研究を見てみると、そういう現象の背景が推察できたりする。
登録:
投稿 (Atom)