Solving Weighted Constraint Satisfaction Problems with Memetic/Exact
  Hybrid Algorithms
  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.
