An information-based neural approach to generic constraint satisfaction

Henrik Jönsson, Bo Söderberg

    Research output: Contribution to journalArticlepeer-review

    Abstract

    A novel artificial neural network heuristic (INN) for general constraint satisfaction problems is presented. extending a recently suggested method restricted to boolean variables. In contrast to conventional ANN methods, it employs a particular type of non-polynomial cost function, based on the information balance between variables and constraints in a mean-field setting. Implemented as an annealing algorithm, the method is numerically explored on a testbed of Graph Coloring problems. The performance is comparable to that of dedicated heuristics, and clearly superior to that of conventional mean-field annealing.
    Original languageEnglish
    Pages (from-to)1-17
    JournalArtificial Intelligence
    Volume142
    Issue number1
    DOIs
    Publication statusPublished - 2002

    Subject classification (UKÄ)

    • Biophysics

    Free keywords

    • constraint satisfaction
    • connectionist
    • artificial
    • neural network
    • heuristic information
    • mean-field annealing
    • graph coloring

    Fingerprint

    Dive into the research topics of 'An information-based neural approach to generic constraint satisfaction'. Together they form a unique fingerprint.

    Cite this