## 1 Introduction
However, the nature of SLS techniques is that they are incomplete (no guarantee to explore the search space [11] fully); therefore, they can not prove satisfiability. Nevertheless, almost four decades' effort pays off as there are many algorithms capable of handling the SAT problem with hundreds of thousands of variables, which was satisfying when formulating and handling the real-world problem into SAT. However, when converted into the SAT problem, the modern real-world problems require solving the SAT problem that is much larger, in much less time than the size of the SAT problems and the solving speed a decade ago. These requirements of the modern real-world problems imposed even more challenges into handling the SAT problem. Therefore, researchers in both tracks: the exact search area (also known as complete or systematic search), and the stochastic local search (also known as optimization search, or incomplete search [12]), are trying to investigate more efficient algorithms to handle the size (where the hardware is limited) and the speed in which the solution to the SAT problem is satisfying w.r.t both the quality of the solution and the speed of reaching it. SLS techniques, no matter how sophisticated they are, are either descending directly from or based indirectly on the work of [PERSON] and [PERSON] on Local Search (LS), that is, hill-climbing [13]. The hill-climbing procedure iteratively improves the objective function, where all the violated constraints (clauses in SAT encoded problems in CNF (Conjunctive normal form)) are measured by searching for moves that reduce the total number of violated constraints. For example, while searching for a solution, any local modification (moves) that make a major reduction of the objective function is taken. The work of [PERSON] and [PERSON] showed that hill-climbing successfully reaches solutions when handling problems such as travelling salesman problem and the n-queenproblem [13] However, the hill-climbing algorithm is faced with encountering what is known as local optima, in which there are no moves in the current solution stage that improve the objective function cost, that is, getting stuck in local minima. In Reference [14], another algorithm that could improve the hill-climbing algorithm was proposed that employs a random walk known as WalkSAT ([15]). The random walk addition reduces the level of the hill-climbing algorithm greediness by increasing the level of the randomness through explicitly picking at complete random order any unsatisfied clause (violated constraint) within the current solution stage and flip one of its literals (assign a different value from the variable domain in constraints satisfaction problem (CSP) [16]). Another algorithm based on the hill-climbing local search algorithm is the greedy local search (GSAT) [17] algorithm, which generally follows the hill-climbing procedure such that the moves must improve the current objective function cost, with the addition that equal-cost moves are permitted with a probability parameter \(p\) (also known as noise as in simulated annealing [18; 19; 20; 21]). The GSAT algorithm could prevent the search process from getting stuck in plateaus, which is another drawback of the hill-climbing algorithm. Thus, the GSAT algorithm could continue searching even though the objective function cost is not improving. In other words, GSAT improved the performance of the hill-climbing algorithm and could successfully cope with the hill-climbing level of greediness through the sideway utilization. However, adding the noise to allow the sideway moves does not prevent GSAT from getting stuck in local minima; therefore, GSAT+Restart (GSAT reset), GSAT+Random Walk, and GSAT+Weights were proposed in the year 1993 [21]. The three variants' experimental results show that major improvements are gained such that larger problems could be handled, and the speed of reaching feasible solutions was improved. In 1993 also, [PERSON] [22] proposed a similar clause weighting technique known as Breakout algorithm.