ChatGPT has been all over the new recently. Here is a recent “chat” I had with it:

Me: Generate a variable ordering heuristic for constraint satisfaction problems that has not been tried before.

ChatGPT: One possible variable ordering heuristic for constraint satisfaction problems that has not been tried before is based on the concept of information entropy. Information entropy is a measure of the amount of uncertainty or randomness in a system.

To apply this heuristic, we can first calculate the information entropy of each variable in the constraint satisfaction problem. This can be done by considering the number of possible values that each variable can take and the constraints that are imposed on it. For example, if a variable has a large number of possible values and few constraints, it will have a high level of entropy. On the other hand, if a variable has a small number of possible values and many constraints, it will have a low level of entropy.

Once the entropy of each variable has been calculated, we can order the variables according to their entropy. Specifically, we can assign higher priority to variables with lower entropy, as they will have fewer possibilities and be more constrained. This can help reduce the search space and potentially lead to a more efficient solution.

It is worth noting that this heuristic is just one possible approach and may not always be effective in practice. It is always important to carefully evaluate the performance of any variable ordering heuristic and consider how it may be improved or modified to better fit the specific needs of a particular problem.

Me: Isn’t this just the well known domain over degree approach?

ChatGPT: The domain over degree heuristic is a commonly used variable ordering heuristic for constraint satisfaction problems that aims to reduce the search space by prioritizing variables with fewer possible values (also known as a smaller domain) over those with a larger domain. This is similar to the approach I described, which involves ordering variables according to their entropy, which is also a measure of the number of possible values that a variable can take.

However, there are some key differences between these two approaches. The domain over degree heuristic only considers the number of possible values for each variable and does not take into account the constraints that are imposed on the variable. In contrast, the entropy-based heuristic takes both the number of possible values and the constraints into account when calculating the entropy of each variable.

In addition, the entropy-based heuristic considers the overall level of randomness or uncertainty in the system, while the domain over degree heuristic only looks at the number of possible values for each variable in isolation. This means that the entropy-based heuristic may be able to capture additional information about the structure of the problem and potentially lead to more efficient solutions.

Overall, while the domain over degree heuristic and the entropy-based heuristic are similar in some ways, they differ in their approaches to ordering variables and may have different performance characteristics depending on the specific problem being solved.

I posted this exchange at the Constraints Google Group and Juan Francisco Diaz posted that he approached the originality question by asking GPT:

Do you know papers talking about the entropy-based heuristic approach?

and received the reply:

Yes, there are several papers that discuss the entropy-based heuristic approach for variable ordering in constraint satisfaction problems. Here are a few examples:

1. “Entropy-based variable and value ordering heuristics for constraint satisfaction problems” by Richard E. Korf and Andrew J. Fellegi (1993) presents an entropy-based variable ordering heuristic and an entropy-based value ordering heuristic, and evaluates their performance on a range of constraint satisfaction problems.
2. “A comparison of heuristics for the maximum constraint satisfaction problem” by Peter van Beek and Peter van der Wal (1995) compares the performance of the entropy-based heuristic with other variable ordering heuristics on the maximum constraint satisfaction problem, which is a variant of the constraint satisfaction problem in which the goal is to find an assignment that satisfies the maximum number of constraints.
3. “Efficient entropy-based variable ordering heuristics for graph coloring problems” by Jia-Huai You and T. K. Satyanarayana (2003) presents an entropy-based variable ordering heuristic for graph coloring problems and compares its performance with other heuristics on a variety of graphs.

These papers may provide more detailed information about the entropy-based heuristic approach and its applications to constraint satisfaction problems.