Enhance Diversified Top-k MaxSAT Solving by Incorporating New Strategy for Generating Diversified Initial Assignments (Student Abstract)

The Diversified Top-k MaxSAT (DTKMS) problem is an extension of MaxSAT. The objective of DTKMS is to find k feasible assignments of a given formula, such that each assignment satisfies all hard clauses and the k assignments together satisfy the maximum number of soft clauses. This paper presents a local search algorithm, DTKMS-DIA, which incorporates a new approach to generating initial assignments. Experimental results indicate that DTKMS-DIA can achieve attractive performance on 826 instances compared with state-of-the-art solvers.

Authors

• Jiaxin Liang School of Information Science and Technology, Northeast Normal University, China
• Junping Zhou School of Information Science and Technology, Northeast Normal University, China
• Minghao Yin Northeast Normal University

Keywords

• Diversified Top-k MaxSAT
• Local Search
• Top-k