並列連続局所探索の研究

ニュース概要

本研究は、対称的な疑似ブール(PB)制約を伴うブール充足可能性問題の解法アプローチとして、並列連続局所探索(CLS)を検討する。n変数のPB充足可能性問題は、n次元超立方体上の微分可能な目的関数を持つ連続最適化問題に緩和される。充足可能なインスタンスについて、この最適化問題の大域的最小化子はSAT問題の充足割り当てに対応する。経験的実験を通じて、以下の新知見を提示する:(i)冗長制約は収束を加速させるのではなく阻害する可能性がある、(ii)CLSはハイブリッド設定での部分ソルバーとして有望であり、部分割り当てを迅速に完成させる、(iii)鞍点密度の高い目的関数により局所探索はソリューション品質(充足度)の安定分布に急速に収束し、追加のソルバーステップは限定的な効果しか得られない。本知見は、現代のアクセラレータハードウェア上のSATに対するCLSの実践的利用に有用である。