Machine learned heuristics to improve constraint satisfaction

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

2 Citations (Scopus)

Abstract

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
PublisherSpringer-Verlag
Pages103-113
Number of pages11
ISBN (Electronic)978-3-540-28645-5
ISBN (Print)978-3-540-23237-7
DOIs
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)
Volume3171
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

ConferenceSBIA
CountryBrazil
CitySão Luís, Maranhão
Period29/09/041/10/04

Keywords

  • Bioinformatics
  • Constraint programming
  • Machine learning

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

Cite this