An Exact Algorithm Based on MaxSAT Reasoning for the Maximum Weight Clique Problem

Zhiwen Fang, Chu-Min Li, Ke Xu

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

Abstract

Recently, MaxSAT reasoning is shown very effective in computing a tight upper bound for a Maximum Clique (MC) of a (unweighted) graph. In this paper, we apply MaxSAT reasoning to compute a tight upper bound for a Maximum Weight Clique (MWC) of a wighted graph. We first study three usual encodings of MWC into weighted partial MaxSAT dealing with hard clauses, which must be satisfied in all solutions, and soft clauses, which are weighted and can be falsified. The drawbacks of these encodings motivate us to propose an encoding of MWC into a special weighted partial MaxSAT formalism, called LW (Literal-Weighted) encoding and dedicated for upper bounding an MWC, in which both soft clauses and literals in soft clauses are weighted. An optimal solution of the LW MaxSAT instance gives an upper bound for an MWC, instead of an optimal solution for MWC. We then introduce two notions called the Top-k literal failed clause and the Top-k empty clause to extend classical MaxSAT reasoning techniques, as well as two sound transformation rules to transform an LW MaxSAT instance. Successive transformations of an LW MaxSAT instance driven by MaxSAT reasoning give a tight upper bound for the encoded MWC. The approach is implemented in a branch-and-bound algorithm called MWCLQ. Experimental evaluations on the broadly used DIMACS benchmark, BHOSLIB benchmark, random graphs and the benchmark from the winner determination problem show that our approach allows MWCLQ to reduce the search space significantly and to solve MWC instances effectively. Consequently, MWCLQ outperforms state-of-the-art exact algorithms on the vast majority of instances. Moreover, it is surprisingly effective in solving hard and dense instances.
BibTeX
@article{fang2016exact,
  author = {Zhiwen Fang and Chu-Min Li and Ke Xu},
  title = {{An Exact Algorithm Based on MaxSAT Reasoning for the Maximum Weight Clique Problem}},
  journal = {J. Artif. Intell. Res.},
  year = {2016},
  doi = {10.1613/jair.4953},
}
Figure