2016年10月31日月曜日

救急車配置問題を python で解いているサイトがあった

救急車配置問題を python で解こうとしているサイトがあった。

http://qiita.com/Tsutomu-KKE@github/items/ad7214eb150b3de052ea
以下のような方向で発展できるかもしれない。


  1. p-median は LP に定式化できるので、今どきの LP solver なら、まず解ける。これを初期解として改良する、というのはありかもしれない。分枝限定法とも組み合わせられるのではないだろうか?
  2. いま思ったが、p-median に定式化するのと似たような感じで、最も時間がかかるところを最小化するのも LP になる。これも、今どきの LP solver なら、まず解けるだろう。つまり、1,2 のイイトコどりをするような解を構成できるはず。

2016年10月26日水曜日

カミフルについて

新潟に行ったときにカミフルのあたりも見てきたので、思ったことを少し書き留めておいてみる。
(やはり、どんな研究も実際の生活に役に立ってこそ意味があるので、どこかに出かけたときには、いろんな所を見れるだけ見るように歩いたりしている。)

1.場所がわかりにくい
 新潟駅からで徒歩だと結構ある。というか、普通はバスを使うべき距離だった、と後で気がつく。しかしながら、バスが通る大通りの古町のあたりからだと、どこにあるのか、よくわからない。大通りからも、それなりに歩くので、途中で「道間違えたか?」と心配になって帰りそうになった。
 大通りからも分かるような矢印とかほしい。

2.到着しても、ここがカミフルだって気がつかない
 すでにカミフルに到着してから100メートルぐらい歩いてようやく、カミフルにすでに入っていると気がついた。例えば、通りにある柱に統一的なカラーをするとか、見た目だけで「このあたりは、何かの区域なの?」って分かるようになったらいいかと思う。個人的には、緑と青のパステルトーンにしたら似合いそうだと思うが、カミフルに引っ掛けてカラフルにするのもありだと思う。イメージとしては、ヴェネチアのパリーナみたいな感じのものが各お店の入り口にあったら、いいのでは?

3.アニメ・マンガ専門学校との共同作業があってもいいのかも
 せっかくの新潟なので、このあたりで特色を出すのもいいかなと思う。例えば、東京にあるお店と同じようなお店は、もっと新潟駅の近くにあるラブラ万代でも見ることができたので、それとは被らないようにとも思うけど、こういった共同作業でいかにシナジー効果を出せるかが一筋縄ではいかないのも分かる。



今回、新潟の中でも特に「カミフルに行ってみよう」と思ったのは、マンハッタンでいうところのソーホーあるいはチェルシーのように若手の人が集まるアートエリアなのかな?と思ったところにある。
上にはいろいろと書いてはみたけど、実際に行ってみた感じでは、これからの成長力が面白いエリアになりつつあるのかも、と思っている。



2016年10月24日月曜日

arXiv のフォローを外す

今まで arXiv の math.OC カテゴリを RSS でフォローしていたが、このフォローをやめてみることにした。

理由としては、
「面白そうな論文が多すぎて、全部追いかけるのが大変になった」
というところ。
1日に15本ぐらいずつ登録されているんじゃないか、と思うので1週間に100本ぐらいになってしまい、情報過多になってしまったので、思い切ってサクッとやめてみることにしてみた。


2016年10月13日木曜日

Google Optimization Tools

RAMP の予稿集を見ていて、あとでチェックしてみようと思ったのが、
Google Optimization Tools
https://developers.google.com/optimization/

どうやら、ざっと見る限り、線形計画問題や整数計画問題のソルバーのインターフェース、およびナップサック問題の解法とネットワーク最適化計算が実装されているようだ。

ずっと以前にネットワーク最適化のソフトウェアを調べたときには、API などがソフトウェアごとにマチマチで、理論的研究成果がソフトウェア実装にどれだけ反映されているのか調べるのが面倒になってしまいギブアップしてしまった。
Google のソフトウェアがデファクトスタンダードになってくれば、理論的研究でも「Google Optimization Tools と比較して何パーセント性能向上」というような数値実験結果が増える方向にいくんじゃないかと思ったりする。



あと、LPやMIPについては既存ソフトウェアへのインターフェースだけ、ってところは気になるところ。既存ソフトウェアで Google が使うには十分なパフォーマンスが得られるのか。あるいは、LP, MIP は Google としては、それほど高性能である必要はないのか。どっちなんだろう。

RAMP1日目雑感

今日は、RAMP1日目、ということで、聞いてきたことの中から、いろいろと思ったことなどを、つらつらと書いておいてみる。


1.Optimality theorems for convex optimization problems
by Gue Myung Lee (以前に、韓国の応用数理学会の会長だったような気がするけど、他人の空似かも)

いろいろな最適性条件を扱っている。
Theorem 4.1 が「constraint qualification が必要ない最適性条件を作っている」ということなので、これがどういうアイデアで実現できているかを把握できれば、他の証明などにも発展できるかもしれない。
また、SOS-convex という概念を扱っている。キーワードとしては面白そうなので、どういった実用例・応用例があるか把握してみたい。

2.Nonsommth semi-infinite multiobjective optimization problem
by Do Sang Kim

無限個の制約がある多目的最適化問題について扱っている。
どうやら efficient と weakly efficient の違いが、最適性条件にも影響しているようだ。
今日の話は最適性条件の理論面が中心だったけど、計算手法としては、
Approximate quasi efficient solutions in multiobjective optimization
http://ssmr.ro/bulletin/pdf/51-2/predamod.pdf
が参考になるようなので、あとでチェックをしてみるといいかと思う。
また、今日の話では、どれだけ高速に計算できるか、などの話はなかったので、そういった視点からみると、何かいいアイデアが浮かんだりするだろうか?

3.From symmetric cone optimization to nonsymmetric cone optimization: Projection onto nonsymmetric cones
by Jein-Shan Chen

対称錐は、self-dual と homogeneous の2条件を満たす錐であって、これらのときに内点法が上手くいくことになっている。
これらの2条件を満たさないような錐のときにどうなるか、ということ。
特に錐への射影を陽に計算する手段を作れるかどうかを、いくつかの錐について議論している。

個人的に思うのは、self-dual と homogeneous のうち、self-dual はいいにしても、homogeneous は物理でいうところの相対性理論と結びつくところだから、こっちを外すのはしんどいかと思う。
homogeneous であって self-dual でないところがどういう構造をしているのか、のあたりが面白そう。

4. Highlight on recent progress for the trust region subproblem and its variants
by Ruey-Lin Sheu

trust-region subproblem は x^T x \le 1 の制約を持つ QCQP だけど、半径1以外の制約にどのような制約が入ってくると、どれだけ難しくなるか、という話。
Iterative reduction procedure という、問題を分割して解く手法を提案している。
あとで細かく論文を確認してみると良さそう。




あと、個人的には、今日の帰り際にRuey-Lin Sheu 先生に挨拶できたのが良かった。
5年前にお世話になっていながら、そのあとに直接お会いできる機会がなかったので、今回挨拶できたのは良かったと思う。

2016年10月7日金曜日

IguanaTeX のバグを回避する

ghostscript のところで set TEMP が効いてなくてバグになっていた現象だが、bat ファイルを挟むことで回避できることが分かった。

まずは、Powerpoint でIguanaTeX タブの「Main Settings」を開く。
ここでは、Absolute が C:\temp とし、gswin32c がC:\Program Files (x86)\gs\gs9.16\bin\gswin32c.exe となっていたとする。

このとき、以下のような bat ファイルを作り C:\Program Files (x86)\gs\gs9.16\bin\gswin32c2.bat とする。

== ここから ==
@echo off
set TEMP=c:\temp
"C:\Program Files (x86)\gs\gs9.16\bin\gswin32c.exe" %*
== ここまで ==
ここの2行目に、上で得た Absolute、3行目に gswin32c.exe の情報を入れる。

こうやってできた
C:\Program Files (x86)\gs\gs9.16\bin\gswin32c2.bat を
「Main Settings」の ghostscript のところに登録する。

こうすると、gswin32c2.bat 経由で set TEMP をはさんで gswin32c.exe を呼び出せるので、バグが回避できる。

IguanaTeX にバグがある

IguanaTeX は、資料作成のときにとても便利である。
というか、IguanaTeX を使い始めてから、beamer の出番はなくなってしまった。

そんな IguanaTeX でもバグがあって、例えば

${\cal P}$

などが入ると platex では、

Error while using Ghostscript to convert from PDF to PNG. Is your path correct?

というエラーメッセージが出る。
ちなみに、${\cal P}$ を外すと普通に platex でコンパイルできるので、パスが違っているわけでもない。

IguanaTeX のデバッグモードで見ると、IguanaTex_tmp_tmp.png を生成するときに失敗している。
このコマンドをコマンドラインから実行すると、

GPL Ghostscript 9.10: **** Could not open temporary file ''
GPL Ghostscript 9.10: Could not open the scratch file .
**** Unable to open the initial device, quitting.

Temp folder の設定が反映されていないようで、コマンドラインからだと set TEMP= を設定すると実行できる。ただ、ppam ファイルを解析していないので、ppam ファイルの中で TEMP をどのようにコントロールしているかが、ちょっとわからない。




まぁ、こんなバグが残ってはいるけど、IguanaTeX は、すごく便利。
もはや、これなしで資料を作るとか大変すぎる。

2016年10月5日水曜日

Uzawa method の実装に挑戦

ICCOPTで勉強してきた Uzawa method をSDPについて実装を行ってみた。
コアとなるアルゴリズムは、Matlab なら 30 行程度で実装できる。

1反復当たりの計算量はADMM よりも小さい(計算量オーダーで違う)ので、各反復は高速だが、やはり収束までの反復回数が相当かかる。

特に、理論的に収束させるためのステップ幅が 1.0e-5 よりも短くなるのが厳しい。
適当にステップ幅を大きくすると、当然ながら点列は収束しないで、どっか明後日の方向に飛んでってしまう。

SDPA にある example1.dat-s なら 100 反復程度なので結構高速だが、SDPLIB にある control1.dat-s を解こうとしたところ 100 万反復(「万」に注意)しても、解に近づけなかった。

ちなみに、「Uzawa method は双対問題への劣勾配法に相当する」、と書いてある論文があった。

やはり参考にしている元論文と同じように特定の状況のみに使うべきか、あるいは、もう少し別のスピードアップを検討するべきか。Uzawa method は、もともと広範囲のアルゴリズムなので、スピードアップについてもいろいろと研究があることだし。


2016年10月4日火曜日

列生成法を勉強するための資料

列生成法を勉強する上で基本的なところを学ぶことができるのが、

"A tutorial on column generation and branch-and-price for vehicle routing problems"
4OR, December 2010, Volume 8, Issue 4, pp 407–424
http://link.springer.com/article/10.1007%2Fs10288-010-0130-z
になっている。


日本語の場合は、
「はじめての列生成法」
http://www.orsj.or.jp/archive2/or57-04/or57_4_198.pdf
が非常によく書けていて参考になる。