Does it matter to first select one variable or another in Constraint Satisfaction Problems?

What is it about?

Constraint Satisfaction Problems (CSPs) are one kind of combinatorial optimization problems. But, they are computationally expensive to evaluate, even when using modern techniques. In this kind of problems, variables are linked together, so choosing one value for a variable limits the values others may take. So, how important is it to actually select an appropriate value for the first few variables? We aim to explore this in our work. Also, we show that such a selection can even affect simple techniques.

Featured Image

Why is it important?

Selecting a value for a variable may improve or harm the performance of a technique, even a simple one. So, we should take this information into account when defining strategies for solving CSPs.