重み付き部分MaxSAT問題における基数制約符号化手法の改良

• 早田 翔

  九州大学大学院システム情報科学府

• 長谷川 隆三

  九州大学大学院システム情報科学研究院

書誌事項

タイトル別名

• Improvement in CNF Encording of Cardinal Constraints for Weighted Partial MaxSAT
• オモミズキ ブブン MaxSAT モンダイ ニ オケル キスウ セイヤク フゴウカ シュホウ ノ カイリョウ

抄録

Weighted Partial MaxSAT(WPMS) is a generalization of Satisfiability problem. Many optimization problems can be reduced to WPMS in polynomial time. So it is important to develop MaxSAT solvers. Cardinality constraints plays important role in solving MaxSAT. In this paper, we propose Weighted Totalizer(WTO) and Partial Encording(PE). WTO is based on Totalizer(TO), and use less variables and clauses than TO. PE is a new encording method, which is optimized for particular WPMS problems. Our experimental results show the effectiveness of these methods.

収録刊行物

• 人工知能学会研究会資料 人工知能基本問題研究会

  人工知能学会研究会資料 人工知能基本問題研究会 97 (0), 14-, 2015-03-18

  一般社団法人 人工知能学会

詳細情報

• CRID: 1390288547259373056
• NII論文ID: 130008061480
• NII論文ID: 40020397804
• NII書誌ID: AA11977943
• DOI: 10.11517/jsaifpai.97.0_14
• ISSN: 24364584
• NDL書誌ID: 026253118
• Web Site: https://ndlsearch.ndl.go.jp/books/R000000004-I026253118
• 本文言語コード: ja
• データソース種別:
  • JaLC
  • NDL
  • CiNii Articles
• 抄録ライセンスフラグ: 使用可