Accéder directement au contenu Accéder directement à la navigation
Article dans une revue

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

Abstract : Although 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.
Type de document :
Article dans une revue
Liste complète des métadonnées
Contributeur : Louise DESSAIVRE Connectez-vous pour contacter le contributeur
Soumis le : dimanche 10 avril 2022 - 11:39:16
Dernière modification le : mardi 30 août 2022 - 17:02:43

Lien texte intégral




Zhenxing Xu, Kun He, Chu-Min Li. An iterative Path-Breaking approach with mutation and restart strategies for the MAX-SAT problem. Computers and Operations Research, Elsevier, 2019, 104, pp.49-58. ⟨10.1016/j.cor.2018.12.005⟩. ⟨hal-03636420⟩



Consultations de la notice