AIApr 19, 2013
Solving WCSP by Extraction of Minimal Unsatisfiable Cores
arXiv:1304.5449v13 citations
Originality Synthesis-oriented
AI Analysis
This work addresses WCSP, a combinatorial optimization problem, with an incremental approach that builds on existing techniques.
The paper tackles the Weighted Constraint Satisfaction Problem (WCSP) by integrating extraction and relaxation of Minimal Unsatisfiable Cores, proposing both an incomplete greedy algorithm and a complete algorithm.
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 decline our approach in two ways: an incomplete, greedy, algorithm and a complete one.