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
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;
Conference_Titel :
Tools with Artificial Intelligence (ICTAI), 2013 IEEE 25th International Conference on
Conference_Location :
Herndon, VA
Print_ISBN :
978-1-4799-2971-9
DOI :
10.1109/ICTAI.2013.140
