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 dis-carded 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 elim-ination to the challenging problem of nding 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. 1