Multi-MaxSAT:ラグランジュ分解・調整法を用いたWeighted Max-SAT問題の解法

黒田 陽之  平山 勝敏  

誌名
電子情報通信学会論文誌 D   Vol.J92-D   No.1   pp.51-60
発行日: 2009/01/01
Online ISSN: 1881-0225
DOI: 
Print ISSN: 1880-4535
論文種別: 論文
専門分野: 分散協調とエージェント
キーワード: 
Weighted Max-SAT,  疎結合な問題,  ラグランジュ分解,  

本文: PDF(318.7KB)>>
論文を購入




あらまし: 
Weighted Max-SAT問題とは,SAT問題における各節に重みを与え,満足で きない節の重み和を最小にするような論理変数への真偽値の割当を求める最 適化問題である.SAT問題に関する研究が近年劇的に進展したことを受けて,SAT問題の最適化版であるWeighted Max-SAT問題への関心も最近高まりつつある. 本論文では,複数の部分問題(節集合)が互いに緩く結合することにより構成 されるWeighted Max-SAT問題に対して特に有効な新しい解法としてMulti-MaxSATを提案する.評価実験によれば,部分問題間で共有される変数の 数が比較的少ないとき,Multi-MaxSATは,最新の代表的な厳密解法や発見的解法よりも処理時間や発見できる解の質の面で優れている.