Modulo計算に基づく基数制約のCNF符号化方式の提案と評価

DOI HANDLE オープンアクセス
  • 小川 徹
    九州大学大学院システム情報科学府情報学専攻 : 修士課程
  • 劉 洋洋
    九州大学大学院システム情報科学府情報学専攻 : 博士後期課程
  • 長谷川 隆三
    九州大学大学院システム情報科学研究院情報学部門
  • 越村 三幸
    九州大学大学院システム情報科学研究院情報学部門
  • 藤田 博
    九州大学大学院システム情報科学研究院情報学部門

書誌事項

タイトル別名
  • Modulo Based CNF Encoding of Cardinality Constraints and Its Evaluation

この論文をさがす

抄録

Totalizer (TO) proposed by Bailleux et al. and Half Sort (HS) proposed by Asin et al. are typical CNF encoding methods of cardinality constraint. The former is based on unary adder, while the latter is based on odd-even merge. Although TO is inferior to HS interms of the number of clauses, TO is superior to HS in terms of the number of variables. We propose a new method called Modulo Totalizer (MTO) to overcome the disadvantage of TO. As an application, we have developed a partial MaxSAT solver with MTO. Preliminary experimental results show that our MTO based MaxSAT solver is comparable to or surpass the conventional TO based maxsat solvers.

収録刊行物

関連プロジェクト

もっと見る

キーワード

詳細情報 詳細情報について

  • CRID
    1390290699814852352
  • NII論文ID
    120005306729
  • NII書誌ID
    AN10569524
  • DOI
    10.15017/26858
  • ISSN
    21880891
    13423819
  • HANDLE
    2324/26858
  • 本文言語コード
    ja
  • データソース種別
    • JaLC
    • IRDB
    • CiNii Articles
    • KAKEN
  • 抄録ライセンスフラグ
    使用可

問題の指摘

ページトップへ