An iterative Path-Breaking approach with mutation and restart strategies for the MAX-SAT problem - Archive ouverte HAL Accéder directement au contenu
Article Dans Une Revue Computers and Operations Research Année : 2019

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

(1) , (1) , (2, 3)
1
2
3

Résumé

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.

Dates et versions

hal-03636420 , version 1 (10-04-2022)

Identifiants

Citer

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, 2019, 104, pp.49-58. ⟨10.1016/j.cor.2018.12.005⟩. ⟨hal-03636420⟩
24 Consultations
0 Téléchargements

Altmetric

Partager

Gmail Facebook Twitter LinkedIn More