• DocumentCode
    468418
  • Title

    A Value Ordering Heuristic for Weighted CSP

  • Author

    Levasseur, Nicolas ; Boizumault, Patrice ; Loudni, Samir

  • Author_Institution
    Univ. de Caen, Caen
  • Volume
    1
  • fYear
    2007
  • fDate
    29-31 Oct. 2007
  • Firstpage
    259
  • Lastpage
    262
  • Abstract
    In this paper, we propose a new value ordering heuristic for weighted constraint satisfaction problems (WCSP) based on the quality of solutions. The H-quality of an assignment estimates its capacity at occurring in solutions of "good" quality. Experiments using limited discrepancy search on random WCSP instances and CELAR benchmarks show that our value ordering always outperforms MinAC in a significant way.
  • Keywords
    constraint theory; estimation theory; optimisation; search problems; CELAR benchmarks; assignment estimation; limited discrepancy search; value ordering heuristic; weighted constraint satisfaction problems; Artificial intelligence; Constraint optimization; Cost accounting; Counting circuits; Filtering algorithms; Search methods; Tellurium;
  • fLanguage
    English
  • Publisher
    ieee
  • Conference_Titel
    Tools with Artificial Intelligence, 2007. ICTAI 2007. 19th IEEE International Conference on
  • Conference_Location
    Patras
  • ISSN
    1082-3409
  • Print_ISBN
    978-0-7695-3015-4
  • Type

    conf

  • DOI
    10.1109/ICTAI.2007.45
  • Filename
    4410292
    • Link To Document
    https://search.isc.ac/dl/search/defaultta.aspx?DTC=49&DC=468418