Skip to content

Analysis and extension of the Inc* on the satisfiability testing problem

Research output: Chapter in Book/Report/Conference proceedingChapter (peer-reviewed)peer-review

Inc (star) is a general algorithm that can be used in conjunction with any local search heuristic and that has the potential to substantially improve the overall performance of the heuristic. The general idea of the algorithm is the following. Rather than attempting to directly solve a difficult problem, the algorithm dynamically chooses a smaller instance of the problem, and then increases the size of the instance only after the previous simplified instances have been solved, until the full size of the problem is reached. Genetic programming is used to discover new strategies for Inc*. Preliminary experiments on the satisfiability problem (SAT) problem have shown that Inc* is a competitive approach. In this paper we enhance Inc* and we experimentally test it on larger set of benchmarks, including big instances of SAT. Furthermore, we provide an analysis of the algorithm's behaviour.
Original languageEnglish
Title of host publicationEvolutionary Computation, 2008. CEC 2008. (IEEE World Congress on Computational Intelligence). IEEE Congress on
Place of PublicationHong Kong
PublisherIEEE
Pages3342-3349
Number of pages8
ISBN (Print)9781424418220
Publication statusPublished - Jun 2008
Event2008 IEEE World Congress on Computational Intelligence - Hong Kong
Duration: 1 Jun 20086 Jun 2008

Conference

Conference2008 IEEE World Congress on Computational Intelligence
Period1/06/086/06/08

Documents

Related information

Relations Get citation (various referencing formats)

ID: 79959