On the Practical use of Variable Elimination in Constraint Optimization Problems: 'Still-life' as a Case Study

Details On the Practical use of Variable Elimination in Constraint Optimization Problems: 'Still-life' as a Case Study On the Practical use of Variable Elimination in Constraint Optimization Problems: 'Still-life' as a Case Study

2011-09-09

arxiv.org/abs/1109.2131v1

Journal Of Artificial Intelligence Research, Volume 23, pages 421-440, 2005

Computer Science

Artificial Intelligence

Scientific paper

10.1613/jair.1541

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.

Affiliated with

Also associated with

No associations

Rating

On the Practical use of Variable Elimination in Constraint Optimization Problems: 'Still-life' as a Case Study does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with On the Practical use of Variable Elimination in Constraint Optimization Problems: 'Still-life' as a Case Study, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and On the Practical use of Variable Elimination in Constraint Optimization Problems: 'Still-life' as a Case Study will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-38027