SOCP に対する多項式時間アルゴリズム

Optimization Online に最近掲載された

http://www.optimization-online.org/DB_FILE/2016/11/5713.pdf

をざっと眺めてみると、SOCP に対する多項式時間アルゴリズムが載っていて、内点法とも近いような、それでいてそうでもないような感じで面白いと思う。

標準形を特定の形式に変形することでアルゴリズムを作るってところは Karmarkar の内点法に似たような感じもあるし、途中で体積の計算をしたりしているところは楕円体法を思い出したりもする。

気になるのは、
（１）実際にプログラムを組んでみたら、どれくらいの性能が出るのか？
（２）内点法よりも数値誤差に強いだろうか？

特に（２）のところは、実行可能内点がない問題がとけるようになれば、ぜひ使ってみたいところ。でも、これはやっぱり難しい？

NASA との共同研究での 3D パッキング問題

INFORMS Annual Meeting で聞いた発表のひとつに、NASA との共同研究で 3D パッキング問題を解いている、というものがあった。

ふつうの問題とは若干違っていて、ひょっとしたら数学的性質がかなり違うのかもしれない。
発表の中では、「厳密解を求めるために、今は整数計画問題として解いている」ということで、定式化されている整数計画問題は比較的オーソドックスに定式化されていた。

これは、なかなかに面白いネタだと思う。
例えば、
１）定式化を工夫して、冗長な情報を除去したり、CPLEX などで高速に解けるようにする
２） Bender's decomposition などが使えるか検討する
３） Lagraingian 緩和, SDP 緩和などの緩和手法で近似値を低コストで得る
などなど、いろんな発展があるんじゃないかと思う。

発表のパワーポイント資料を発表者から頂くことができたので、定式化については検討してみようと思う。

PDF の日本語目次を pdftk で修正する

PDF を結合したりするときに使う pdftk だが、目次を入れ替えることもできる。
このときに、utf8 を使えば日本語でも大丈夫になる。

例えば、a.pdf の目次情報を取り出すなら、
$ pdftk a.pdf dump_data_utf8 output mokuji.txt
として mokuji.txt に取り出せる。
これをutf8 の文字コードのまま編集してセーブしたら
$ pdftk a.pdf update_info_utf8 mokuji.txt output a2.pdf
とすれば、他の内容を引き継ぎつつ、目次情報だけを更新できる。

あるいは、目次情報などが全くない PDF に対しても、
https://www.pdflabs.com/blog/export-and-import-pdf-bookmarks/
を参考にしつつ、以下のような mokuji.txt をutf8で作ればOKである。

BookmarkBegin
BookmarkTitle: 日本語目次
BookmarkLevel: 1
BookmarkPageNumber: 1
BookmarkBegin
BookmarkTitle: 目次ページ
BookmarkLevel: 2
BookmarkPageNumber: 3

Bixby がなぜ CPLEX を止めたか

Bixby がなぜ CPLEX を止めたのか、その理由が今回の OPTIMA (OPTIMA 101) に掲載されているインタビュー記事の途中に書いてあった。
このインタビューは、いろいろと書いてあるので、非常に面白い。

まだインターネットには掲載されていないけど、そのうちに
http://www.mathopt.org/Optima-Issues/optima101.pdf
にアップロードされるのだと思う。

Julia のエディタとして Visual Studio Code を試してみる

Julia を使うためのエディタとして Visual Studio Code を試してみた。
まず、Visual Studio Code は、
https://code.visualstudio.com/docs/?dv=winzip
から Windows 版の zip ファイルをダウンロードして、zip ファイルを展開して使ってみた。

次に Visual Studio Code を実行して、「表示」-「拡張機能」で検索できる状態にして、「julia」として検索。これで Julia のサポートが入る。

また、linter の設定として、settings.json に
"julia.validate.executablePath":"C:\\Users\\ユーザー名\\AppData\\Local\\Julia-0.4.5\\bin\\julia.exe"
を追加する。
ちなみに、パスの区切りはバックスラッシュが２個になるところに注意。
settings.json の構文を間違えると、Visual Studio Code のウィンドウの一番左下にある x マークの数字が増えるので、xマークのところをチェックすると理由を教えてくれる。

これで一通り設定は終了。

使ってみると、エディタとして、構文サポートをしてくれる。
なお、エディタとターミナルは連携しておらず、「デバッグ」-「統合ターミナル」と開いても、julia.exe が起動するわけでもないし、julia.exe のディレクトリに移動するわけでもない。
したがって、普通のエディタとコマンドプロンプトを起動して、それらのウィンドウを上下に並ぶように配置したぐらいの効果が得られる。

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

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

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

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

カミフルについて

新潟に行ったときにカミフルのあたりも見てきたので、思ったことを少し書き留めておいてみる。

（やはり、どんな研究も実際の生活に役に立ってこそ意味があるので、どこかに出かけたときには、いろんな所を見れるだけ見るように歩いたりしている。）

１．場所がわかりにくい

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

　大通りからも分かるような矢印とかほしい。

２．到着しても、ここがカミフルだって気がつかない

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

３．アニメ・マンガ専門学校との共同作業があってもいいのかも

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

今回、新潟の中でも特に「カミフルに行ってみよう」と思ったのは、マンハッタンでいうところのソーホーあるいはチェルシーのように若手の人が集まるアートエリアなのかな？と思ったところにある。

上にはいろいろと書いてはみたけど、実際に行ってみた感じでは、これからの成長力が面白いエリアになりつつあるのかも、と思っている。