Estimating bounds on expected plateau size in maxsat problems

Andrew M. Sutton, Adele E. Howe, L. Darrell Whitley

Research output: Chapter in Book/Report/Conference proceedingConference contribution

5 Scopus citations

Abstract

Stochastic local search algorithms can now successfully solve MAXSAT problems with thousands of variables or more. A key to this success is how effectively the search can navigate and escape plateau regions. Furthermore, the solubility of a problem depends on the size and exit density of plateaus, especially those closest to the optimal solution. In this paper we model the plateau phenomenon as a percolation process on hypercube graphs. We develop two models for estimating bounds on the size of plateaus and prove that one is a lower bound and the other an upper bound on the expected size of plateaus at a given level. The models' accuracy is demonstrated on controlled random hypercube landscapes. We apply the models to MAXSAT through analogy to hypercube graphs and by introducing an approach to estimating, through sampling, a key parameter of the models. Using this approach, we assess the accuracy of our bound estimations on uniform random and structured benchmarks. Surprisingly, we find similar trends in accuracy across random and structured problem instances. Less surprisingly, we find a high accuracy on smaller plateaus with systematic divergence as plateaus increase in size.

Original languageEnglish (US)
Title of host publicationEngineering Stochastic Local Search Algorithms - Designing, Implementing and Analyzing Effective Heuristics - Second International Workshop, SLS 2009, Proceedings
Pages31-45
Number of pages15
DOIs
StatePublished - Nov 4 2009
Event2nd International Workshop on Engineering Stochastic Local Search Algorithms - Designing, Implementing and Analyzing Effective Heuristics, SLS 2009 - Brussels, Belgium
Duration: Sep 3 2009Sep 4 2009

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume5752 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Other

Other2nd International Workshop on Engineering Stochastic Local Search Algorithms - Designing, Implementing and Analyzing Effective Heuristics, SLS 2009
CountryBelgium
CityBrussels
Period9/3/099/4/09

Fingerprint Dive into the research topics of 'Estimating bounds on expected plateau size in maxsat problems'. Together they form a unique fingerprint.

Cite this