2017年11月17日金曜日

待ち行列の研究って、純粋数学になっていくよね、と思ったりすること

病院の患者などを研究している論文があって、その中に

1.患者の待ち時間
2.患者が病院にいる総時間
3.ベッドの使用率

をシミュレーションで解析している論文があった。

自分としては、「これって、待ち行列で解析すればいいのでは?」と思ったわけだが、論文ではシミュレーションソフトを使って解析していた。

そこで「待ち行列で解析」という考えを一度横において考えてみると、シミュレーションソフトを使って待ち行列を解析して、それで実用的な結果が得られる、というのは、確かにありかもしれない。

数理最適化についても、コンピュータの性能が上がればシミュレーションで十分になる範囲も格段に向上するだろうし、現段階では応用数学に分類されることが多い数理最適化も将来的には純粋数学に仲間入りすることもあり得るのかも、と思ったりもする。




2017年11月10日金曜日

Julia で返り値を複数の中から一つだけ取り出したいとき

たとえば、対称行列 A の固有値分解は

D, V = eig(A)

とすると得られるが、ここで V は不要だから D だけ欲しい、というときも結構ある。
その時は
D = (eig(A))[1]
とすると最初の引数だけが得られる。

もちろん、2番目がほしい時は
V = (eig(A))[2]
とすればよい。

ちなみに、配列の中で順番を入れ替えることもできて
V, D  = (eig(A))[[2 1]]
としたりすればよい。
ただし、[[2 1]]は2重カッコのように見えるが、(eig(A))[2 1] のように1重カッコだとエラーになって処理されない。

unimodular な SOCP

いま手元で作っている SOCP が良く良くデータを見てみたら、
||U*x|| <= a'*x + b
という形式で、行列の U のところが unimodular になっていた。

unimodular な場合っていうのは、何かに使えたりするんだろうか?


2017年11月8日水曜日

論文読み:From feasibility to improvement to proof: three phases of solving mixed-integer programs

今回は、Optimization Online とは別に、雑誌に掲載された論文をチェックしてみた。

From feasibility to improvement to proof: three phases of solving mixed-integer programs
http://www.tandfonline.com/doi/full/10.1080/10556788.2017.1392519

整数計画問題を厳密に解く時には分枝限定法が一般に用いられるが、この論文は以下のような良く見られる状況に着目している。
1.最初の実行可能解を得るまでの時間は、最適解を得るまでよりも短い
2.最適解を得るまでの時間は、その解が最適であると保証するまでの時間よりも短い

したがって、分枝限定法を3段階に分けていて、
 1.最初の実行可能解を見つけるまで
 2.最適解を見つけるまで
 3.最適解が最適であると保証できるまで
これらの3段階でどのように推移していくか、というヒューリスティクスを議論している。
数値実験を見る限り、それなりにうまく動いているヒューリスティクスのようだ。

整数計画問題を近似的に解く方法として様々なヒューリスティクスが提案されているが、このような分枝限定法のヒューリスティクスを用いて他のヒューリスティクスを改良したら面白いかもしれない。


2017年11月7日火曜日

論文読み: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から呼び出せるライブラリは、まだまだ拡大の余地が大きいので。)

2017年11月6日月曜日

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

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

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

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

2017年11月5日日曜日

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

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

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

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

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

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