An Evolutionary Approach for Solving Multi-Objective WCSPs Using Mini-Bucket Elimination Heuristics

A Weighted Constraint Satisfaction Problem (WCSP) is a generalization of a constraint satisfaction problem (CSP) where some of the constraints can be violated at some cost and thus preferences among solutions can be expressed. Most research has focused on developing algorithms for solving single-objective problems. However, many real world constraint satisfaction problems involve multiple measures of performance that should be optimized simultaneously. In this paper, we introduce a new scheme that tackles the Multi-Objective WCSP combining multi-objective stochastic search and inference methods. The new approach exploits the efficiency of an evolutionary algorithm and the advantage of adaptable inference levels offered by the Mini-Bucket Elimination algorithm. Experiments conducted on the single-objective and the bi-objective variant of the Weighted Vertex Cover problem demonstrate the performance of the new approach, highlighting the benefits the inference step brings to the evolutionary algorithm.