1．ま　え　が　き

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

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

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

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

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