What is Least-Constraining-Value?

Question

In constraint satisfaction problems, heuristics can be used to improve the performance of a bactracking solver. Three commonly given heuristics for simple backtracking solvers are:

• Minimum-remaining-values (how many values are still valid for this variable)
• Degree heuristic (how many other variables are affected by this variable)
• Least-constraining-value (what value will leave the most other values for other variables)

The first two are pretty obvious and simple to implement. First choose the variable that has the least values left in its domain, and if there are ties, choose the one that affects the most other variables. This way if a parent step in the solver picked a bad assignment, you are likely to find out sooner and thereby save time if you choose the variable with the least values left that affects the most other things.

Those are simple, clearly defined, and easy to implement.

Least-constraining-value is not clearly defined, anywhere I looked. Artificial Intelligence: A Modern Approach (Russel & Norvig) just says:

It prefers the value that rules out the fewest choices for the neighboring variables in the constraint graph.

Searching for "least-constraining-value" only turned up a lot of university slide shows based on this textbook, with no further information on how this would be done algorithmically.

The only example given for this heuristic is a case where one choice of value eliminates all choices for a neighboring variable, and the other does not. The problem with this example is that it this is a trivial case, which would be eliminated immediately when the potential assignment is checked for consistency with the problem's constraints. So in all the examples I could find, the least-constraining-value heuristic didn't actually benefit the solver performance in any way, except for a small negative effect from adding a redundant check.

The only other thing I can think of would be to test the possible assignments of the neighboring variables for each assignment, and count the number of possible assignments of the neighbors that exist for each possible assignment of this variable, then order the values for this variable based on the number of neighbor assignments available if that value is chosen. However, I don't see how this would offer an improvement over a random order, since this requires both testing numerous variable combinations and sorting based on the results from counting.

Can anyone give a more useful description of least-constraining-value, and explain how that version of least-constraining-value would actually yield an improvement?

Answer 1

see this link:

https://people.cs.pitt.edu/~wiebe/courses/CS2710/lectures/constraintSat.example.txt

It first picks variable "O" and then tests "O" with all of it's legal values "i" to see the number of reductions on "O"'s neighbors "N". It adds all of them. and picks an "i" that causes less reductions:

   sums = {0:0,1:0,2:0,3:0,4:0,5:0,6:0,7:0,8:0,9:0}
   For i from 0 to 9:  
     plug "o=i" into the constraint formulas
     For each neighbor "N" of "o" in the constraint graph:
       sums[i] += the number of values remaining for "N"

It picks "i" so that:

sums[i] = MAX{sums[i] | for all "i" that is a member of "O",s valid values}

I hope This can help you find your answer!

Answer 2

I think that the main thing here is that these heuristics are applied depending on the task for which the solver is written. And if there is a possibility that if the selected value of a variable does not leave a single value in the domain of another variable (let's say that we have heavily-constrained problem with only one solution), then the solution will come to a standstill. And a random search can go along the right path leading to a decision and the wrong one. And if it goes wrong, you will have to do backtracking (see conflict-directed backjumping), and it takes computational time. But the algorithm using LCV heuristics is more likely to go along a more correct path and no returns are required. But if there is underconstrained problem I think it will be much like random search. But I admit that my opinion may not be absolutely correct and this is only my understanding of the problem, since I do not have much experience with CSP.