最大可满足性问题的算法研究综述

Survey on algorithms for the maximum satisfiability problem

最大可满足性问题(maximum satisfiability,MaxSAT)是一个著名的、具有NP难度的组合优化问题.本研究总结了近年来求解最大可满足性问题的各类算法.首先,给出了最大可满足性问题的定义;然后,基于完备算法和非完备算法两个类型,对求解MaxSAT的各类算法进行了综述.其中完备算法包括分支定界算法和迭代调用可满足性问题求解器的算法,非完备算法包括近似算法、基于最小校正子集的算法和局部搜索算法;最后,分析和对比了各类求解算法的优劣,并对最大可满足性问题求解所面临的挑战及可能的研究方向进行了讨论和展望.

The maximum satisfiability problem(MaxSAT)is a well-known and NP-hard combinatorial optimization problem.A survey on various algorithms for the maximum satisfiability problem proposed in recent years was provided.Firstly,the problem definition of the maximum satisfiability problem was provided.Then,the algorithms for solving MaxSAT were summarized,including complete algorithms and incomplete algorithms.The complete algorithms include the branch and bound algorithms,and the algorithms that solving the problem by iteratively calling of a solver for the satisfiability problem.The incomplete algorithms include the approximation algorithms,the algorithms based on minimal correction subset,and the local search algorithms.In the end,the advantages and disadvantages for each kind of algorithms were compared,and the challenges and possible research directions for solving the maximum satisfiability problem were further discussed and prospected.