Efficient branch-and-bound algorithms for weighted MAX-2-SAT
Efficient branch-and-bound algorithms for weighted MAX-2-SAT
复制标题
DOI：
10.1007/s10107-009-0285-6
复制
发表时间：
2011-04
影响因子：
2.7
通讯作者：
T. Ibaraki;T. Imamichi;Yuichi Koga;H. Nagamochi;K. Nonobe;M. Yagiura
中科院分区：
文献类型：
--
作者：
T. Ibaraki;T. Imamichi;Yuichi Koga;H. Nagamochi;K. Nonobe;M. Yagiura
MAX-2-SAT是典型的组合问题之一，是np困难问题。给定一组非命题变量的子句，其中每个子句最多包含两个字面量，并由一个正实数加权，MAX-2-SAT要求找到一个使满足子句的总权重最大化的真值分配。在本文中，我们利用三种下界提出了MAX-2-SAT的分支定界精确算法。所有下界都基于表示子句之间冲突的有向图，其中两个使用MAX-2-SAT的集合覆盖表示。在基准实例上的计算比较表明，这些算法在减少搜索树节点数量和计算时间方面非常有效。
MAX-2-SAT is one of the representative combinatorial problems and is known to be NP-hard. Given a set ofmclauses onnpropositional variables, where each clause contains at most two literals and is weighted by a positive real, MAX-2-SAT asks to find a truth assignment that maximizes the total weight of satisfied clauses. In this paper, we propose branch-and-bound exact algorithms for MAX-2-SAT utilizing three kinds of lower bounds. All lower bounds are based on a directed graph that represents conflicts among clauses, and two of them use a set covering representation of MAX-2-SAT. Computational comparisons on benchmark instances disclose that these algorithms are highly effective in reducing the number of search tree nodes as well as the computation time.