小特集 10. 半整数緩和とその応用

電子情報通信学会 - IEICE会誌 試し読みサイト
Vol.101 No.3 (2018/3) 目次へ

前の記事へ次の記事へ


グラフアルゴリズムの最先端

小特集 10.

半整数緩和とその応用

Half-integral Relaxation and Its Applications

岩田陽一

岩田陽一 国立情報学研究所情報学プリンシプル研究系

Yoichi IWATA, Nonmember (Principles of Informatics Research Division, National Institute of Informatics, Tokyo, 101-8430 Japan).

電子情報通信学会誌 Vol.101 No.3 pp.284-287 2018年3月

©電子情報通信学会2018

abstract

 NP困難問題の整数制約を緩めたLP緩和は,近似計算や分枝限定法などで広く用いられている.問題によっては,最適緩和解が整数値のほかに0.5のみを持つ場合があり,そのような緩和は半整数緩和と呼ばれる.本稿では,半整数緩和の持つ良い性質を解説し,パラメータ化計算量などの理論研究への応用を紹介する.また,これらの理論研究がアルゴリズムの実性能の改善へつながることを紹介する.

キーワード:LP緩和,劣モジュラ性,分枝限定法,パラメータ化計算量

1.ま え が き

 整数計画問題(IP)の整数制約を取り除いた問題は線形計画緩和(LP緩和)と呼ばれ,幅広い応用を持つ.例えば,緩和解を適切に丸めることで,様々な近似度保証付きのアルゴリズムが得られており,また,LP緩和を解くことで得られた最適値の下界(若しくは上界)を用いて枝刈り探索を行う分枝限定法は整数計画ソルバなどで活用されている.LP緩和の中には,最適緩和解が任意の有理数値ではなく,{0,0.5,1} のみを取るような場合がある.このような緩和は「半整数緩和」と呼ばれる.本稿では,半整数緩和が以下のような良い性質を持つことを解説し,それを活用して理論的な計算量並びに実性能の改善が得られることを紹介する.

 (1) 半整数緩和を解く効率的な組合せ的アルゴリズムが存在する.分枝限定法等では繰り返し緩和問題を解く必要があるが,単体法などのLPに対する汎用解法の代わりにこれを用いることで,高速化ができる.

 (2) 「永続性(Persistency)」と呼ばれる性質を持つ.これは最適緩和解で整数値を取った変数(の一部)は,最適整数解でも同じ値を取るという性質である.この性質は分枝限定法の効率化や前処理に活用することができる.

 (3) 多項式時間で解ける様々な離散最適化問題が「劣モジュラ関数」の最小化と捉えることができるが,劣モジュラ関数のmath次元への一般化である「math劣モジュラ関数」の最小化として半整数緩和を捉えることができる.この解釈は,どのような問題が半整数緩和を持つのかの理解に役立ち,また,math劣モジュラ性から永続性を簡単に導くことができる.

 以下では,頂点被覆問題と多分割カット問題という二つの古典的NP困難問題を例に用いて解説を進める.


続きを読みたい方は、以下のリンクより電子情報通信学会の学会誌の購読もしくは学会に入会登録することで読めるようになります。 また、会員になると豊富な豪華特典が付いてきます。


続きを読む(PDF)   バックナンバーを購入する    入会登録


  

電信情報通信学会 - IEICE会誌はモバイルでお読みいただけます。

電子情報通信学会誌 会誌アプリのお知らせ

電信情報通信学会 - IEICE会誌アプリをダウンロード

  Google Play で手に入れよう

本サイトでは会誌記事の一部を試し読み用として提供しています。