Constraint satisfaction by local search

• 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.

Ämnesord

NATURVETENSKAP  -- Data- och informationsvetenskap (hsv//swe)

NATURAL SCIENCES  -- Computer and Information Sciences (hsv//eng)

Nyckelord

Local Search

Heuristics

Constraints

Satisfiability

Publikations- och innehållstyp

vet (ämneskategori)

rap (ämneskategori)