Arrêt de service programmé du vendredi 10 juin 16h jusqu’au lundi 13 juin 9h. Pour en savoir plus
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

https://hal-u-picardie.archives-ouvertes.fr/hal-03636420
Contributeur : Louise Dessaivre Connectez-vous pour contacter le contributeur
Soumis le : dimanche 10 avril 2022 - 11:39:16
Dernière modification le : lundi 11 avril 2022 - 03:31:05

Lien texte intégral

Identifiants

Collections

Citation

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

Partager

Métriques

Consultations de la notice

20