制約充足問題に対する数理計画法を用いたアプローチ

制約充足問題において，扱える制約集合を制限した際の計算量が多項式時間可解かもしくはNP完全であるという予想は二分予想と呼ばれ，理論的に非常に重要な課題であると認識されている．本研究では，この予想を，数理計画法を用いることで解決することを目指す．そのためのステップとして，数理計画法を利用したアルゴリズムを開発することが目標である． 具体的な成果を以下に記す．まず，解を直接求める代わりに，充足可能性保存割当てを求めるアルゴリズムを開発した．充足可能性保存割当ては，解を緩和した概念であり，解そのものよりも扱い易いことが期待される．一方で，このような割当てを逐次的に求めていけば，解を求めることが出来る．そのため，充足可能性保存割当てを求めること自体がNP困難であるので，多面錐により近似することで，効率的なアルゴリズムを開発した．ここで，多面錐により近似することにより，数理計画法の一種である線形計画法のアルゴリズムを用いることが可能となることに注意する．そして，近似がどの程度良いものになるかについての解析を詳細に行い，解が良い性質をもつ場合には極大な近似を与えることに成功した．また，上記のアルゴリズムにより解ける部分クラスを解析し，整数線形不等式系の実行可能性問題に対しては，先行研究の結果を含むクラスが解けることを示した．このことにより，上記のアルゴリズムが広い問題クラスを解くことを明らかにした．さらに，提案したアルゴリズムを，特殊な問題クラスに対して高速化した．提案アルゴリズムにでは線形計画法を解いているが，この際，組合せ的な特徴付けを与えることにより，線形計画法に対する汎用的なアルゴリズムよりも高速に解くアルゴリズムを提案した．

制約充足問題において，扱える制約集合を制限した際の計算量が多項式時間可解かもしくはNP完全であるという予想は二分予想と呼ばれ，理論的に非常に重要な課題であると認識されている．本研究では，この予想を，数理計画法を用いることで解決することを目指す．そのためのステップとして，数理計画法を利用したアルゴリズムを開発することが目標である． 具体的な成果を以下に記す．まず，解を直接求める代わりに，充足可能性保存割当てを求めるアルゴリズムを開発した．充足可能性保存割当ては，解を緩和した概念であり，解そのものよりも扱い易いことが期待される．一方で，このような割当てを逐次的に求めていけば，解を求めることが出来る．そのため，充足可能性保存割当てを求めること自体がNP困難であるので，多面錐により近似することで，効率的なアルゴリズムを開発した．ここで，多面錐により近似することにより，数理計画法の一種である線形計画法のアルゴリズムを用いることが可能となることに注意する．そして，近似がどの程度良いものになるかについての解析を詳細に行い，解が良い性質をもつ場合には極大な近似を与えることに成功した．また，上記のアルゴリズムにより解ける部分クラスを解析し，整数線形不等式系の実行可能性問題に対しては，先行研究の結果を含むクラスが解けることを示した．このことにより，上記のアルゴリズムが広い問題クラスを解くことを明らかにした．さらに，提案したアルゴリズムを，特殊な問題クラスに対して高速化した．提案アルゴリズムにでは線形計画法を解いているが，この際，組合せ的な特徴付けを与えることにより，線形計画法に対する汎用的なアルゴリズムよりも高速に解くアルゴリズムを提案した．