# A General Framework Based on Machine Learning for
## 2 Background
### Instance Characterization  
In this investigation, we characterize the instances by using seven simple yet useful binary CSP features. Before describing them, we must introduce three concepts: the constraint density, the constraint tightness, and the clustering coefficient. To help clarify these concepts and features, we use the example CSP instance depicted in Figure 1.  
The constraint density of a variable is the number of constraints where it is involved divided by the maximum number of possible constraints for such a variable. In the case of binary constraints, a variable can participate in, at most, \(|X|-1\) constraints (which would mean that such a variable is fully connected to the remaining variables in the instance). In our example, variable \(x_{3}\) participates in three out of four possible constraints. Then, its constraint density is 0.75. The constraint tightness, on the other hand, applies to constraints, not to variables. The constraint tightness is the fraction of forbidden pairs of values between two variables given a constraint. It estimates how difficult it is to satisfy a constraint. In our example, each variable can take one out of five available values. Then, there are 25 possible combinations of value assignments for each constraint. The constraint between variables \(x_{1}\) and \(x_{2}\) forbids 20 out of those 25 possible assignments. In other words, such a constraint forbids 80% of the possible assignments, which is why tightness of this constraint is 0.8. The lower the tightness of a constraint, the easier it is to satisfy it. The clustering coefficient is somehow similar to the constraint density, but it takes the analysis a little further. It measures how close the neighbors of one particular variable are to being fully connected. For example, variable \(x_{2}\) is connected to two variables, \(x_{1}\) and \(x_{3}\). Then, its constraint density is 0.5 (it participates in two out of four possible constraints). By considering a subgraph containing only these three variables (\(x_{2}\) and its two neighbors \(x_{1}\) and \(x_{3}\)), we can have, at most, three constraints (assuming a fully connected graph). Since there are two out of three possible constraints in such a subgraph, the clustering coefficient of variable \(x_{2}\) is 0.66. Now, by using these three concepts, we can define the features used to characterize the instances in this work:  
Figure 1: An example of a Constraint Satisfaction Problem (CSP) instance. Average constraint density is the average of the constraint densities of all the variables within the instance. The constraint density in our example CSP is calculated as \[\left(\frac{1}{4}+\frac{2}{4}+\frac{3}{4}+\frac{1}{4}+\frac{1}{4}\right)\times \frac{1}{5}=0.4.\]
2. Average constraint tightness is the average of the constraint tightnesses of all the constraints within the instance. In our example, the constraint tightness is calculated as \[\frac{0.8+0.2+0.48+0.88}{4}=0.59.\]
3. Average clustering coefficient is the average of the clustering coefficients of all the variables within the instance. The average clustering coefficient of our example CSP is calculated as \[\left(1+\frac{2}{3}+\frac{3}{6}+1+1\right)\times\frac{1}{5}=0.83.\]
4. Lower quartile of the constraint density is the middle number between the smallest number and the median of the constraint densities of all the variables within the instance. First, we need to sort the constraint densities in our example CSP: 0.25, 0.25, 0.25, 0.5, and 0.75. Based on these values, the median is 0.25 and, in this case, the lower quartile is also 0.25. 5. Upper quartile of the constraint density is the middle number between the median and the largest of the constraint densities of all the variables within the instance. Based on the constraint densities sorted in the previous feature, the upper quartile is 0.50. 6. Lower quartile of the constraint tightness is the middle number between the smallest number and the median of the constraint tightnesses of all the constraints within the instance.