論文読み：Theoretical challenges towards cutting-plane selection

切除平面法についての理論面の情報を集めた論文が出ていた。

https://link.springer.com/content/pdf/10.1007%2Fs10107-018-1302-4.pdf

サーベイのような位置づけの論文で、どういった cut があるのか、それらがどういう性質を持っているのか、などがまとめられている。
確率論的な立場で cut の性質を証明している Theorem 1 は、こういった視点があるのか、と思ったりする。

あと、この論文の Final Remarks は秀逸。
the answers may not be unique.
の他にも含蓄の多い言葉が並んでいる。
Final Remarks 全体を引用したくなるけど、そうすると引用としては長くなりすぎるので止めておくが、CPLEX, GuRoBi などを使っている人は、一読の価値があるんじゃないかと思う。

sharelatex の synctex がズレるのを回避できる

sharelatex は便利だけど、synctex で PDF から tex に移動したときに数十行ぐらい常にズレるのが気になっていた。つまり、PDF で範囲指定をしてから、画面中央の左矢印で tex に移動すると、範囲指定していたところからは数十行ズレた位置に移動してしまう。

ずっと気になっていたのだが、今日何気に PDF をダブルクリックしてみたら、tex が該当箇所にほぼ正確に移動できることが分かった。
こんなに簡単な方法で回避できるとは思ってもみなかった。

発表した内容よりもいい定式化に気がついた

土曜日に発表したときに定式化をあげたけど、今朝の通勤時間にもっといい式変形があることに気がついた。非ゼロの数を1/3程度にできる。

で、３０分ぐらいでプログラムを作って実行してみたけど、思っていたほど効果が出ない。
計算時間だと 5 % 程度しか削減できない。
内点法の動きは、ちょっと謎だ。

まぁ、今回のはうまく行かなかったけど、first-order method に使えるかもしれないんで、もう少し考えてみることにする。

研究集会で発表してきた

土曜日にあった研究集会で発表をさせてもらった。
今回の発表では、ここまでの研究内容の棚卸もいろいろとできたし、もらったコメントも勉強になるコメントが多く、とてもいい機会になった。

今回の内容については、似たような構造の数理最適化問題がたくさんあるので、まだまだ何本も論文にできるような内容を含んでいるかと思うし、もっと時間を使ってやっていけたら、とも思う。今回の発表でもらったコメントなどで「Todoリスト」も強化できたし。

また、数理最適化があまり使われてこなかった分野の話でもあるけど、数理最適化手法が強い効果を発揮したりもするので、数理最適化手法を作れる人には面白いかな、と思ったりもする。個人的には、離散最適化の人が入ってきたりしたらアルゴリズムを作るという意味では無敵なんだろうな、と予想していたりもするけど、その一方で参入障壁も大きいかもしれない。

あと、違った分野の人とやり取りをしていると、「数理最適化だけだと井の蛙かも？」ということに気づいたりする。専門用語の違いから話が全く通じなかったりすることもあったりするけど（自分の英語力のなさも見落とせない要素だけど）、分野の違いを超えて研究をするのにどういったことが大事なのか、ということを教わったりもする。こういった経験は、別に進めている放射線治療に関する最適化などの勉強にも役立っている。


あと、今回の発表で細かいところでは、最後の質問が終わったところでピッタリ予定の時間になったのが、「あぁ、こういう偶然ってあるもんなんだなぁ」と思ったりもした。発表スピードは自分でコントロールできるにしても、質問の数とかは自分ではコントロールできるものではないし。

そんな色々があるにしても、もうちょっと研究を頑張って、いろんなところに役立てられるようになれれば、と思う今日この頃。

sharelatex の日本語入力がうまくいかない

ローカルなところにインストールした sharelatex だが、今までほとんど英語しか入力してなかったので気にならなかったが、日本語を入力しようとすると変な四角が出てきて、これがどうしたものか、というところ。

具体的には、
https://qiita.com/RAWSEQ/items/7f9fc0fd4b3d572856ed
にあるような Ace エディタで日本語入力するときのトラブルと同じ症状なのだけど、これを sharelatex で回避するにはどうしたらいいかが今一つよくわからない。

うーん、ローカルで CSS 制御すれば回避できそうだけど、それを調べるのも今のところは面倒だし、どうしたものか。

まぁ、その点を除けば sharelatex はとても良くできていて、やっぱり便利。

CPLEX の前処理をパズル感覚で楽しむ

最近、CPLEX で LP を解いているが、CPLEX の前処理が思っていた以上に優秀である。
例えば、A*x = b という等式制約を A*x <= b と (-A)*x <= (-b) と２つの不等式制約に分解すると一般的には内点がなくなるので、内点法では解きにくいはずである。しかも、A と (-A) が両方入ると行の線形独立も失われれる。
単純に内点法を組むとうまく行かない、という典型例なのだが、CPLEX だと前処理がきちんと働いて、それなりに数値的に安定して解ける。

ということで、CPLEX の前処理ではうまく処理できないような LP の例を簡単に作れないだろうか？ということを試してみているのだが、これがパズル感覚でなかなかに面白い。
単純に A と (-A) を入れるだけでなくて、もう少し細工をしたりすると CPLEX が CPX_STAT_NUM_BEST を返すようになる。

もっと単純な例で CPX_STAT_NUM_BEST を出せないだろうか？と、ついついいじり倒してしまう。

ただ、「こういう例で CPX_STAT_NUM_BESTを出せるよ」という例題をインターネットに公開してしまうと、CPLEX の開発者がうっかり見つけてしまって、それを回避してしまう前処理を入れてしまうかもしれないから、イタチごっごかもしれないけど。

台湾、進んでるなぁ

INFORMS の雑誌に台湾の AI とかブロックチェーンとかの話が載っていたのでパラパラと読んでみたけど、第一印象としては「台湾、進んでるなぁ」ということだった。

結構実用化に近いことをやってたりもしているようなので、重要な特許とかは先に抑えたりとかもしているかもしれない。（ブロックチェーンについては、特許を押さえるようにしている企業が日本の中にもある、というのを読んだ記憶がある。）
そうなると、こういった分野で基礎研究の論文とか書くにしても、特許と重なってないか、とかを慎重に調べる必要があるんだろうなぁ、と思ったりする。論文のデータベースで検索とかする時に特許の情報が一緒に掲載されたりということは見たことがないから、両方調べたりするのは大変そう。

AIとかブロックチェーンとかだと、台湾はこれから大きく発展していくのかもしれない、と思うような話だった。