An iterative Path-Breaking approach with mutation and restart strategies for the MAX-SAT problem

International audienceAlthough Path-Relinking is an effective local search method for many combinatorial optimization problems, its application is not straightforward in solving the MAX-SAT, an optimization variant of the satisfiability problem (SAT) that has many real-world applications and has gained more and more attention in academy and industry. Indeed, it was not used in any recent competitive MAX-SAT algorithms in our knowledge. In this paper, we propose a new local search algorithm called IPBMR for the MAX-SAT, that remedies the drawbacks of the Path-Relinking method by using a careful combination of three components: A new strategy named Path-Breaking to avoid unpromising regions of the search space when generating trajectories between an elite solution and its inverse solution; a weak and a strong mutation strategies, together with restarts, to diversify the search; and stochastic path generating steps to avoid premature local optimum solutions. We then present experimental results to show that IPBMR outperforms two of the best state-of-the-art MAX-SAT local search solvers, and an empirical investigation to identify and explain the effect of the three components in IPBMR. (C) 2018 Elsevier Ltd. All rights reserved