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

Jiaxin Liang, Junping Zhou, Minghao YinAAAI 2024 · DOI

TL;DR

This paper introduces DTKMS-DIA, a new local search algorithm for the Diversified Top-k MaxSAT (DTKMS) problem. Its core innovation lies in a novel strategy for generating diverse initial assignments, which significantly improves performance compared to existing state-of-the-art solvers.

What Problem Does This Paper Address?

The Diversified Top-k MaxSAT (DTKMS) problem is an extension of the classic MaxSAT problem. While MaxSAT aims to find a single assignment that satisfies the maximum number of "soft" clauses (while ensuring all "hard" clauses are satisfied), DTKMS seeks to find k distinct assignments that collectively satisfy the most soft clauses. This is crucial for applications where diversity in solutions is as important as the quality of individual solutions, such as in network routing or combinatorial auctions. Existing local search algorithms for DTKMS, while effective, have historically paid limited attention to the crucial step of generating good initial assignments, which can heavily influence the overall search process and the quality of the final diverse set of solutions. This paper addresses this gap by proposing a more sophisticated method for generating these initial assignments.

Methods

DTKMS-DIA employs a local search framework that alternates between two main procedures: solution construction and solution updating. The key novelty lies in the diversified initial assignment generation strategy. This strategy is driven by unit propagation, a standard technique in SAT solving. It iteratively assigns variables, prioritizing hard clauses, then solution-falsified soft clauses, and finally solution-satisfied soft clauses. When unit propagation reaches a dead end (no more unit clauses), a heuristic is used to select the next unassigned variable. This heuristic considers the variable's occurrence in currently falsified soft clauses and its assignment order in the previous assignment to encourage diversity. The generated initial assignments are then refined by local search to find feasible assignments in different search areas.

Datasets

The paper evaluates DTKMS-DIA on 826 instances from:

  • The main unweighted track of MSE 2023.
  • The top-k track of MSE 2020.
  • Benchmarks derived from the Diversified Top-k Clique Search (DTKCS) problem, modeled as DTKMS instances.

Key Insights and Ideas

  • Initial Assignment Quality is Paramount: The paper strongly emphasizes that the quality and diversity of initial assignments are critical factors for the success of local search algorithms in DTKMS.
  • Unit Propagation as a Diversity Driver: Leveraging unit propagation, not just for constraint satisfaction but also for guiding the assignment process based on clause types (hard, falsified soft, satisfied soft), is a novel way to inject diversity.
  • Balancing Exploration and Exploitation: The combination of unit propagation (controlled assignment) and a heuristic for unassigned variables (guided exploration) allows for a broader exploration of the solution space while still aiming for good solutions.

Key Results

DTKMS-DIA demonstrated superior performance compared to the state-of-the-art local search solver LS-DTKMS. Across 826 instances and various values of k (2, 3, 4, 5), DTKMS-DIA found more instances with better solutions (#Better) and a comparable number of equally good solutions (#Equal) than LS-DTKMS. For instance, on the Unweighted MSE23 (732 instances) benchmark with k=2, DTKMS-DIA achieved 602 "better" solutions compared to LS-DTKMS's 90. Overall, DTKMS-DIA is presented as the best solver on these benchmarks.

Limitations and Future Work

The authors acknowledge that their work focuses on enhancing the initial assignment generation strategy. Future work will involve developing more optimized techniques and conducting comprehensive studies on real-world applications of DTKMS. The paper does not explicitly discuss limitations related to scalability for extremely large instances or specific types of problems where the proposed heuristic might struggle.

Summary updated

BibTeX
@inproceedings{liang2024enhance,
  author = {Jiaxin Liang and Junping Zhou and Minghao Yin},
  title = {{Enhance Diversified Top-k MaxSAT Solving by Incorporating New Strategy for Generating Diversified Initial Assignments (Student Abstract)}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2024},
  doi = {10.1609/aaai.v38i21.30473},
}
Figure