最大可满足性问题（Maximum Satisfiability problem,Max SAT）是第一个被证明为NP完全的可满足性问题（Satisfiability problem,SAT）的优化形式。作为逻辑约束优化模型,Max SAT有很强的表达能力,学术研究以及工业优化中有很多问题都可以转化为Max SAT问题,从而利用Max SAT的方法和策略进行研究或求解。近年来,国内外研究者们对Max SAT问题的求解进行了非完备算法和完备算法两个方面的研究,使得Max SAT问题的求解方法和技术有了显著的进步。非完备算法的求解目标是在较短的时间内找到更优质的解,不需保证解的全局最优性,而完备算法则是需要在求解时保证解的最优性。非完备算法的求解器在随机、构造或者某些特定结构的非复杂算例上优势明显,但在工业算例等大规模复杂算例上则弱于完备算法求解器。当前优秀的完备求解器大多是基于SAT求解器的,即调用SAT求解器来间接发挥针对SAT的子句学习策略的强大求解能力。而作为另一类Max SAT问题的完备求解器,基于分支限界（Branch and Bound,Bn B）的完备求解器在近年来发展缓慢。针对如上的现状,本课题对Max SAT问题的非完备算法和完备算法进行了深入研究,主要的研究内容和创新点包括如下三个部分。首先,提出了新的局部搜索策略,称为路径截断策略,并提出结合该策略以及适配的重启和扰动策略的算法。通过对局部搜索中的路径重连策略进行实验研究,分析其求解Max SAT问题效果较差的原因。针对该原因在路径搜索中加入截断条件并改进初始解策略从而提出了新的路径搜索策略,即路径截断策略（PB,Path-Breaking）。然后,设计了一个重启迭代搜索框架,再加入扰动策略,包括强扰动和弱扰动,从而有效利用局部最优信息,最后形成了高效的局部搜索算法,称为IPBMR（Iterative Path-Breaking approach with Mutation and Restart strategies）。实验结果表明,该算法超越了当时最好的局部搜索算法CCLS等,在国际Max SAT竞赛（Max SAT Evaluation,MSE）2016年的大部分算例中IPBMR算法的求解速度比CCLS有数量级上的提升。其次,对非完备算法求解工业大算例效果较差的问题进行分析,提出了新的初始解构造算法,其中包含一个全局信息反馈策略;在此基础上,提出了将该初始解构造算法和路径截断策略相结合的算法。对IPBMR进行了实验分析,发现了其在求解工业大算例中的弱点并分析了原因,然后针对性地提出了一个基于树形赋值的初始解构造算法ASIF（Assignment approach by Search Information Feedback）。该算法选取并定义了构造过程中有意义的量,使用这些量设计了一个全局搜索信息更新反馈机制,对初始解构造过程中的经验进行积累并为后续解的构造提供指导信息,再根据后续解的构造情况对全局经验进行反馈和更新,从而有效利用了解构造过程中的经验和信息。将ASIF作为初始解构造算法,结合IPBMR中的PB策略,形成了新的算法PB-ASIF（Path-Breaking approach with ASIF strategies）。实验结果表明,ASIF算法能快速构造优质的初始可行解,PB-ASIF求解工业算例的能力明显超过了IPBMR,有效改进了使用PB策略求解工业算例的效果,且PB-ASIF具有提升其它求解器求解效果的潜力。最后,对完备算法中的子句学习策略以及分支限界策略进行研究,提出了针对Max SAT问题的子句学习策略,并结合该子句学习策略和分支限界策略提出了新的完备算法。当前没有直接用于Max SAT问题求解的冲突驱动子句学习方法,依赖SAT完备求解技术的进步会使Max SAT完备求解算法的发展受限。而基于分支限界的算法在近些年的发展缓慢,它未直接应用子句学习策略也没有适用的知识积累策略。为了构建完备算法的知识积累策略,提出了针对Max SAT问题求解的子句学习策略。并针对大算例的求解设计了新的分支限界策略,然后结合改进的分支限界策略和子句学习策略提出了求解Max SAT问题的完备算法,称为Max CDCL。实验结果表明,该算法对比MSE2020竞赛求解器能排进前五,且其求解的算例中有很多是基于SAT的Max SAT求解器无法解出的,表明针对Max SAT问题求解的子句学习新策略有很强的发展潜力。与SAT问题的冲突驱动子句学习策略一样,Max SAT子句学习策略刚刚提出就显示出了很强的竞争力,Max SAT子句学习策略的发展将有力推进Max SAT完备算法的求解能力的提升。该算法有效提升了基于分支限界的Max SAT完备算法的求解性能,为该类算法的发展提供了新的思路。