On the Practical use of Variable Elimination in Constraint Optimization
  Problems: 'Still-life' as a Case Study
  Variable elimination is a general technique for constraint processing. It is
often discarded because of its high space complexity. However, it can be
extremely useful when combined with other techniques. In this paper we study
the applicability of variable elimination to the challenging problem of finding
still-lifes. We illustrate several alternatives: variable elimination as a
stand-alone algorithm, interleaved with search, and as a source of good quality
lower bounds. We show that these techniques are the best known option both
theoretically and empirically. In our experiments we have been able to solve
the n=20 instance, which is far beyond reach with alternative approaches.
