کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
419044 681733 2007 14 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Regular-SAT: A many-valued approach to solving combinatorial problems
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
Regular-SAT: A many-valued approach to solving combinatorial problems
چکیده انگلیسی

Regular-SAT is a constraint programming language between CSP and SAT that—by combining many of the good properties of each paradigm—offers a good compromise between performance and expressive power. Its similarity to SAT allows us to define a uniform encoding formalism, to extend existing SAT algorithms to Regular-SAT without incurring excessive overhead in terms of computational cost, and to identify phase transition phenomena in randomly generated instances. On the other hand, Regular-SAT inherits from CSP more compact and natural encodings that maintain more the structure of the original problem. Our experimental results—using a range of benchmark problems—provide evidence that Regular-SAT offers practical computational advantages for solving combinatorial problems.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Applied Mathematics - Volume 155, Issue 12, 15 June 2007, Pages 1613–1626
نویسندگان
, , , , ,