SAT変換に基づく制約ソルバーとその性能評価
本論文では，SAT変換に基づく制約ソルバーであるSugarの概要とその性能評価結果について述べる．Sugarは，制約充足問題(CSP)，制約最適化問題(COP)および最大制約充足問題(Max-CSP)を，命題論理の充足可能性判定問題(SAT問題) に変換し，MiniSat等の高速なSATソルバーを用いて求解を行うシステムである．SAT変換には，order encodingと名付けた新しい方法を用いており，従来広く用いられているdirect encodingやsupport encodingよりも，多くの問題に対して高速な求解が可能である．本論文では，order encodingの説明を含めたSugarの概要について述べた後，2008年に開催された第3回国際CSPソルバー競技会およびMax-CSPソルバー競技会での結果を基にSugarの性能評価結果を報告する．なお，Sugarは同競技会の10
SAT/SMTソルバの仕組み
NLP コロキウム https://nlp-colloquium-jp.github.io/ で発表した際のスライドです。 論文: https://arxiv.org/abs/2205.01954 GitHub: https://github.com/joisino/wordtour 概要 単語埋め込みは現代の自然言語処理の中核技術のひとつで、文書分類や類似度測定をはじめとして、さまざまな場面で使用されていることは知っての通りです。しかし、ふつう埋め込み先は何百という高次元であり、使用する時には多くの時間やメモリを消費するうえに、高次元埋め込みを視覚的に表現できないため解釈が難しいことが問題です。そこで本研究では、【一次元】の単語埋め込みを教師なしで得る方法を提案します。とはいえ、単語のあらゆる側面を一次元で捉えるのは不可能であるので、本研究ではまず単語埋め込みが満たすべき性質を健全性と完
制約充足問題として最強のボジョレーを求める - Debug me
ちゃお......舞いおりん......† 今回は#ajiting Advent Calendar 2015の8日目ということでVOYAGE GROUPの多目的スペースAjitoにむりやり絡めて話そうと思います。 はじめに 先月の話になってしまいますが、今年もボジョレーヌーボーが解禁されました。 解禁日はAjitoでも終業後に飲んでる人がちらほらいたそうです (私はその日体調悪くて家に直帰しました...†) さてボジョレーヌーボーといえば、毎年公開されるキャッチコピーが話題ですね。Wikipediaに年ごとのものが載っているのでちょっと挙げてみますとこんな感じです。 1995年「ここ数年で一番出来が良い」 1996年「10年に1度の逸品」 1997年「まろやかで濃厚。近年まれにみるワインの出来で過去10年間でトップクラス」 1998年「例年のようにおいしく、フレッシュな口当たり」 1999
Introduction to Max-SAT and Max-SAT Evaluation
This document provides an introduction to Max-SAT and Max-SAT evaluation. It discusses SAT and related problems like Max-SAT and pseudo-boolean optimization. The author shares their experience submitting their solver "toysat" to the Max-SAT evaluation in 2013. For Max-SAT 2014, the author plans to submit improved versions of SCIP, FibreSCIP, and toysat. The document concludes by discussing interac
Sugar: a SAT-based Constraint Solver
Sugar is a SAT-based Constraint Solver. Constraint Satisfaction Problem (CSP) is encoded to a Boolean CNF formula, and it is solved by an external SAT solver. Sugar also can solve Constraint Optimization Problems (COP) and Max-CSP. Sugar is an award winning solver of global constraint categories at the International CSP Solver Competitions in 2008 and 2009, and of four categories at the 2008 Inter
<hr> <!– <img width=“20%” src=“banbara.png”><br> –> <font size=“-1”> <table> <tr> <td><img width=“150px” src=“soh.png”></td> <td class=“button2”><a href=“http://www.edu.kobe-u.ac.jp/istc-tamlab/”>Tamura Lab.</a><a href=“http://kix.istc.kobe-u.ac.jp/~soh/jp/”>T. Soh</a></td> </tr> </table> </font> <img src=“http://cgi.center.kobe-u.ac.jp:8000/cgi-bin/Count.cgi?df=svc00652-cspsat.dat%7Cdd=C” align=a
A Prolog SAT Solver
A Pearl on SAT and SMT Solving in Prolog The solver is (SICStus) available as sat_solver.pl. Some code for static variable ordering is also included, static_var_order.pl. The benchmarks from the paper are also included, flopsbenchmarks.tar. Please cite satlib.org from where a number of these files come. A version of the solver to produce statistics on timings and assignments is also included, sat_
情報基礎特論: 制約プログラミング入門
CSP Cream Sugar Copris : 2011 6 6 2011 8 22 2012 6 24 2014 5 19 : CSP Cream Sugar Copris 1 2 3 Cream Java OpenOffice.org Calc 4 Sugar SAT Scala : CSP Cream Sugar Copris : CSP Cream Sugar Copris (CSP) (CSP; Constraint Satisfaction Problem) (X, D, C) X: (variable) D: x ∈ X (domain) ( : D(x) = {1, 2, 3}) D(x) C: X (constraint) X v x v(x) ∈ D(x) v (assignment) v C (satisfy) CSP (satisfiable) v (unsatisfia
Vol.28 No.2 (2013/03) SAT ソルバー – 人工知能学会 (The Japanese Society for Artificial Intelligence)
私のブックマーク 私のブックマーク：SAT ソルバー 番原 睦則 (神戸大学 情報基盤センター) 宋 剛秀 (神戸大学 情報基盤センター) 田村 直之 (神戸大学 情報基盤センター) 井上 克巳 (国立情報学研究所) 命題論理の充足可能性判定問題 (SAT) は，与えられた命題論理式の充足可能性を判定する問題であり，最初にNP完全性が証明された問題でもある．SAT は人工知能および計算機工学における最も基本的な問題として，論理合成，システム検証，プランニング問題，スケジューリング問題，制約充足問題，制約最適化問題，定理証明など，さまざまな分野に応用されている．近年，106-107 個の変数をもつ大規模な SAT問題を，非常に高速に解くことが可能な SAT ソルバーが実現され，これらの分野への実用的応用が急速に拡大している． このように，与えられた問題を論理式で表現し SAT ソルバーを用い
1
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
http://www.sci.brooklyn.cuny.edu/~zhou/papers/padl16.pdf
http://www.sci.brooklyn.cuny.edu/~zhou/papers/padl16_slides.pdf
https://www.cs.upc.edu/~oliveras/TDV/dl.pdf
SWI-Prolog -- library(clpb): CLP(B): Constraint Logic Programming over Boolean Variables
Welcome to the ACP | Association for Constraint Programming