論文読み：Minotaur: A Mixed-Integer Nonlinear Optimization Toolkit

Optimization Online のところから、もうひとつ論文読み。

Minotaur: A Mixed-Integer Nonlinear Optimization Toolkit
http://www.optimization-online.org/DB_HTML/2017/10/6275.html

基本的には、タイトルにある通り、混合整数非線形最適化問題を解くソフトウェアを作りました、という内容。
アルゴリズムも分枝限定法を使っていて、内部的には CLP, Gurobi, CPLEX, BQPD, qpOASES, FilterSQP, IPOPT を呼んでいる。
インターフェースは C++ なので、実装するのは結構大変。

できれば、Julia にある JuMP.jl から呼び出せるようになってくれると便利だと思う。(JuMP.jlから呼び出せるライブラリは、まだまだ拡大の余地が大きいので。）

経営工学会でフラストレーション溜まりまくり

先週にパシフィコ横浜で行われた経営工学会の秋季大会に参加してきて、いろいろと発表を聞いてきた結果、フラストレーションが溜まりまくった、という話。

いろんな発表があるわけだけど、「この研究は、こういった数学を使ったら、もっと解析できるかも」というのが多くて、数理最適化としては研究の素になりそうな内容がゴロゴロと転がっていた。結果として「あれもやってみたいし、これもやってみたい。どれからやってみればいいのか分からん」というところになった。

やはり、一度に複数はできないので、とりあえず一つずつ検討してみたほうが良さそうにも思ったりしている。

論文読み：Enriching Solutions to Combinatorial Problems via Solution Engineering

１１月の optimization online の更新が来ていたので、いくつかを論文読みをしてみた。
そのうちの一つが

Enriching Solutions to Combinatorial Problems via Solution Engineering
http://www.optimization-online.org/DB_HTML/2017/10/6252.html

簡単にいうと、組合せ最適化問題では同じ最適値を達成するような最適解が大量にある場合があって、そのようなときに大量の最適解から特徴的な最適解をどのように取り出すか、という話。

ざっくりと手法をまとめると、多様性を表すような目的関数を作って、別の最適化問題を解いている。
また、既に得られている最適解を切除平面で外すことで別の最適解を得たりしている。

個人的に思うに、「特徴的な解」に含まれる「特徴的な」の部分をどのように数学的に表すかは様々な方法があるから、割り当て問題などでの現実的なサイズになるとどうなるか、というあたりが結構大変そう、と思ったりする。

Chubanov の方法を凸結合したら面白そうね、って話

この前の RAMP で線形計画問題などを含む Chubanov の方法についての話があって、とても勉強になった。Chubanov の方法が流行っている、というのは既に聞いていたが、自分では勉強していなかったので、いい機会でもあった。

個人的な印象としては、
「漠然と想像していたよりも内点法に似通っている」
というところ。
基本的には、錐の中心へとスケーリングする、という計算方法がKarmarkar の内点法に近い印象になっているのではないかと思う。

対称錐の場合、homogeneous の性質が効くため、錐の中心とすべての実行可能内点は同じとみなすことができるので、Karmarkar の内点法で生成される内点の点列以外にも内点の点列が作れる、ということである。

単純に考えると、Karmarkar の内点法の生成する点列と Chubanov の内点法の生成する点列で凸結合を取れば、それら２つの方法を統合した計算手法が作れるんだろうなぁ、って思う。
そうすると、最初の反復では計算効率の良い Karmarkar 法を使って、解の近くに近づいたら Chubanov 法に切り替えて固有値計算をうまくやる、とかできるかとは思う。

Julia で Mosek 8 がこけるので、Mosek 7 を使えるようにする

Julia を Linux 上で動かしていて、ここから Mosek を呼びたいのだが、なぜか Segmentation fault が起こってしまい失敗する。
たぶん libc のバージョンとかがあっていないんだろうなぁ、と勝手に推測しているわけだが、Matlab から Mosek を呼んでも Segmentation fault が起こる。

そこで、Mosek.jl を build しなおして、Mosek 7 を利用するようにする。
まずは、julia で Mosek.jl をインストールする。
julia> Pkg.add("Mosek")
そのあとで、
$ cd ~/.julia/v0.6/Mosek/deps
に移動して、build.jl の最初にある
mskvmajor = "8"
mskvminor_minimum = 1
を
mskvmajor = "7"
mskvminor_minimum = 0
に修正する。
本来 Mosek.jl は Mosekのバージョンが 8.1 以降にしか対応していないので、そのバージョンチェックを 7 でも通過できるように修正していることになる。
（このあたりの不具合は、どっかで出てくるかもしれない。）

そのあとで、
$ cd ~/.julia/v0.6/Mosek/deps
$ MOSEKBINDIR=/home/username/mosek/7/tools/platform/linux64x86/bin julia -e 'include("build.jl")'

としてパッケージを build しなおす。このとき MOSEKBINDIR は Mosek のインストールされたディレクトリにあわせて適宜修正する。

これで何はともあれ Mosek 7 を Julia から呼べるようになる。

モデリング言語特集を読んでみて

今回の OPTIMA (つまり OPTIMA 103) はモデリング言語特集ということで、
JuMP (Julia), PuLP (Python), CVXPY (Python), ompr (R), ZIMPL
について書いてあって、それぞれの比較があって面白かった。

プログラミング言語としては、やはり Julia は R や Python よりも後発なだけあって使い勝手なども向上しているが、モデリング言語として考えると他との連携もあるので単純に比較するのは難しいので、結局最後は好みの問題とかこれまでの経験とかで決まるんだろうなぁ、と思ったりもする。

あと、それぞれのサンプルがあるが、サンプルとして数独が使われていることが多くて、研究者の中では数独って手ごろな問題としても面白いんだろうなぁ、って思ったりもする。

論文読み：Julia で Feasiblity Pump

Julia で Feasibility Pump ベースのヒューリスティクスを実装した、という内容があったので、チェックしてみた。

FPBH.jl: A Feasibility Pump Based Heuristic for Multi-objective Mixed Integer Linear Programming in Julia
http://www.optimization-online.org/DB_HTML/2017/09/6195.html

手法としては、多目的関数最小化問題の Pareto をどうやっていくのか、というのがメインで、Feasibility Pump はサブぐらいの位置づけだった。
あと、Julia で整数計画問題を解くところは、CPLEX.jl を使っている。