(iwi)の日記

ALENEX'15 論文採択：指数時間 Branch-and-Reduce アルゴリズムの実性能

13:03 |

国際学会 ALENEX 2015 に論文が採択されました．ALENEX (Meeting on Algorithm Engineering & Experiments) は実験系アルゴリズム (experimental algorithmics) を扱う最も有名な会議の 1 つで，理論系アルゴリズムのトップ学会 SODA (Symposium on Discrete Algorithms) に併設して開催されます．発表は来年の 1 月にアメリカの San Diego です．

今回の論文は "Branch-and-Reduce Exponential/FPT Algorithms in Practice: A Case Study of Vertex Cover" というタイトルで，研究室同期の岩田との共著です．

背景１：アルゴリズム研究における理論と実性能の乖離

アルゴリズムが好きな人はよく御存知の通り，アルゴリズムの世界には理論（オーダーによる計算量解析）と実性能（実装し実データに適用した際の性能）に大きな乖離があります．これは，理論コミュニティでのアルゴリズムの評価基準が，理論的な計算量の改善を証明できるか否かのみにほぼなっており，本当に実性能が優れているかをほぼ全く考慮しないことによるものです．それ故，「理論的に計算量を改善するアプローチ」と「現実のデータにおける高速化を達成するアプローチ」に大きな違いがある場合も少なくなく，しばしば，理論的なアルゴリズム研究の価値が問われることとなってしまっています．

背景２：厳密指数時間アルゴリズムにおける理論と実性能の乖離

大きな乖離が存在する一つのアルゴリズム研究分野として，探索・最適化のアルゴリズムがあります．

例えば，実際によく用いられている CPLEX や Gurobi などの最適化ソフトウェアは，branch and cut と呼ばれるフレームワークに基づいており，良い cut を導入することによって探索空間を狭めてゆく工夫が中心となっています．一方，理論コミュニティでは branch and cut が扱われることは殆どありません．これは，理論的な計算量の改善を証明することが困難であるからです．

そこで，理論コミュニティでは，計算量の改善が証明可能な異なるアプローチが次々と提案されてきました．その 1 つが，branch and reduce と呼ばれるものです．問題を簡潔化する reduction rule を導入することで，受け取るインスタンスを reduction 済みのものと仮定します．すると，可能性が限定されるため，探索の分岐数を理論的に抑えることができます．例えば，頂点被覆問題では O*(1.212^n) 時間での動作が理論的に保証可能なアルゴリズムがこのアプローチにより提案されています．

（詳しくは岩田のこの資料の P.29 からをどうぞ：指数時間アルゴリズム入門）

本論文の内容：branch and reduce アルゴリズムは本当に理論的価値しか持たないのか？

本論文では「こういった branch and reduce のアルゴリズムは本当に理論的価値しか持たないのか？」という疑問に向き合い，そして典型的な予想を裏切るポジティブな結果を提示します．

我々は，頂点被覆問題を例に取り，今まで理論的な価値のみが重視されてきた数々の branch and reduce テクニックを徹底的に盛り込んだ実装を作成しました．そして，様々な現実のインスタンスを用い，branch and cut に基づく CPLEX や branch and bound に基づく MCS アルゴリズム等との比較を行いました．

結果は非常に興味深いもので，インスタンスの種別による得意不得意はあるものの，多くのインスタンスで branch and reduce によるアルゴリズムは（全く cut を用いないにも関わらず）branch and cut に匹敵する性能を達成しました．特に，ソーシャルネットワークやウェブグラフ等の大規模疎グラフにおいては，branch and reduce に基づくアルゴリズムが最も良い性能を示しました．数千万辺・一億辺規模のソーシャルネットワークの最小頂点被覆も厳密に求めることに成功しました．

また，今回の実装は branch and reduce に基づいているため，他の手法と違い，実用上高速なだけでなく理論的に計算量の証明ができることも面白い点です．O*(1.2210^n) 時間で動作することが証明できる他，最良優先探索と組み合わせた場合は O(m 4^k + m√n) 時間で動作することも証明できます（k は integrality gap）．

関連研究・感想など

アルゴリズム研究における理論と実性能の乖離を問題視している研究者は少なくありませんが，その問題に実際に取り組んでいる研究者は残念ながらかなり少ないです．この問題に正面から取り組み成果を挙げているのが，Microsoft Research でお世話になっていた Andrew Goldberg 先生達です．交通ネットワークにおける最短経路クエリのヒューリスティクスを理論的に解析する枠組み，コンピュータビジョン系のインスタンスに特化した最大流アルゴリズムの理論的解析など，とても面白い研究をなさっているので，興味がある方はそちらも是非見てみて下さい．