新しい最適化の概念

数理最適化の分野では first-order method のような手法が「大規模なデータ」を扱えるということで多くの研究がされてきたが、昨日チェックしたもう１本の論文では、「first-order method が扱えるような小さなデータではなくて、ちゃんとした規模のデータを扱いたい」という話が載っていた。

そのために、今までの数理最適化の概念とは全く異なる最適化の概念を導入していて、簡単にいうと
「最適値や最適解を求めない」
というもの。

「なるほど、そういう考え方があったか」という気分で、目から鱗がパラパラ。

Home Health Care の論文をチェック

今回は、

OR problems related to Home Health Care: A review of relevant routing and scheduling problems,
Operations Research for Health Care (2017), http://dx.doi.org/10.1016/j.orhc.2017.06.001

という論文をチェックしてみた。
簡単にいうと、「自宅療養をしているような患者さんが複数いる場合に看護師がどういう順番で患者さんを見て回ったらいいか？」というような内容で研究している論文のサーベイだった。

結構面白いテーマかと思って読んだわけだけど、それぞれの論文でケースバイケースでアルゴリズムを作っている感じだった。ある意味で行き当たりばったりなアプローチが多く、うまく行く理由がたまたまなのか、ちゃんと科学的理由があるのか、検証がなされていないようだ。

一番致命的なのは、他の研究者がデータにアクセスできない（たぶん、公開を前提としてのデータ収集が行われていないためだろうな、とは思う）ことで、論文の結果を再現できないことだと思う。

このサーベイで指摘されているように、ベンチマークのようなデータセットがあって、それで試すことで本当に有益な手法なのかが分かるようになるのかもしれない。

クロスドッキングセンターの出庫エリアにおけるシュート・ドック割り当てとその解法の提案

論文を読んでみたので、思ったあたりをメモ書きしておく。

１．問題を mixed integer linear programming (MILP) で定式化する
２．MILP が小さい場合は Gurobi で解く
３．大きくなる場合は、遺伝的アルゴリズム＋局所探索で解く
４．数値実験では、MILP が小さい場合は Gurobi で解いた解と同程度の解を遺伝的アルゴリズム＋局所探索で得ることができる


読んでみた限りだと、遺伝的アルゴリズムと局所探索の実装は、問題にあまり特化せずに比較的スタンダードな実装が行われているようだ。
数理最適化の視点だと、ガッチリと問題の性質を使いまくった複雑なアルゴリズムを作って、その定理とか証明したりなっちゃうかもしれないけど、実用上では厳密解を求める必要がないから、こういうアプローチはありだなぁ、と思ったりする。

内点法の謎

内点法のソフトウェアで大きな謎なのが

「理論的には近傍を作ったほうがいいのに、数値実験では近傍を作らないほうがパフォーマンスがよい」

ということ。
近傍を作らなかった場合の解析というのは、まだ改良の余地があるのではないか？と思ったりする。

MUMPS がバージョンアップしていた

いままで気がついてなかったけど、SDPA の Debian パッケージがコンパイルできなくなっている、という連絡が来ていて、その理由として SDPA が利用している MUMPS の Debian パッケージの バージョンが上がっていることがあるようだ。

いままで何年もずっと 4.10 のままだったけど、5.1.1 になったようだ。

ちょうどいい機会でもあるので、SDPA も OpenBLAS に切り替えたりしつつ MUMPS の調整をするのがよさそうだ。
とはいえ、MUMPS の Debian パッケージも sid にあがってきたばかりのようなので、少し下調べしてみようと思う。

Facial Reduction 難しいなぁ

SDP に内点がない場合、Slater の制約想定を満たさないので、理論的には内点法ではうまく解けない。
そういったときに内点がある問題に SDP を修正する枠組みとして、Facial Reduction がある。
ということで、それを手元にある SDP に適用したりしてみているが、これがSDPソルバーで解いてみると、あんまり上手くいかない。簡単にいうと、精度が向上しない。

結構重要なこととして、
「SDP ソルバーで十分な精度で解けるかどうか、と、内点があるかないかというのは、それほど関係がない」
ということがある。
やはり、double 型が 64bit という影響は強くて、64bit 用の Facial Reduction というのを作ればいいんだろうなぁ、と思ったりしている。

TeX の数式を Word の数式に変換する

普段は TeX で数式を書いていると、たまに Word で数式を書かないといけないときが苦行である。
今日は、$$\sum_{i=1}^Z g_i x_i$$ という式を入れようとして、力尽きた。

で、いろいろと調べた結果、pandoc を使うと、ある程度は TeX を Word に変換できる。
例えば
$ pandoc -s sample.tex -o sample.docx
とすればよい。

もちろん、pandoc も完ぺきではなくて、数式の途中に色を使ってみたりとか、文章の途中で underline とか入れるとうまく処理ができなくなるようなので、pandoc では簡単な数式だけを処理させて、それを Word に貼りつけて色を調整したりとかするほうが楽ちんでもある。