A new PSO approach to constraint satisfaction

Constraint satisfaction arises in many domains in different forms. Search and inference compete for solving constraint satisfaction problems (CSPs) but the most successful approaches are those which benefit from both techniques. Based on this idea, this article introduces a new scheme for solving the general Max-CSP problem. The new approach exploits the simplicity and efficiency of a modified Particle Swarm Optimization and the advantage of adaptable inference levels offered by the Mini-Bucket Elimination algorithm. Experiments conducted on binary CSPs using different levels of inference are illustrative for the inference/search trade-off. Comparative studies highlight the differences between our stochastic population-based method and the systematic search performed by a Branch and Bound algorithm.