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

Mohamed Bader, R. Poli

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

138 Downloads (Pure)


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
PublisherInstitute of Electrical and Electronics Engineers Inc.
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


Conference2008 IEEE World Congress on Computational Intelligence


  • Genetic Programming
  • SAT
  • Combinatorial Optimization


Dive into the research topics of 'Analysis and extension of the Inc* on the satisfiability testing problem'. Together they form a unique fingerprint.

Cite this