Show simple item record

dc.contributor.convenorManuela M. Veloso
dc.contributor.authorPham, Duc Nghia
dc.contributor.authorThornton, John
dc.contributor.authorSattar, Abdul
dc.contributor.editorVeloso, MM
dc.date.accessioned2017-12-05T00:20:24Z
dc.date.available2017-12-05T00:20:24Z
dc.date.issued2007
dc.date.modified2009-05-29T07:10:01Z
dc.identifier.issn1045-0823
dc.identifier.refurihttp://www.ijcai-07.org/
dc.identifier.urihttp://hdl.handle.net/10072/18331
dc.description.abstractLocal search procedures for solving satisfiability problems have attracted considerable attention since the development of GSAT in 1992. However, recent work indicates that for many real-world problems, complete search methods have the advantage, because modern heuristics are able to effectively exploit problem structure. Indeed, to develop a local search technique that can effectively deal with variable dependencies has been an open challenge since 1997. In this paper we show that local search techniques can effectively exploit information about problem structure producing significant improvements in performance on structured problem instances. Building on the earlier work of Ostrowski et al. we describe how information about variable dependencies can be built into a local search, so that only independent variables are considered for flipping. The cost effect of a flip is then dynamically calculated using a dependency lattice that models dependent variables using gates (specifically and, or and equivalence gates). The experimental study on hard structured benchmark problems demonstrates that our new approach significantly outperforms the previously reported best local search techniques.
dc.description.peerreviewedYes
dc.description.publicationstatusYes
dc.languageEnglish
dc.language.isoeng
dc.publisherSpringer
dc.publisher.placeMenlo Park, California
dc.publisher.urihttps://www.ijcai.org/Abstract/07/380
dc.relation.ispartofstudentpublicationN
dc.relation.ispartofconferencename20th International Joint Conference on Artificial Intelligence
dc.relation.ispartofconferencetitle20TH INTERNATIONAL JOINT CONFERENCE ON ARTIFICIAL INTELLIGENCE
dc.relation.ispartofdatefrom2007-01-06
dc.relation.ispartofdateto2007-01-12
dc.relation.ispartoflocationHyderabad, INDIA
dc.relation.ispartofpagefrom2359
dc.relation.ispartofpagefrom6 pages
dc.relation.ispartofpageto2364
dc.relation.ispartofpageto6 pages
dc.rights.retentionY
dc.subject.fieldofresearchcode280213
dc.titleBuilding Structure into Local Search for SAT
dc.typeConference output
dc.type.descriptionE1 - Conferences
dc.type.codeE - Conference Publications
dc.description.versionVersion of Record (VoR)
gro.facultyGriffith Sciences, School of Information and Communication Technology
gro.rights.copyright© 2007 International Joint Conference on Artificial Intelligence. The attached file is reproduced here in accordance with the copyright policy of the publisher. Please refer to the Conference's website for access to the definitive, published version.
gro.date.issued2007
gro.hasfulltextFull Text
gro.griffith.authorSattar, Abdul


Files in this item

This item appears in the following Collection(s)

  • Conference outputs
    Contains papers delivered by Griffith authors at national and international conferences.

Show simple item record