Within-problem Learning for Efficient Lower Bound Computation in Max-SAT Solving

There are no files associated with this record.

Title Within-problem Learning for Efficient Lower Bound Computation in Max-SAT Solving
Author Lin, Han; Su, Kaile; Li, Chu-Min
Publication Title Proceedings of the Twenty-Third AAAI Conference on Artificial Intelligence and the Twentieth Innovative
Editor Dieter Fox, Carla P. Gomes
Year Published 2008
Place of publication California, United States
Publisher AAAI Press
Abstract This paper focuses on improving branch-and-bound Max-SAT solvers by speeding up the lower bound computation. We notice that the existing propagation-based computing methods and the resolution-based computing methods, which have been studied intensively, both suffer from several drawbacks. In order to overcome these drawbacks, we propose a new method with a nice property that guarantees the increment of lower bounds. The new method exploits within-problem learning techniques. More specifically, at each branch point in the search-tree, the current node is enabled to inherit inconsistencies from its parent and learn information about effectiveness of the lower bound computing procedure from previous nodes. Furthermore, after branching on a new variable, the inconsistencies may shrink by applying unit propagation to them, and such process increases the probability of getting better lower bounds. We graft the new techniques into maxsatz and the experimental results demonstrate that the new solver outperforms the best state-of-the-art solvers on a wide range of instances including random and structured ones.
Peer Reviewed Yes
Published Yes
Publisher URI http://www.aaai.org/Conferences/AAAI/aaai08.php
Copyright Statement Copyright 2008 AAAI Press. Use hypertext link for access to conference website.
ISBN 9781577353683 (PBK.)
Conference name Twenty-Third AAAI Conference on Artificial Intelligence, AAAI-08
Location Chicago, Illinois, USA
Date From 2008-07-13
Date To 2008-07-17
URI http://hdl.handle.net/10072/24593
Date Accessioned 2009-05-12
Date Available 2009-07-02T06:45:00Z
Language en_AU
Research Centre Institute for Integrated and Intelligent Systems
Faculty Faculty of Science, Environment, Engineering and Technology
Subject Computational Logic and Formal Languages
Publication Type Conference Publications (Full Written Paper - Refereed)
Publication Type Code e1

Brief Record

Griffith University copyright notice