2017年4月25日火曜日

scip には、合わないデータだったみたい

昨日までだいぶかかってインストールした SCIP に早速データを投入して数値実験。
結果としては、CPLEX のほうが性能が良かった。
このあたりは入力データ依存なので、たまたま SCIP に合わないデータなのかもしれない。

分かった点としては、
1.primal bound (実行可能点)が5時間ぐらいたっても1つも得られない。したがって duality gap も出てきていない。
   CPLEX の場合は、数分で実行可能点をとりあえずは発見している。ついでに、dual bound も CPLEX の値のほうがいい。
2.メモリ使用量が劇的に増える。
   分枝の方法があってないのかもしれないけど、とりあえず5時間ぐらいで300万ノードぐらいが生成されていて、100GB のメモリを使用。

このままだと「コンピュータに負担はかかるけど、有益な情報が得られない」ということになりそうなので、計算をストップすることにしてみた。

やはり、入力データにどれだけ性能が出せるかはやってみないと分からないものだ。

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 がどこにあるか指定する必要あり。画面上のメッセージは分かりにくいけど、20回ぐらいトライ&エラーをすれば、なんとかなった。)

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 で検索すればよい。

6. Matlab でパスを追加
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 でインストールできるようになるのは、現状では難しいと思う。

2017年4月12日水曜日

救急車再配置の実例

今朝のニュースで、リアルタイムでの救急車再配置を実際に行っている例が取り上げられていた。
前に調べた時には、日本では実例が見つからなかったので、大変参考になった。
実際にどのように行っているのか、情報がどこかにあるか調べてみようと思う。


2017年4月7日金曜日

IT Text 数理最適化

世の中には、非常に不思議だと思うこともあって、「IT Text 数理最適化」の Amazon のページにレビューが1件もなかったりする。

数理最適化の基礎を勉強するうえでとてもいい本だと思うし、自分もちょくちょく参考にしていたりするし、他の人から「数理最適化って、どの本で勉強したらいいですか?」って聞かれたら「この本がおススメ」って伝えていたりもするし。

なんでレビューが1件もないのか謎だ。不思議だ。



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

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 誤差だけ許容するような条件に拡張した場合にどうなるか、という点が議論されていた。

実際の数値計算では、厳密に(誤差0で)KKT条件を満たせることは、ほぼないので、epsilon-KKT 条件のようなものが計算されているはずで、その理論展開が普通の KKT 条件と似たようなところで展開されている、というのが面白い。
つまり、「KKT 条件が成り立たないはずの数理最適化問題が、KKT条件を想定して作られたソフトウェアでも、なぜか答えが求まっちゃう」ということが実際には良くあるわけだが(例えば、Slater 条件を満たさない SDP の解を SDPA が求めちゃったり)、こういう研究を見てみると、そういう現象の背景が推察できたりする。

2017年2月28日火曜日

Newton Sketch

SIAM Optimization に「Newton Sketch」というタイトルの論文が出ていたので、チェックをしてみたが、なかなかに面白かった。

普通に Newton 法を実行すると Hessian $$\nabla^2 f(x)$$ が重たいわけだけど、ある構造を満たすような正定値対象行列 $$S$$ を用いて $$S \nabla^2 f(x)^{1/2}$$ のように変更する。
ここで、$$SS$$ は確率的に選んでいて、しかも行列積などが高速に行える構造を持っているようなものを作っている。

このようにすると、stochastic gradient よりも速い収束が得られる、という話だった。

たしかに、stochastic gradient は反復回数が非常に多くて十分な収束が得られないので、こういったように改善する、というのは面白いアイデアだと思う。

論文では、self-concordant なども議論していて、SDP なども解けるとのこと。
ただ、数値実験では SDP が出ていないので、たぶん SDP の構造にはあまりあてはまっていない可能性もある。
そういった可能性もあるが、SDP でどうやって性能を引き出せるか、ということに注目すれば、新しいテーマにできるかもしれない。



2017年1月16日月曜日

みかん最適化分割問題

今朝の NHK で、「みかんの皮を切っていって、酉の形ができあがる」というスゴ技をやっている人がいました。

「あたらしいみかんのむきかた」という本(Amazon の「あたらしいみかんのむきかた」)にはみかんの皮のむき方が書いてあるようなので、実際の絵などは、そちらを見ると分かりやすいかと思います。

これがどうすごいか、というのを数学的な視点からいうと

1.みかんの皮に余りがない(つまり、酉の形になっている皮を戻すと球形に戻る)
2.酉の形は連結である
3.みかんのヘタの部分が酉の目の位置に来ている

の3点が挙げられます。
数理最適化で考えてみると、「3次元多様体から連続的に変化させて得られる2次元多様体で、もっともイメージに近いような変化を求める」というようなことになるかと思われるわけです。

この場合の計算方法としては、次のうちのどちらかなぁ、と思います。
(1)多様体から多様体への写像を求める
(2)皮を離散化して、座標ごとの連結情報を維持しながら、各座標の写像を計算する


うーん、こういったのを頭の中で計算できてしまうとは、世の中には色んな達人がいるものです。


2017年1月13日金曜日

Julia の型変換は、なかなかに難しい (SDPA を Julia で実装する:その3)

Julia では、function の引数に型指定できるので、間違った入力が来ても、引数チェックの時点ではじくことができる。

たとえば、
function func1(x::Int, y::Float64)
とすれば、x は Int, y は Float64 が指定できる。
具体的には、
func1(x::Int, y::Float64) = x+y
等と定義すれば、func1(3, 4.5) で計算できる。


ここで、Int の 3 と Float64 の 4.5 の足し算をすると、Float64 の 7.5 が帰ってくる。
そこで、y のほうに整数を入れても自動的に変換できるだろう、と思うと、実はそうではない。
func1(3,4) とすると、「型が合わない」というエラーが出る。

特に難しいのはベクトルの定義で、例えば
a = [-2; 3; 1]
とすると、Array{Float64} では型が合わないので、基本的には Array{Int}, Array{Float64} のそれぞれで関数を作るか、あるいは float で変換するか、というあたりである。

このあたりを、どうすると簡単に SDPA を使えるようにできるか、検討している。




2017年1月11日水曜日

SDPA を Julia で実装してみる(その2)

SDPA sparse format の読み込みの続きを行った。
Matlab と Julia では、文字列処理が異なるので、単純にコピーするわけにもいかず、このあたりが結構手間がかかる。

Julia では、replace で文字列の置換、split で文字列分解ができて、このあたりは強力な操作ができる。

あと、疎行列については Matlab であればメモリー領域を先に確保しておくことができるが、Julia では同じような機能がない様子。
今は小さいファイルしか読み込んでいないので特に問題ないが、大きい問題になると読み込みに時間がかかりそうだ。

2017年1月10日火曜日

SDPA を Julia で実装してみる(その1)

最近になって、SDPA を Julia で実装しなおしている。
主な理由としては、SDPA のメンテナンスコストを抑えるため。

やはり、SDPAのインストールなどを考えると、コンピュータに関する知識がある程度は必要だし、かといって、OpenBLAS などを毎回コンパイルするのも大変。
そこで、プログラミング言語としても、それなりにスピードがある Julia で実装を行ってみている。


ということで、まずは最初のところとして、SDPA sparse format を Julia に読み込むようにしている。
SDPA では、fscanf の文字処理が強力なので、それに任せているが、Julia だと fscanf を使えないので(libcを経由すれば使えるけど、それだとlibcがないところで使えない)、正規表現で読み込むようにしている。

とりあえずファイルからは読み込めたので、あとは疎行列形式に持たせるようにすれば、OK になるはず。
Matlab に近いインターフェイスにできるだけしたいけど、Matlab だとスピードが出ないところもあるので、そのあたりは適宜修正になりそう。