2017年7月21日金曜日

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

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

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


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


2017年7月19日水曜日

内点法の謎

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

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

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

2017年7月16日日曜日

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

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

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

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


2017年7月4日火曜日

Facial Reduction 難しいなぁ

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

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