On the Practical Use of Variable Elimination in Constraint Optimization Problems: 'Still-Life' as a Case Study
Abstract
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.
Cite
Text
Larrosa et al. "On the Practical Use of Variable Elimination in Constraint Optimization Problems: 'Still-Life' as a Case Study." Journal of Artificial Intelligence Research, 2005. doi:10.1613/JAIR.1541Markdown
[Larrosa et al. "On the Practical Use of Variable Elimination in Constraint Optimization Problems: 'Still-Life' as a Case Study." Journal of Artificial Intelligence Research, 2005.](https://mlanthology.org/jair/2005/larrosa2005jair-practical/) doi:10.1613/JAIR.1541BibTeX
@article{larrosa2005jair-practical,
title = {{On the Practical Use of Variable Elimination in Constraint Optimization Problems: 'Still-Life' as a Case Study}},
author = {Larrosa, Javier and Morancho, Enric and Niso, David},
journal = {Journal of Artificial Intelligence Research},
year = {2005},
pages = {421-440},
doi = {10.1613/JAIR.1541},
volume = {23},
url = {https://mlanthology.org/jair/2005/larrosa2005jair-practical/}
}