No Cover Image

Conference Paper/Proceeding/Abstract 1638 views

Cube and Conquer: Guiding CDCL SAT Solvers by Lookaheads

Marijn J. H Heule, Oliver Kullmann Orcid Logo, Siert Wieringa, Armin Biere

Hardware and Software: Verification and Testing, Volume: 7261, Pages: 50 - 65

Swansea University Author: Oliver Kullmann Orcid Logo

Full text not available from this repository: check for access using links below.

Check full text

DOI (Published version): 10.1007/978-3-642-34188-5_8

Abstract

We present a new SAT approach, called cube-and-conquer, targeted at reducing solving time on hard instances. This two-phase approach partitions a problem into many thousands (or millions) of cubes using lookahead techniques. Afterwards, a conflict-driven solver tackles the problem, using the cubes t...

Full description

Published in: Hardware and Software: Verification and Testing
ISSN: 0302-9743 1611-3349
Published: Heidelberg Springer 2011
Online Access: Check full text

URI: https://cronfa.swan.ac.uk/Record/cronfa8073
first_indexed 2013-11-06T02:44:56Z
last_indexed 2018-02-09T04:36:53Z
id cronfa8073
recordtype SURis
fullrecord <?xml version="1.0"?><rfc1807><datestamp>2015-10-15T10:20:20.4634571</datestamp><bib-version>v2</bib-version><id>8073</id><entry>2012-02-22</entry><title>Cube and Conquer: Guiding CDCL SAT Solvers by Lookaheads</title><swanseaauthors><author><sid>2b410f26f9324d6b06c2b98f67362d05</sid><ORCID>0000-0003-3021-0095</ORCID><firstname>Oliver</firstname><surname>Kullmann</surname><name>Oliver Kullmann</name><active>true</active><ethesisStudent>false</ethesisStudent></author></swanseaauthors><date>2012-02-22</date><deptcode>MACS</deptcode><abstract>We present a new SAT approach, called cube-and-conquer, targeted at reducing solving time on hard instances. This two-phase approach partitions a problem into many thousands (or millions) of cubes using lookahead techniques. Afterwards, a conflict-driven solver tackles the problem, using the cubes to guide the search. On several hard SAT-competition benchmarks, our hybrid approach outperforms both lookahead and conflict-driven solvers. Moreover, because cube-and-conquer is natural to parallelise, it is a competitive alternative for solving SAT problems in parallel. This approach was originally developed for solving hard van-der-Waerden problems, and for these (hard, unsatisfiable) problems the approach is not only very well parallelisable, but outperforms all other (parallel or not) SAT-solvers in terms of total run-time by at least a factor of two.</abstract><type>Conference Paper/Proceeding/Abstract</type><journal>Hardware and Software: Verification and Testing</journal><volume>7261</volume><paginationStart>50</paginationStart><paginationEnd>65</paginationEnd><publisher>Springer</publisher><placeOfPublication>Heidelberg</placeOfPublication><issnPrint>0302-9743</issnPrint><issnElectronic>1611-3349</issnElectronic><keywords/><publishedDay>31</publishedDay><publishedMonth>12</publishedMonth><publishedYear>2011</publishedYear><publishedDate>2011-12-31</publishedDate><doi>10.1007/978-3-642-34188-5_8</doi><url>http://www.cs.swan.ac.uk/~csoliver/papers.html#CuCo2011</url><notes></notes><college>COLLEGE NANME</college><department>Mathematics and Computer Science School</department><CollegeCode>COLLEGE CODE</CollegeCode><DepartmentCode>MACS</DepartmentCode><institution>Swansea University</institution><apcterm/><lastEdited>2015-10-15T10:20:20.4634571</lastEdited><Created>2012-02-22T13:37:06.0000000</Created><path><level id="1">Faculty of Science and Engineering</level><level id="2">School of Mathematics and Computer Science - Computer Science</level></path><authors><author><firstname>Marijn J. H</firstname><surname>Heule</surname><order>1</order></author><author><firstname>Oliver</firstname><surname>Kullmann</surname><orcid>0000-0003-3021-0095</orcid><order>2</order></author><author><firstname>Siert</firstname><surname>Wieringa</surname><order>3</order></author><author><firstname>Armin</firstname><surname>Biere</surname><order>4</order></author></authors><documents/><OutputDurs/></rfc1807>
spelling 2015-10-15T10:20:20.4634571 v2 8073 2012-02-22 Cube and Conquer: Guiding CDCL SAT Solvers by Lookaheads 2b410f26f9324d6b06c2b98f67362d05 0000-0003-3021-0095 Oliver Kullmann Oliver Kullmann true false 2012-02-22 MACS We present a new SAT approach, called cube-and-conquer, targeted at reducing solving time on hard instances. This two-phase approach partitions a problem into many thousands (or millions) of cubes using lookahead techniques. Afterwards, a conflict-driven solver tackles the problem, using the cubes to guide the search. On several hard SAT-competition benchmarks, our hybrid approach outperforms both lookahead and conflict-driven solvers. Moreover, because cube-and-conquer is natural to parallelise, it is a competitive alternative for solving SAT problems in parallel. This approach was originally developed for solving hard van-der-Waerden problems, and for these (hard, unsatisfiable) problems the approach is not only very well parallelisable, but outperforms all other (parallel or not) SAT-solvers in terms of total run-time by at least a factor of two. Conference Paper/Proceeding/Abstract Hardware and Software: Verification and Testing 7261 50 65 Springer Heidelberg 0302-9743 1611-3349 31 12 2011 2011-12-31 10.1007/978-3-642-34188-5_8 http://www.cs.swan.ac.uk/~csoliver/papers.html#CuCo2011 COLLEGE NANME Mathematics and Computer Science School COLLEGE CODE MACS Swansea University 2015-10-15T10:20:20.4634571 2012-02-22T13:37:06.0000000 Faculty of Science and Engineering School of Mathematics and Computer Science - Computer Science Marijn J. H Heule 1 Oliver Kullmann 0000-0003-3021-0095 2 Siert Wieringa 3 Armin Biere 4
title Cube and Conquer: Guiding CDCL SAT Solvers by Lookaheads
spellingShingle Cube and Conquer: Guiding CDCL SAT Solvers by Lookaheads
Oliver Kullmann
title_short Cube and Conquer: Guiding CDCL SAT Solvers by Lookaheads
title_full Cube and Conquer: Guiding CDCL SAT Solvers by Lookaheads
title_fullStr Cube and Conquer: Guiding CDCL SAT Solvers by Lookaheads
title_full_unstemmed Cube and Conquer: Guiding CDCL SAT Solvers by Lookaheads
title_sort Cube and Conquer: Guiding CDCL SAT Solvers by Lookaheads
author_id_str_mv 2b410f26f9324d6b06c2b98f67362d05
author_id_fullname_str_mv 2b410f26f9324d6b06c2b98f67362d05_***_Oliver Kullmann
author Oliver Kullmann
author2 Marijn J. H Heule
Oliver Kullmann
Siert Wieringa
Armin Biere
format Conference Paper/Proceeding/Abstract
container_title Hardware and Software: Verification and Testing
container_volume 7261
container_start_page 50
publishDate 2011
institution Swansea University
issn 0302-9743
1611-3349
doi_str_mv 10.1007/978-3-642-34188-5_8
publisher Springer
college_str Faculty of Science and Engineering
hierarchytype
hierarchy_top_id facultyofscienceandengineering
hierarchy_top_title Faculty of Science and Engineering
hierarchy_parent_id facultyofscienceandengineering
hierarchy_parent_title Faculty of Science and Engineering
department_str School of Mathematics and Computer Science - Computer Science{{{_:::_}}}Faculty of Science and Engineering{{{_:::_}}}School of Mathematics and Computer Science - Computer Science
url http://www.cs.swan.ac.uk/~csoliver/papers.html#CuCo2011
document_store_str 0
active_str 0
description We present a new SAT approach, called cube-and-conquer, targeted at reducing solving time on hard instances. This two-phase approach partitions a problem into many thousands (or millions) of cubes using lookahead techniques. Afterwards, a conflict-driven solver tackles the problem, using the cubes to guide the search. On several hard SAT-competition benchmarks, our hybrid approach outperforms both lookahead and conflict-driven solvers. Moreover, because cube-and-conquer is natural to parallelise, it is a competitive alternative for solving SAT problems in parallel. This approach was originally developed for solving hard van-der-Waerden problems, and for these (hard, unsatisfiable) problems the approach is not only very well parallelisable, but outperforms all other (parallel or not) SAT-solvers in terms of total run-time by at least a factor of two.
published_date 2011-12-31T06:16:14Z
_version_ 1821385083665252352
score 11.047783

Similar Items