Boosting complete techniques thanks to local search methods

In this paper, an efficient heuristic allowing one to localize inconsistent kernels in propositional knowledge‐bases is described. Then, it is shown that local search techniques can boost the performance of logically complete methods for SAT. More precisely, local search techniques can be used to gu...

Full description

Saved in:
Bibliographic Details
Published in:Annals of mathematics and artificial intelligence 1998-01, Vol.22 (3-4), p.319-331
Main Authors: Mazure, Bertrand, Saïs, Lakhdar, Grégoire, Éric
Format: Article
Language:English
Subjects:
Search methods
Citations: Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
cited_by cdi_FETCH-LOGICAL-c229t-91544e6a44ad2c240e7491dc9585ab39e61dfd2212c24acd6a653c5499ef1f6f3
cites
container_end_page 331
container_issue 3-4
container_start_page 319
container_title Annals of mathematics and artificial intelligence
container_volume 22
creator Mazure, Bertrand
Saïs, Lakhdar
Grégoire, Éric
description In this paper, an efficient heuristic allowing one to localize inconsistent kernels in propositional knowledge‐bases is described. Then, it is shown that local search techniques can boost the performance of logically complete methods for SAT. More precisely, local search techniques can be used to guide the branching strategy of logically complete techniques like Davis and Putnam's one, giving rise to significant performance improvements, in particular when addressing locally inconsistent problems. Moreover, this approach appears very competitive in the context of consistent SAT instances, too.
doi_str_mv 10.1023/A:1018999721141
format article
fullrecord <record><control><sourceid>proquest</sourceid><recordid>TN_cdi_proquest_journals_2918193313</recordid><sourceformat>XML</sourceformat><sourcesystem>PC</sourcesystem><sourcerecordid>2918193313</sourcerecordid><originalsourceid>FETCH-LOGICAL-c229t-91544e6a44ad2c240e7491dc9585ab39e61dfd2212c24acd6a653c5499ef1f6f3</originalsourceid><addsrcrecordid>eNotjktLAzEUhYMoWKtrtwHXo7k3j5mrq1rqAwpudF1icsdpnU7qJP3_tujqO3DgO0eIa1C3oFDfze5BQUNENQIYOBETsLWualOr00NWgBUao8_FRc4bpRS5xk3Ew2NKuayHLxnSdtdzYVk4dMP6Z89Zls4P3wck2afge5nZj6GTWy5divlSnLW-z3z1z6n4eFq8z1-q5dvz63y2rAIilYrAGsPOG-MjBjSKa0MQA9nG-k9N7CC2ERGOpQ_ReWd1sIaIW2hdq6fi5s-7G9PxVllt0n4cDpMrJGiAtAatfwEvOklw</addsrcrecordid><sourcetype>Aggregation Database</sourcetype><iscdi>true</iscdi><recordtype>article</recordtype><pqid>2918193313</pqid></control><display><type>article</type><title>Boosting complete techniques thanks to local search methods</title><source>Springer Nature</source><creator>Mazure, Bertrand ; Saïs, Lakhdar ; Grégoire, Éric</creator><creatorcontrib>Mazure, Bertrand ; Saïs, Lakhdar ; Grégoire, Éric</creatorcontrib><description>In this paper, an efficient heuristic allowing one to localize inconsistent kernels in propositional knowledge‐bases is described. Then, it is shown that local search techniques can boost the performance of logically complete methods for SAT. More precisely, local search techniques can be used to guide the branching strategy of logically complete techniques like Davis and Putnam's one, giving rise to significant performance improvements, in particular when addressing locally inconsistent problems. Moreover, this approach appears very competitive in the context of consistent SAT instances, too.</description><identifier>ISSN: 1012-2443</identifier><identifier>EISSN: 1573-7470</identifier><identifier>DOI: 10.1023/A:1018999721141</identifier><language>eng</language><publisher>Dordrecht: Springer Nature B.V</publisher><subject>Search methods</subject><ispartof>Annals of mathematics and artificial intelligence, 1998-01, Vol.22 (3-4), p.319-331</ispartof><rights>Kluwer Academic Publishers 1998.</rights><lds50>peer_reviewed</lds50><woscitedreferencessubscribed>false</woscitedreferencessubscribed><citedby>FETCH-LOGICAL-c229t-91544e6a44ad2c240e7491dc9585ab39e61dfd2212c24acd6a653c5499ef1f6f3</citedby></display><links><openurl>$$Topenurl_article</openurl><openurlfulltext>$$Topenurlfull_article</openurlfulltext><thumbnail>$$Tsyndetics_thumb_exl</thumbnail><link.rule.ids>314,777,781,27905,27906</link.rule.ids></links><search><creatorcontrib>Mazure, Bertrand</creatorcontrib><creatorcontrib>Saïs, Lakhdar</creatorcontrib><creatorcontrib>Grégoire, Éric</creatorcontrib><title>Boosting complete techniques thanks to local search methods</title><title>Annals of mathematics and artificial intelligence</title><description>In this paper, an efficient heuristic allowing one to localize inconsistent kernels in propositional knowledge‐bases is described. Then, it is shown that local search techniques can boost the performance of logically complete methods for SAT. More precisely, local search techniques can be used to guide the branching strategy of logically complete techniques like Davis and Putnam's one, giving rise to significant performance improvements, in particular when addressing locally inconsistent problems. Moreover, this approach appears very competitive in the context of consistent SAT instances, too.</description><subject>Search methods</subject><issn>1012-2443</issn><issn>1573-7470</issn><fulltext>true</fulltext><rsrctype>article</rsrctype><creationdate>1998</creationdate><recordtype>article</recordtype><recordid>eNotjktLAzEUhYMoWKtrtwHXo7k3j5mrq1rqAwpudF1icsdpnU7qJP3_tujqO3DgO0eIa1C3oFDfze5BQUNENQIYOBETsLWualOr00NWgBUao8_FRc4bpRS5xk3Ew2NKuayHLxnSdtdzYVk4dMP6Z89Zls4P3wck2afge5nZj6GTWy5divlSnLW-z3z1z6n4eFq8z1-q5dvz63y2rAIilYrAGsPOG-MjBjSKa0MQA9nG-k9N7CC2ERGOpQ_ReWd1sIaIW2hdq6fi5s-7G9PxVllt0n4cDpMrJGiAtAatfwEvOklw</recordid><startdate>19980101</startdate><enddate>19980101</enddate><creator>Mazure, Bertrand</creator><creator>Saïs, Lakhdar</creator><creator>Grégoire, Éric</creator><general>Springer Nature B.V</general><scope>8FE</scope><scope>8FG</scope><scope>ABJCF</scope><scope>AFKRA</scope><scope>ARAPS</scope><scope>AZQEC</scope><scope>BENPR</scope><scope>BGLVJ</scope><scope>CCPQU</scope><scope>DWQXO</scope><scope>GNUQQ</scope><scope>HCIFZ</scope><scope>JQ2</scope><scope>K7-</scope><scope>L6V</scope><scope>M7S</scope><scope>P5Z</scope><scope>P62</scope><scope>PQEST</scope><scope>PQQKQ</scope><scope>PQUKI</scope><scope>PTHSS</scope></search><sort><creationdate>19980101</creationdate><title>Boosting complete techniques thanks to local search methods</title><author>Mazure, Bertrand ; Saïs, Lakhdar ; Grégoire, Éric</author></sort><facets><frbrtype>5</frbrtype><frbrgroupid>cdi_FETCH-LOGICAL-c229t-91544e6a44ad2c240e7491dc9585ab39e61dfd2212c24acd6a653c5499ef1f6f3</frbrgroupid><rsrctype>articles</rsrctype><prefilter>articles</prefilter><language>eng</language><creationdate>1998</creationdate><topic>Search methods</topic><toplevel>peer_reviewed</toplevel><toplevel>online_resources</toplevel><creatorcontrib>Mazure, Bertrand</creatorcontrib><creatorcontrib>Saïs, Lakhdar</creatorcontrib><creatorcontrib>Grégoire, Éric</creatorcontrib><collection>ProQuest SciTech Collection</collection><collection>ProQuest Technology Collection</collection><collection>Materials Science &amp; Engineering Collection</collection><collection>ProQuest Central</collection><collection>Advanced Technologies &amp; Aerospace Collection</collection><collection>ProQuest Central Essentials</collection><collection>AUTh Library subscriptions: ProQuest Central</collection><collection>Technology Collection</collection><collection>ProQuest One Community College</collection><collection>ProQuest Central</collection><collection>ProQuest Central Student</collection><collection>SciTech Premium Collection</collection><collection>ProQuest Computer Science Collection</collection><collection>Computer science database</collection><collection>ProQuest Engineering Collection</collection><collection>Engineering Database</collection><collection>ProQuest advanced technologies &amp; aerospace journals</collection><collection>ProQuest Advanced Technologies &amp; Aerospace Collection</collection><collection>ProQuest One Academic Eastern Edition (DO NOT USE)</collection><collection>ProQuest One Academic</collection><collection>ProQuest One Academic UKI Edition</collection><collection>Engineering collection</collection><jtitle>Annals of mathematics and artificial intelligence</jtitle></facets><delivery><delcategory>Remote Search Resource</delcategory><fulltext>fulltext</fulltext></delivery><addata><au>Mazure, Bertrand</au><au>Saïs, Lakhdar</au><au>Grégoire, Éric</au><format>journal</format><genre>article</genre><ristype>JOUR</ristype><atitle>Boosting complete techniques thanks to local search methods</atitle><jtitle>Annals of mathematics and artificial intelligence</jtitle><date>1998-01-01</date><risdate>1998</risdate><volume>22</volume><issue>3-4</issue><spage>319</spage><epage>331</epage><pages>319-331</pages><issn>1012-2443</issn><eissn>1573-7470</eissn><abstract>In this paper, an efficient heuristic allowing one to localize inconsistent kernels in propositional knowledge‐bases is described. Then, it is shown that local search techniques can boost the performance of logically complete methods for SAT. More precisely, local search techniques can be used to guide the branching strategy of logically complete techniques like Davis and Putnam's one, giving rise to significant performance improvements, in particular when addressing locally inconsistent problems. Moreover, this approach appears very competitive in the context of consistent SAT instances, too.</abstract><cop>Dordrecht</cop><pub>Springer Nature B.V</pub><doi>10.1023/A:1018999721141</doi><tpages>13</tpages></addata></record>
fulltext fulltext
identifier ISSN: 1012-2443
ispartof Annals of mathematics and artificial intelligence, 1998-01, Vol.22 (3-4), p.319-331
issn 1012-2443
1573-7470
language eng
recordid cdi_proquest_journals_2918193313
source Springer Nature
subjects Search methods
title Boosting complete techniques thanks to local search methods
url http://sfxeu10.hosted.exlibrisgroup.com/loughborough?ctx_ver=Z39.88-2004&ctx_enc=info:ofi/enc:UTF-8&ctx_tim=2025-01-17T17%3A02%3A46IST&url_ver=Z39.88-2004&url_ctx_fmt=infofi/fmt:kev:mtx:ctx&rfr_id=info:sid/primo.exlibrisgroup.com:primo3-Article-proquest&rft_val_fmt=info:ofi/fmt:kev:mtx:journal&rft.genre=article&rft.atitle=Boosting%20complete%20techniques%20thanks%20to%20local%20search%20methods&rft.jtitle=Annals%20of%20mathematics%20and%20artificial%20intelligence&rft.au=Mazure,%20Bertrand&rft.date=1998-01-01&rft.volume=22&rft.issue=3-4&rft.spage=319&rft.epage=331&rft.pages=319-331&rft.issn=1012-2443&rft.eissn=1573-7470&rft_id=info:doi/10.1023/A:1018999721141&rft_dat=%3Cproquest%3E2918193313%3C/proquest%3E%3Cgrp_id%3Ecdi_FETCH-LOGICAL-c229t-91544e6a44ad2c240e7491dc9585ab39e61dfd2212c24acd6a653c5499ef1f6f3%3C/grp_id%3E%3Coa%3E%3C/oa%3E%3Curl%3E%3C/url%3E&rft_id=info:oai/&rft_pqid=2918193313&rft_id=info:pmid/&rfr_iscdi=true