mits58のメモ

メモ 参考にしないでください

IPCO 2019 目を通したリスト

IPCO って思ったより Integer Programming よりなんですね……

1. Integer Programming and Incidence Treedepth - Eduard Eiben, Robert Ganian, Sebastian Ordyniak, Michal Philipczuk and Marcin Wrochna.

  • 整数計画問題の容易さは、制約行列の構造と深く関係しているってのが最近わかった。具体的には、制約行列の Gaifman graph の primal (or dual) treedepth と、絶対値最大の係数に関して FPT ってのがわかった。
  • これを、より広いクラスの整数線形計画問題に対して拡張してみたらどう?ってのがこの論文らしい。結果としては、FPT ではなくて、すべての係数の絶対値が 1 で、incidence treedepth が 5 であるときでさえ NP-hard だったらしい。
  • Gaifman graph とはなんぞや……と思ったら、ノードが変数で、ある制約条件に共起する場合、そのノード間に辺を張ってできるグラフらしい。
  • Treedepth もよくわかっていないので調べたら、TREE-DEPTH AND VERTEX-MINORS に、スターグラフにどれくらい近いかを測る指標っぽい(小さいとスターグラフに近いって感じ)
  • 問題に対応するグラフ構造を使って解析しているのは面白いなぁ、こういうのやってみたい。

2. Strong mixed-integer programming formulations for trained neural networks - Ross Anderson, Joey Huchette, Christian Tjandraatmadja and Juan Pablo Vielma.

  • 訓練済みニューラルネットワークに対応する、高次の区分的線形関数に対する強い混合整数計画定式化を提案。
  • この定式化は、画像分類ネットワークが敵対的入力に対しロバストであることの証明や、機械学習モデルが目的関数である決定問題を解く際に用いることができる。
  • このMIP定式化を ReLU とか Max Pooling とかに適用してみて、画像分類タスクにおけるネットワークで推論時間がかなり改善したっぽい。
  • 正直???という感じだけど、面白そうではある。ただ、Neural Network そのものに対しての解析はかなりやられてそうだし今更感も……?

3. A Bundle Approach for SDPs with Exact Subgraph Constraints - Elisabeth Gaar and Franz Rendl.

  • 厳密部分グラフアプローチってのは、いくつかのグラフ上の NP-hard な問題に対するよりタイトな半正定値計画緩和を得るための階層的なスキーマなんだけど、これを解くのは禁止部分グラフ制約が多すぎてつらい。
  • 部分的なラグランジュ双対を導入して、その評価が2つの独立した部分問題になるという事実を利用するらしい。よくありそうなテク。

arXiv になかったのとかもあって悲しみ。