Research map / Learning theory and algorithms / Combinatorial and search optimization
Enhance Diversified Top-k MaxSAT Solving by Incorporating New Strategy for Generating Diversified Initial Assignments (Student Abstract)
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes DTKMS-DIA, a local search solver for Diversified Top-k MaxSAT with a new unit-propagation-driven strategy for generating diversified initial assignments, outperforming LS-DTKMS on 3304 instances.
Problem
Diversified Top-k MaxSAT (DTKMS) requires finding k feasible assignments that jointly satisfy the maximum number of soft clauses; local search performance depends heavily on initial assignment quality, which prior work neglected.
Approach
A diversified initial assignment generator that alternates unit propagation (with prioritized unit clauses: hard, solution-falsified soft, solution-satisfied soft) and a heuristic variable selection scoring variables by previous assignment order and occurrence in falsified soft clauses, extending a decimation approach for MaxSAT.
Key results
- On 3304 DTKMS instances (826 formulas with k=2,3,4,5), DTKMS-DIA finds better solutions on 1662 instances versus 235 for LS-DTKMS, with 1407 ties (600s timelimit).
- On MSE23 with k=2, DTKMS-DIA is better on 602 instances vs 90 for LS-DTKMS.
- The authors conclude DTKMS-DIA is overall the best solver on these benchmarks.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use DTKMS-DIA's diversified initial-assignment strategy instead of LS-DTKMS | DTKMS solving · DTKCS (k=2–5) | #Better instances: 13 vs 2; 14 vs 0; 11 vs 0; 12 vs 0 | Helped |
| Use DTKMS-DIA's diversified initial-assignment strategy instead of LS-DTKMS | DTKMS solving · Unweighted Top-k (k=2–5) | #Better instances: 23 vs 0; 20 vs 0; 20 vs 0; 17 vs 0 | Helped |
| Use DTKMS-DIA's diversified initial-assignment strategy instead of LS-DTKMS | DTKMS solving · Unweighted MSE23 (k=2–5) | #Better instances: 602 vs 90; 498 vs 72; 254 vs 61; 178 vs 10 | Helped |
Limitations
- Evaluated only against a single baseline solver (LS-DTKMS)
- Only unweighted benchmarks evaluated
- Effect of parameters m, lambda1, lambda2 not analyzed in the abstract
Experimental setup
Datasets: MSE 2023 main unweighted track MSE 2020 top-k track DIMACS-based DTKCS instances
Benchmarks: MSE 2023 unweighted (732 instances) MSE 2020 top-k unweighted (73 instances) DTKCS (21 instances)
Metrics: number of instances with better soft clauses satisfied number of ties
Baselines: LS-DTKMS
Builds on: LS-DTKMS decimation approach for MaxSAT
Closest papers by meaning
- Improving the Lower Bound in Branch-and-Bound Algorithms for MaxSAT (AAAI 2025 · similarity 0.86)
- Better Understandings and Configurations in MaxSAT Stochastic Local Search Solvers via Anytime Performance Analysis (AAAI 2025 · similarity 0.85)
- DiverSAT: A Novel and Effective Local Search Algorithm for Diverse SAT Problem (AAAI 2025 · similarity 0.84)
- Theoretical and Empirical Analysis of Cost-Function Merging for Implicit Hitting Set WCSP Solving (AAAI 2024 · similarity 0.82)
- Parameterization of (Partial) Maximum Satisfiability above Matching in a Variable-Clause Graph (AAAI 2024 · similarity 0.80)
- Automatic Core-Guided Reformulation via Constraint Explanation and Condition Learning (AAAI 2024 · similarity 0.80)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.