ISMP 3日目

パラレルセッションがたくさんあってどこにいくか困ります．

今日の1つ目．Matteo Fischettiによる招待講演「Pure cutting plane methods for integer linear programming: A computational perspective」．なんですか，これは．無茶苦茶面白いんですけど．Fractional Gomory cutだけでどこまでILPが解けるか突き詰めてみる話．何も考えずに実装しちゃうと全然だめだし，そもそも最適解に収束する前にsaturationを起こしてしまう．これで，ああだめでした，で終わらないのがすごくて，ちゃんと原因を突き詰める．突き詰めてみると，カットの生成法と退化が絶妙に絡んで悪さをしていることが分かる，と．そもそもGomoryの原論文では辞書順を用いてカットを生成し，それによって(退化を避けるように)収束性を示していたのだけど，普通はそんなことしない．というのは，それが理論的な収束性を示すためだけに重要なものだと思われていたから．しかし，実際はそれをやってみるとうまくいく．さて，どうして？となったとき，辞書式最適なものに対応するタブローがよい性質をもっていることが分かる．しかも，辞書順をうまく操作することで必ず非整数変数でbranchできるようになり，効率も増す．実際計算機実験をしてみると各段にパワフル．計算機実験から得られた知見をデータとして上手に解析し，それを理論的な考察に生かす．そして，それをまた実装して実験する，というサイクルが見事に噛み合っていてとても楽しかった．実は，アルゴリズムに対する実験の論文で，データ解析の甘さや，そこから得る知見に対する考察の浅さが目立つものは割と多く，そういうことに不満を持っていたので，このような素晴らしい研究を目の当たりにすると，気持ちが晴れ晴れする．それぐらい感激した．

階数最小化のセッションからMaryam Fazelの「A null-space analysis of the nuclear norm heuristic using the spherical section property」．あるアフィン空間上にある行列の階数を最小化する問題というのがシステム同定，機械学習，距離再構成，データマイニングのようないろんなところで現れてきていて，Fazelらの研究により，それとcompressed sensingの密接な関係が明らかになってきている．という背景のもとで，実際，階数最小化は非凸最適化なので，nuclear norm heuristicと呼ばれる方法でそれを凸最適化 (SDP緩和) に変換し，それを解く．そこで，このSDPを解くことで元の問題が解けてしまっていることが多いという経験則があるので，それを理論的に考察した，という内容．ここでは考えているアフィン空間の性質としてspherical section propertyというものを考えて，その性質を持つ問題に対してSDP緩和の解の一意性と元問題とのギャップが0であるということを証明している．

同じく階数最小化のセッションからStephen Vavasisの「Nuclear norm minimization for the planted clique and biclique problems」．最大クリーク問題や最大二部クリーク問題は階数最小化問題として定式化ができるので，それに対してnuclear norm heuristicを適用したらどうなるか，という話．いわゆるplantedモデルに対してnuclear norm heuristicが最適解を出力する，ということを証明している．証明では最適化のKKT条件とランダム行列の理論を用いているように見えた．

今日の2つ目の招待講演．David Shmoysの「Strong LP formulations in the design and analysis of approximation algorithms」．主にminimum knapsack problemとsingle-item lot-sizing problemを例題として，LPをもとにした近似アルゴリズム設計の方法論を紹介した．Minimum knapsack problemは普通にIPとして定式化し，普通にLP緩和をするとintegrality gapが発散してしまう場合がある．なので，これでは近似アルゴリズム設計ができない．なので，Carr, Fleischer, Leung, Phillips 2000はknapsack cover inequalityという不等式を考えて，これを付け加えてもIPは変わらないが，LP緩和が強くなることを示して，実際にLP丸め法による2近似アルゴリズムを設計した．最近CarnesとShmoysがこれの主双対法版を考案し，かなりシンプルになったので，これについては詳しく紹介された．なかなか鮮やか．その後で，Bienstock 2008とBienstock and McClosky 2008によるPTASが紹介されて，そこで取られた奇妙な部分列挙法はとても勉強になった．