Golden Ratio Annealing for Satisfiability Problems Using Dynamically Cooling Schemes

Abstract Satisfiability (SAT) Problem is an NP-Complete problem which means no deterministic algorithm is able to solve it in a polynomial time. Simulated Annealing (SA) can find very good solutions of SAT instances if its control parameters are correctly tuned. SA can be tuned experimentally or by using a Markov approach; the latter has been shown to be the most efficient one. Moreover Golden Ratio (GR) is an unconventional technique used to solve many problems. In this paper a new algorithm named Golden Ratio for Simulated Annealing (GRSA) is presented; it is tuned for three different cooling schemes. GRSA uses GR to dynamically decrease the SA temperature and a Markov Model to tune its parameters. Two SA tuned versions are compared in this paper: GRSA and a classical SA. Experimentation shows that the former is much more efficient than the latter. © Springer Nature