Theoretical and Empirical Analysis of Cost-Function Merging for Implicit Hitting Set WCSP Solving

Javier Larrosa, Conrado Martínez, Emma RollonAAAI 2024 · DOI

TL;DR

This paper tackles the inefficiency of the Implicit Hitting Set (HS) algorithm for Weighted Constraint Satisfaction Problems (WCSP) by introducing cost-function merging techniques. They theoretically analyze and empirically validate that merging cost functions can drastically reduce the number of iterations required by HS, making it more practical for complex problems.

What Problem Does This Paper Address?

The Implicit Hitting Set (HS) approach has proven highly effective for solving MaxSAT problems. However, its application to the closely related Weighted Constraint Satisfaction Problem (WCSP) framework has shown only preliminary promise. The core issue lies in the "core interchangeability" phenomenon within WCSP, where many similar cores (representing different trade-offs) can lead to an exponential number of iterations for the HS algorithm, rendering it computationally infeasible. This paper aims to bridge this gap by providing a deeper theoretical understanding of HS for WCSP and proposing practical methods to overcome its limitations.

Methods

The authors introduce two novel cost-function merging techniques to address core interchangeability:

  • Symbolic Merging: This method treats weights as symbols, merging cost functions based on the counts of specific weights appearing in their domains. It's designed to handle "symbolic core interchangeability."
  • Numeric Merging: This is a stronger form of merging that treats weights as numerical values. It merges cost functions by summing their weights, aiming to resolve "numeric core interchangeability."

The paper also provides a theoretical framework for analyzing the performance of HS-WCSP by bounding the number of iterations. They define "distinguished cores" and use them to establish lower bounds on iterations. They also analyze "maximal cores" to derive upper bounds for a specific variant of HS-WCSP (HS-WCSP-max).

Datasets

The paper uses two artificial benchmark problems for theoretical analysis and empirical evaluation:

  • GreaterThan Problem (PGT(n)): A WCSP designed to exhibit core interchangeability.
  • AllDiff Problem (PAD(n)): Another WCSP specifically constructed to demonstrate the limitations of HS-WCSP.

For empirical validation, they also use the Spot5 benchmark instances.

Key Insights and Ideas

  • Core Interchangeability is the Bottleneck: The paper clearly demonstrates that the exponential blow-up in HS-WCSP iterations stems from the redundant discovery of similar cores, a problem they term "core interchangeability."
  • Merging as a Solution: Cost-function merging is presented as a direct and effective way to combat core interchangeability by creating a more compact representation of the problem's core structure.
  • Symbolic vs. Numeric Merging: The distinction between symbolic and numeric merging is crucial. Symbolic merging is sufficient for certain types of symmetry, but numeric merging is necessary for more complex numerical symmetries, offering a stronger reduction in iterations.
  • Theoretical Bounds Align with Practice: The theoretical bounds derived for the artificial problems (exponential for original, sub-exponential/linear for symbolic, constant for numeric) are shown to be remarkably accurate in empirical tests.
  • Heuristic Merging is Practical: Even without perfect knowledge of core interchangeability, a heuristic approach using tree-decompositions to identify clusters of cost functions for merging proves effective on real-world benchmark problems.

Key Results

  • Theoretical Reductions:
    • For the GreaterThan problem, HS-WCSP iterations are reduced from exponential to a constant number using numeric merging.
  • For the AllDiff problem, symbolic merging reduces iterations from exponential to linear, and numeric merging reduces it to a constant.
  • Empirical Validation:
    • Experiments on the GreaterThan and AllDiff problems confirm the theoretical predictions, showing significant speedups with merging. Numeric merging consistently yields the best performance for GreaterThan, while symbolic merging is highly effective for AllDiff.
  • On the Spot5 benchmark, cost-function merging (both symbolic and numeric) significantly outperforms the original formulation, solving more instances and doing so more efficiently. In many cases, it even surpasses a state-of-the-art solver (Toulbar2).

Limitations and Future Work

  • Limitations:
    • The theoretical analysis focuses on asymptotic behavior and may not fully capture the performance on small instances.
  • The cost of each iteration (especially with complex encodings like totalizers) can be significant, and the paper suggests that the current CES (Core Extraction Solver) implementation's cost can grow exponentially.
  • The heuristic for identifying clusters of cost functions for merging is based on tree-decompositions, which might not always identify the most optimal clusters.
  • Future Work:
    • Explore better implementations of the Core Extraction Solver (CES), potentially by improving SAT encodings or moving to different solving paradigms.
  • Investigate alternative heuristics beyond tree-decompositions for identifying appropriate cost-function clusters.
  • Extend empirical evaluations to a wider range of benchmark instances to further validate the effectiveness of cost-function merging.
  • The authors suggest that merging can be beneficial even when core interchangeability is not strictly present, but rather when cost functions "disagree" in a less structured way. Further exploration of this aspect is warranted.

Summary updated

BibTeX
@inproceedings{larrosa2024theoretical,
  author = {Javier Larrosa and Conrado Martínez and Emma Rollon},
  title = {{Theoretical and Empirical Analysis of Cost-Function Merging for Implicit Hitting Set WCSP Solving}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2024},
  doi = {10.1609/aaai.v38i8.28644},
}

Loading related content...

Figure