Solving the weighted MAX-SAT problem using the dynamic convexized method |
| |
Authors: | Wenxing Zhu Yuanhui Yan |
| |
Institution: | 1. Center for Discrete Mathematics and Theoretical Computer Science, Fuzhou University, Fuzhou?, 350108, China
|
| |
Abstract: | Satisfiability (SAT) and maximum satisfiability (MAX-SAT) are difficult combinatorial problems that have many important real-world applications. In this paper we investigate the performance of the dynamic convexized method based heuristics on the weighted MAX-SAT problem. We first present an auxiliary function which is constructed based on a penalty function, and minimize the function by a local search method which can escape successfully from previously converged local minimizers by increasing the value of a parameter. Two algorithms of the approach are implemented and compared with the Greedy Randomized Adaptive Search Procedure (GRASP) and the GRASP with Path Relinking (GRASP + PR). Experimental results illustrate efficient and faster convergence of our two algorithms. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|