# Dynamic Initial Weight Assignment for MaxSAT
## 4 Experimental Results and Analyses
### Results and Analysis  
Our initial expectation before starting our research was that dynamically allocating initial weights could have an impact on the performance level of algorithms that use weights when applied to handling MaxSAT. Moreover, our expectations became more logical due to the statistics extracted from the second step and linking them with the first step mentioned above. Therefore, we experimented with the dynamic weight distribution mechanism on the problems mentioned in Section 4.1. The experiment included recording the results of all the selected algorithms that proved their outstanding efficiency in addressing and solving SAT problems, DDFW, YaSAT, ProbSAT, and Sparrow. In more detail, we modified DDFW+InitWeight, such that instead of stopping upon reaching a solution in which the number of unsatisfied clauses was zero, DDFW+InitMaxSAT stopped if a certain cut-off number of flips was reached or timed out. Moreover, all algorithms were also modified to record the best solution reached (the maximum number of satisfied clauses or the minimum number of unsatisfied clauses) and the time taken to reach that solution. The experiments were performed on an iMac I5 with a 2.5 GHz CPU and 16 GB of RAM. To decide the cut-off, we allowed DDFW+InitMaxSAT a single trial on all the problems with a 20,000,000 flip cut-off. The best cost (maximum number of satisfied clauses) was recorded then it was used for the full experiments. All the solvers were then allowed 1000 runs on each instance. The termination of each run was performed by either reaching the flip cut-off or after 10 s.  
Table 2 shows the algorithms' CPU run time when they were applied to MaxSAT problems. We decided to choose DDFW and its variant, DDFW+InitMaxSAT, in our experiment. Furthermore, the study included the experimental results of three other algorithms, YaSIAT, Sparrow, and ProbSAT. Firstly, as mentioned above, our choice of DDFW to implement the InitWeight mechanism was that it did not need parameter tuning. The reason for choosing the other three algorithms was that they were the most closely related algorithms to our algorithm, in their method of using weights and solving steps. The ProbSAT algorithm depends on a simplified method, mostly depending on the number of clauses that may become unsatisfied, in deciding to change one of the variables' value. ProbSAT uses a set of parameters in which an automated mechanism is used to reach their ideal values. We relied in this research on the default values of the parameters published in [26]. As for the YaleSatalgorithm, the experiment indicated that it was more sensitive to the parameter settings when the search process had to be restarted and whether the restart had to start over by assigning random values to the variables or using the clause sizes to determine the value of the weight that should be assigned. Like our approach, YaSIAT considers the size of clauses and their neighborhood size to decide on the amount of weight to be allocated to the clauses during the search process. Here, we would like to point out  
Figure 4: The figure illustrates the most weighted clauses and their corresponding neighborhood size for the uuf problem set (30 instances), where the overall average of the neighborhood size is \(\approx\)23.  
that this difference is fundamentally from the mechanism we presented in this research, as our mechanism allocated the initial weights dynamically before starting the search process instead of through the search process. As for the Sparrow algorithm, weights were used in selecting the variables that appeared promising and that, by changing their value, could lead to reaching partial solutions that were better than the current solution. Sparrow is distinguished because it relies on two properties to determine the probability of choosing one of the weighted variables to change its value (see [27]). We want to emphasize that parameter tuning for this study's algorithms was not allowed to ensure fairness.