Machine learned heuristics to improve constraint satisfaction

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

2 Citations (Scopus)


Although propagation techniques are very important to solve constraint solving problems, heuristics are still necessary to handle non trivial problems efficiently. General principles may be defined for such heuristics (e.g. first-fail and best-promise), but problems arise in their implementation except for some limited sources of information (e.g. cardinality of variables domain). Other possibly relevant features are ignored due to the difficulty in understanding their interaction and a convenient way of integrating them. In this paper we illustrate such difficulties in a specific problem, determination of protein structure from Nuclear Magnetic Resonance (NMR) data. We show that machine learning techniques can be used to define better heuristics than the use of heuristics based on single features, or even than their combination in simple form (e.g majority vote). The technique is quite general and, with the necessary adaptations, may be applied to many other constraint satisfaction problems.

Original languageEnglish
Title of host publicationAdvances in Artificial Intelligence – SBIA 2004
Subtitle of host publication17th Brazilian Symposium on Artificial Intelligence, Sao Luis, Maranhao, Brazil, September 29-Ocotber 1, 2004. Proceedings
EditorsAna L. C. Bazzan, Sofiane Labidi
Place of PublicationBerlin
Number of pages11
ISBN (Electronic)978-3-540-28645-5
ISBN (Print)978-3-540-23237-7
Publication statusPublished - 2004
EventSBIA: 17th Brazilian Symposium on Artificial Intelligence - São Luís, Maranhão, Brazil
Duration: 29 Sep 20041 Oct 2004

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


CitySão Luís, Maranhão


  • Bioinformatics
  • Constraint programming
  • Machine learning


Dive into the research topics of 'Machine learned heuristics to improve constraint satisfaction'. Together they form a unique fingerprint.

Cite this