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 緩和などの緩和手法で近似値を低コストで得る
などなど、いろんな発展があるんじゃないかと思う。

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