Neighbourhood Clause Weight Redistribution in Local Search for SAT
Speaker: Abdelraouf Ishtaiwi, Griffith University
When: 2005-10-24 13:00:00
Venue: N54 2.02 Nathan campus Griffith University
Host: (seminar host unavailable)
Abstract:Many problems in Artificial Intelligence (AI) and computer science
can be formulated as constraint-satisfaction problems (CSPs) that
include computer vision, scheduling, temporal reasoning, graph
colouring, planning and the satisfiability problems. The constraint
satisfaction paradigm provides a simple, but expressively rich
methodology to represent complex relationships among objects in the
world, and such relationships can then be exploited in finding
solutions efficiently. This has been one of the most attractive
research fields for the last 3 decades.
The constraint satisfaction problems require clever search methods
to solve them. Broadly speaking, there are two classes of methods
being investigated for these problems: systematic search and
stochastic local search (SLS). The focus of this study is to
investigate the state-of-the-arts algorithms used for the Stochastic
Local Search. The SLS methods can be classified as restart
strategies; stochastic strategies; memory strategies; and constraint
weighting strategies. This thesis will further focus on constraint
weighting algorithms. Motivated by the recent successes of a clause
weighting algorithm, PAWS and hybrid methods R+AdaptNovelty, we will
examine the use of parameters in these algorithms, and explore novel
approaches to make further improvements. We will also extend the
work on local search algorithms to include MAX-SAT problems (over
constrained problems) as many real world problems are often
overconstrained.
In the first chapter we elaborate on the systematic and local search
techniques by showing the similarities and the differences between
systematic search and stochastic local search (SLS) methods and
between the different variants of these two methods. Then, we
identify some limitations and drawbacks of the state-of-the-art
local search techniques such as PAWS, SAPS, AdaptNovelty+ and
RSAPS. Chapter 3 elaborates on the research questions this thesis
will be addressing and a tentative table for various tasks will be
proposed. Chapter 4 describes the preliminary results, DDFW.
Biography:(biography unavailable)
Type: Ph.D confirmation
Contact:(seminar host unavailable), seminar host (n.dunstan@griffith.edu.au)
or Guido Governatori (ITEE seminar co-ordinator)
(guido@itee.uq.edu.au)