Solution techniques for constraint satisfaction problems: Advanced approaches

I. Miguel, Q. Shen

Research output: Contribution to journalReview articlepeer-review

15 Citations (Scopus)

Abstract

Conventional techniques for the constraint satisfaction problem (CSP) have had considerable success in their applications. However, there are many areas in which the performance of the basic approaches may be improved. These include heuristic ordering of certain tasks performed by the CSP solver, hybrids which combine compatible solution techniques and graph based methods which exploit the structure of the constraint graph representation of a CSP. Also, conventional constraint satisfaction techniques only address problems with hard constraints (i.e. each of which are completely satisfied or completely violated, and all of which must be satisfied by a valid solution). Many real applications require a more flexible approach which relaxes somewhat these rigid requirements. To address these issues various approaches have been developed. This paper attempts a systematic review of them.

Original languageEnglish
Pages (from-to)269-293
Number of pages25
JournalArtificial Intelligence Review
Volume15
Issue number4
DOIs
Publication statusPublished - Jun 2000

Keywords

  • Constraint satisfaction problems
  • Flexible constraint satisfaction
  • Graph-based methods
  • Heuristics
  • Hybrids
  • Ill-defined problems

Fingerprint

Dive into the research topics of 'Solution techniques for constraint satisfaction problems: Advanced approaches'. Together they form a unique fingerprint.

Cite this