کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
376775 658307 2016 19 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Learning general constraints in CSP
ترجمه فارسی عنوان
یادگیری محدودیت های عمومی در CSP
کلمات کلیدی
حل محدودیت ها؛ قواعد استنتاج
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر هوش مصنوعی
چکیده انگلیسی

We present a new learning scheme for solvers of the Constraint Satisfaction Problem (CSP), which is based on learning (general) constraints rather than the generalized no-goods or signed-clauses that were used in the past. The new scheme is integrated in a conflict-analysis algorithm reminiscent of a modern systematic propositional satisfiability (SAT) solver: it traverses the conflict graph backwards and gradually builds an asserting conflict constraint. This construction is based on new inference rules that are tailored for various pairs of constraints types, e.g., x≤y1+k1x≤y1+k1 and x≥y2+k2x≥y2+k2, or y1≤xy1≤x and [x,y2]⊈[a,b][x,y2]⊈[a,b]. The learned constraint is stronger than what can be learned via signed resolution. Our experiments show that our solver HCSP backtracks orders of magnitude less than other state-of-the-art solvers, and is overall on par with the winner of this year's MiniZinc challenge.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Artificial Intelligence - Volume 238, September 2016, Pages 135–153
نویسندگان
, ,