Solving Weighted Constraint Satisfaction Problems with Memetic/Exact Hybrid Algorithms
This work addresses scalability issues in constraint optimization for researchers and practitioners, though it is incremental as it builds on existing techniques like bucket elimination and memetic algorithms.
The authors tackled the inefficiency of existing methods for solving weighted constraint satisfaction problems (WCSPs) on large scales by developing a memetic/exact hybrid algorithm, which consistently finds optimal solutions faster for known instances and provides new best solutions for very large instances.
A weighted constraint satisfaction problem (WCSP) is a constraint satisfaction problem in which preferences among solutions can be expressed. Bucket elimination is a complete technique commonly used to solve this kind of constraint satisfaction problem. When the memory required to apply bucket elimination is too high, a heuristic method based on it (denominated mini-buckets) can be used to calculate bounds for the optimal solution. Nevertheless, the curse of dimensionality makes these techniques impractical on large scale problems. In response to this situation, we present a memetic algorithm for WCSPs in which bucket elimination is used as a mechanism for recombining solutions, providing the best possible child from the parental set. Subsequently, a multi-level model in which this exact/metaheuristic hybrid is further hybridized with branch-and-bound techniques and mini-buckets is studied. As a case study, we have applied these algorithms to the resolution of the maximum density still life problem, a hard constraint optimization problem based on Conways game of life. The resulting algorithm consistently finds optimal patterns for up to date solved instances in less time than current approaches. Moreover, it is shown that this proposal provides new best known solutions for very large instances.