SODA

Constraint satisfaction by local search

Bohlin, Markus (2002) Constraint satisfaction by local search. [SICS Report]

[img]
Preview
PDF
826Kb
[img]Postscript
244Kb

Abstract

The constraint satisfaction problem and its derivate, the propositional satisfiability problem (SAT), are fundamental problems in computing theory and mathematical logic. SAT was the first proved NP-complete problem, and although complete algorithms have been dominating the constraint satisfaction field, incomplete approaches based on local search has been successful the last ten years. In this report we give a general framework for constraint satisfaction using local search as well as an different techniques to improve this basic local search framework. We also give an overview of algorithms for problems of constraint satisfaction and optimization using heuristics, and discuss hybrid methods that combine complete methods for constraint satisfaction with local search techniques.

Item Type:SICS Report
Uncontrolled Keywords:Local Search, Heuristics, Constraints, Satisfiability
ID Code:2258
Deposited By:Vicki Carleson
Deposited On:29 Oct 2007
Last Modified:18 Nov 2009 16:03

Repository Staff Only: item control page