Back to search

University of Waterloo

Randomization and Restart Strategies

Abstract

dc:description.abstract

The runtime for solving constraint satisfaction problems (CSP) and propositional satisfiability problems (SAT) using systematic backtracking search has been shown to exhibit great variability. Randomization and restarts is an effective technique for reducing such variability to achieve better expected performance. Several restart strategies have been proposed and studied in previous work and show differing degrees of empirical effectiveness. <br /><br /> The first topic in this thesis is the extension of analytical results on restart strategies through the introduction of physically based assumptions. In particular, we study the performance of two of the restart strategies on Pareto runtime distributions. We show that the geometric strategy provably removes heavy tail. We also examine several factors that arise during implementation and their effects on existing restart strategies. <br /><br /> The second topic concerns the development of a new hybrid restart strategy in a realistic problem setting. Our work adapts the existing general approach on dynamic strategy but implements more sophisticated machine learning techniques. The resulting hybrid strategy shows superior performance compared to existing static strategies and an improved robustness.

Degree

thesis:*
Grantor dc:publisher
University of Waterloo
Year dc:date.issued
2006

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Wu, Huayue

Subjects

dc:subject × 5

Rights

dc:rights
Statement dc:rights
  • Copyright: 2006, Wu, Huayue. All rights reserved.
Language dc:language.iso
en

Identifiers

dc:identifier.*
Handle dc:identifier.uri
http://hdl.handle.net/10012/2923

Chain of custody

source
Harvested from
University of Waterloo
Base URL
dspacemainprd01.lib.uwaterloo.ca/server/oai/request
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
citation

Wu, Huayue. Randomization and Restart Strategies. University of Waterloo, 2006. http://hdl.handle.net/10012/2923