• DocumentCode
    3229294
  • Title

    Solving WCSP by Extraction of Minimal Unsatisfiable Cores

  • Author

    Lecoutre, Christophe ; Paris, Nicolas ; Roussel, Olivier ; Tabary, Sebastien

  • Author_Institution
    CRIL, Univ. Lille-Nord de France, Lens, France
  • fYear
    2013
  • fDate
    4-6 Nov. 2013
  • Firstpage
    915
  • Lastpage
    922
  • Abstract
    Usual techniques to solve WCSP are based on cost transfer operations coupled with a branch and bound algorithm. In this paper, we focus on an approach integrating extraction and relaxation of Minimal Unsatisfiable Cores in order to solve this problem. We derive our approach in two ways: an incomplete, greedy, algorithm and a complete one.
  • Keywords
    constraint satisfaction problems; greedy algorithms; minimisation; tree searching; WCSP; branch-and-bound algorithm; cost transfer operation; incomplete greedy algorithm; minimal unsatisfiable core extraction; minimal unsatisfiable core relaxation; weighted constraint satisfaction problem; Arrays; Artificial intelligence; Complexity theory; Conferences; Cost function; Lenses;
  • fLanguage
    English
  • Publisher
    ieee
  • Conference_Titel
    Tools with Artificial Intelligence (ICTAI), 2013 IEEE 25th International Conference on
  • Conference_Location
    Herndon, VA
  • ISSN
    1082-3409
  • Print_ISBN
    978-1-4799-2971-9
  • Type

    conf

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