Maximum satisfiability (MaxSAT) is a well-known optimization problem and has a wider range of practical applications. Local search is an efficient incomplete method for solving MaxSAT and is useful in fields where high-quality solutions need to be obtained in a reasonable time. For the local search MaxSAT solver, the effectiveness of the initial assignment affects the actual performance, and the existing random initial assignments are often quite different from the optimal solution. In this work, we propose a structure-based initial assignment method, which will obtain an effective initial assignment according to the specific structure of the MaxSAT, called J-init. Experimental results show that the initialization method based on the J-init can effectively improve the solution quality of the MaxSAT problem within the specified time. By using this method, we can get a reasonable initial assignment in a shorter time and provide a more promising starting point for the subsequent optimization process.

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

Optimization of MaxSAT Local Search Solver Based on J-init Assignment

  • Chao Xu,
  • Kang Liu

摘要

Maximum satisfiability (MaxSAT) is a well-known optimization problem and has a wider range of practical applications. Local search is an efficient incomplete method for solving MaxSAT and is useful in fields where high-quality solutions need to be obtained in a reasonable time. For the local search MaxSAT solver, the effectiveness of the initial assignment affects the actual performance, and the existing random initial assignments are often quite different from the optimal solution. In this work, we propose a structure-based initial assignment method, which will obtain an effective initial assignment according to the specific structure of the MaxSAT, called J-init. Experimental results show that the initialization method based on the J-init can effectively improve the solution quality of the MaxSAT problem within the specified time. By using this method, we can get a reasonable initial assignment in a shorter time and provide a more promising starting point for the subsequent optimization process.