Improving stochastic local search for uniform <scp><i>k</i>‐SAT</scp> by generating appropriate initial assignment
Bibliographic record
Abstract
Abstract Stochastic local search (SLS) algorithms are well known for their ability to efficiently find models of random instances of the SAT problem, especially for uniform random k‐SAT instances. Two processes affect most SLS solvers—the initial assignment of the variables and the heuristics that select which variable to flip. In the last few years, the work on generating the appropriate initial assignment has not been paid much attention or seen much progress, while most SLS solvers focused on the heuristic algorithm. The present work aims to improve SLS algorithms on uniform random k‐SAT instances by developing effective methods for generating the initial assignment of variables in a controlled way. First, the allocation strategy introduced recently for 3‐SAT instances is extended to initialize the initial assignment on random k‐SAT instances. Then a concept of an initial probability distribution of the clause‐to‐variable ratio of the instance is introduced to determine the parameters of the allocation strategy. This combined method is added to the beginning of six state‐of‐the‐art SLS algorithms in order to generate initial assignments of variables in a controlled way instead of generating them randomly, resulting in six extended SLS algorithms named WalkSATlm_E, DCCASat_E, Score2SAT_E, CSCCSat_E, Probsat_E, and Sparrow_E, respectively. They are then evaluated in terms of their capabilities and efficiency on uniform random k‐SAT instance from the random track of SAT Competitions in 2016, 2017, and 2018. Experimental results show that these improved SLS solvers outperform their original performance, especially WalkSAT_E, Score2SAT_E, and CSCCSat_E outperform the winner of the random track of SAT competition in 2017. In addition, based on the initial probability distribution method, the present work proposes a parameter tuning and analysis of random 3‐SAT instances and provides an additional comparative analysis with the state‐of‐the‐art random SLS solvers based on large‐scale experiments.
Fetched live from OpenAlex and de-inverted. Abstracts are not stored in this database: the inverted indexes are 8.6 GB of the frame’s 9.3 GB of text, and the host has 13 GB free.
How this classification was reachedexpand
Full frame machine prediction
Teacher imitationNot calibrated prevalence, not ground truth. Human validation pending. The Gemma side is a direct model label for every work in the frame, read from the title-only record. The Codex side is a classifier learned from the 10,348 direct Codex labels and calibrated to design-weighted sample rates; fields without enough sample support carry no Codex call. Candidate is the union of the two sides; consensus is their intersection. These outputs are machine_predicted_unvalidated and are not human labels.
Distilled classifier scores by category (both heads)
| Category | Codex | Gemma |
|---|---|---|
| Metaresearch | 0.001 | 0.003 |
| Meta-epidemiology (narrow) | 0.001 | 0.000 |
| Meta-epidemiology (broad) | 0.001 | 0.001 |
| Bibliometrics | 0.001 | 0.001 |
| Science and technology studies | 0.000 | 0.001 |
| Scholarly communication | 0.001 | 0.001 |
| Open science | 0.001 | 0.001 |
| Research integrity | 0.001 | 0.001 |
| Insufficient payload (model declined to judge) | 0.003 | 0.001 |
Machine scores (provisional)
The two teacher heads of the student model, read on this work. A score orders the frame for review; it never asserts a category, and the validation status ships verbatim with every row.
Baseline scores from an immature model (maturity gate not passed, 7 training rounds). Scores rank; they never assert a category.
score_only:v0-immature-baseline · verbatim from the scoring run: score_only means the number may rank works, and no category label ships from itClassification
machine, unvalidatedMachine predicted; a candidate call from one source (direct Gemma or distilled Codex), not a consensus.
How this classification was reached, model by model and score by score, is at the end of the page under "How this classification was reached".