TL;DR
This paper introduces MWCLQ, a novel exact algorithm for the Maximum Weight Clique (MWC) problem that leverages MaxSAT reasoning. By developing a new "Literal-Weighted" (LW) encoding and specialized transformation rules, MWCLQ significantly outperforms existing state-of-the-art algorithms, especially on hard and dense graph instances.
What Problem Does This Paper Address?
The Maximum Weight Clique (MWC) problem is a fundamental combinatorial optimization problem with applications in areas like protein structure prediction and computer vision. While the unweighted Maximum Clique (MC) problem has seen significant algorithmic advancements, the MWC problem, which assigns weights to vertices, has been less explored. Existing exact algorithms for MWC often struggle with efficiency, particularly on challenging instances. This paper aims to bridge this gap by developing a more effective exact algorithm for MWC, building upon the success of MaxSAT reasoning in the MC domain.
Methods
The core contribution of this paper is the development of MWCLQ, a branch-and-bound algorithm that integrates MaxSAT reasoning for MWC. Key methodological innovations include:
- Literal-Weighted (LW) Encoding: Unlike previous approaches that encode MWC into standard MaxSAT, this paper introduces a novel LW encoding. In this encoding, both soft clauses and individual literals within soft clauses are weighted. This allows for a more nuanced representation of vertex weights.
- MaxSAT Reasoning for Upper Bounding: The LW encoding is designed such that an optimal solution to the MaxSAT instance provides an upper bound for the MWC, not the MWC itself. This is crucial because it allows for iterative refinement of the upper bound.
- Specialized Transformation Rules: To effectively tighten the upper bound, the authors introduce two transformation rules: the $\delta$-Rule and the $(k, \delta)$-Rule. These rules, driven by MaxSAT reasoning techniques like "Top-k literal failed clause" and "Top-k empty clause" detection, allow for splitting LW soft clauses to derive tighter bounds.
- Branch-and-Bound Framework: MWCLQ employs a branch-and-bound search strategy. At each node, it encodes the current subgraph into an LW MaxSAT instance, applies the transformation rules to compute a tight upper bound, and uses this bound for pruning the search space.
Datasets
The authors evaluated their algorithm on several standard benchmarks:
- DIMACS Benchmark: A widely used collection of instances for graph problems, including MC and MWC.
- BHOSLIB Benchmark: Instances known for being challenging for exact algorithms.
- Random Graphs: Generated with varying densities to assess asymptotic behavior.
- Winner Determination Problem (WDP) Instances: Realistic instances from combinatorial auctions, transformed into MWC problems.
Key Insights and Ideas
- MaxSAT for Upper Bounds is Key: The paper highlights that MaxSAT reasoning is most effective for MWC when used to compute tight upper bounds within a branch-and-bound framework, rather than directly solving for the MWC.
- LW Encoding's Advantage: The novel LW encoding is crucial. It allows for a more direct and effective integration of vertex weights into the MaxSAT formulation, enabling more powerful reasoning.
- Splitting for Tighter Bounds: The $\delta$-Rule and $(k, \delta)$-Rule, by splitting clauses based on MaxSAT reasoning, are instrumental in generating tighter upper bounds, leading to more efficient pruning.
- MWCLQ's Superiority: The experimental results consistently show that MWCLQ, by leveraging its specialized LW encoding and reasoning, significantly outperforms other state-of-the-art MWC solvers and MaxSAT solvers.
Key Results
- Performance on DIMACS: MWCLQ solved 61 out of 80 DIMACS instances within the cut-off time, outperforming Cliquer (52), DKum (48), MinSatz (58), and CPLEX (44). It also computed better lower bounds for instances that couldn't be solved.
- Performance on BHOSLIB: MWCLQ solved 5 instances, outperforming Cliquer (1), DKum (5), MinSatz (3), and CPLEX (1).
- Performance on Random Graphs: MWCLQ was the only algorithm to solve all 700 random graphs, significantly outperforming others in terms of runtime and search tree size, especially for dense graphs.
- WDP Instances: MWCLQ demonstrated strong performance on WDP instances, often outperforming other solvers and achieving significant speedups on harder instances.
- Comparison of Encodings: The LW encoding, used by MWCLQ, proved superior to direct, split, and iterative split encodings when integrated into a branch-and-bound framework.
Limitations and Future Work
- Encoding Impact: The paper notes that the choice of encoding significantly impacts the performance of MaxSAT solvers for MWC, and the LW encoding is crucial for MWCLQ's success.
- Vertex Ordering: The authors mention that vertex ordering can influence performance and plan to study its impact further.
- Unit Clause Ordering: Similarly, the ordering of unit clauses is identified as an area for future investigation.
- Other Combinatorial Problems: The authors suggest that the MaxSAT reasoning approach, with a dedicated encoding, could be extended to solve other combinatorial optimization problems, particularly their weighted versions.
Summary updated