MaxSAT by Improved Instance-Specific Algorithm Configuration

Carlos Ansótegui, Yuri Malitsky, Meinolf SellmannAAAI 2014 · DOI

Abstract

This paper introduces ISAC+, a hybrid meta-algorithmic framework that integrates instance-specific algorithm tuning with advanced portfolio selection. By decoupling the configuration generation process from the runtime selection mechanism, the authors created a robust solver system. Evaluated on SAT and MaxSAT benchmarks, ISAC+ demonstrated significant performance gains, ultimately winning six out of eleven categories at the 2013 MaxSAT Evaluation.

Introduction

In combinatorial search, the "No Free Lunch" theorem holds true: no single solver excels across all problem domains. A solver optimized for industrial circuit verification often performs poorly on random mathematical puzzles. This challenge is particularly acute in MaxSAT—the optimization variant of the Boolean Satisfiability (SAT) problem—where solvers must satisfy all "hard" clauses while maximizing the weight of satisfied "soft" clauses.

Historically, researchers have addressed this using two distinct strategies: Algorithm Portfolios, which use machine learning to select the best solver from a pre-defined set, and Algorithm Tuning, which optimizes the parameters of a single flexible solver for specific problem classes. The authors identify a critical gap: these methods are rarely combined effectively. Traditional instance-specific configuration often "locks" an instance into a cluster, limiting the flexibility that modern portfolio selectors provide.

Methodology: The ISAC+ Framework

The authors propose ISAC+ (or "Portfolio Tuner"), which improves upon the original Instance-Specific Algorithm Configuration (ISAC) through a three-stage process:

  1. Clustering and Tuning: A training set of instances is grouped into clusters based on mathematical features. For each cluster, a configurator—specifically the Gender-based Genetic Algorithm (GGA)—identifies optimal parameters for a base solver (e.g., qMaxSAT).
  2. Portfolio Expansion: The system generates a diverse portfolio consisting of the original base solvers and all specialized configurations produced during the tuning stage.
  3. Decoupled Selection: Unlike traditional ISAC, which assigns new instances to a fixed cluster, ISAC+ employs a state-of-the-art portfolio selector called Cost-Sensitive Hierarchical Clustering (CSHC). This selector evaluates the entire expanded portfolio to pick the best configuration for a specific instance, regardless of its original cluster.
The algorithmic structure of the ISAC framework, serving as the foundation for the ISAC+ improvements.

To adapt this for MaxSAT, the authors introduced new feature computation methods, incorporating statistics such as the minimum, maximum, average, and standard deviation of clause weights alongside standard SAT features.

Experimental Evaluation

The methodology was rigorously tested across several benchmarks, including the "HAND" (Crafted) and "RAND" (Random) SAT sets, and the 2012 MaxSAT Evaluation data. The MaxSAT benchmarks covered four primary categories: Plain MaxSAT (MS), Partial MaxSAT (PMS), Weighted MaxSAT (WMS), and Weighted Partial MaxSAT (WPMS).

Key Results

ISAC+ demonstrated a remarkable ability to close the performance gap between existing state-of-the-art methods and the "Virtual Best Solver" (VBS)—a theoretical oracle that always picks the best solver. On SAT benchmarks, ISAC+ closed approximately 30-37% of this gap.

In the MaxSAT domain, the results were even more pronounced. In the Partial MaxSAT (PMS) Crafted category, the best single solver (BS) solved 82.31% of instances. ISAC+ increased this to 98.46%, nearly reaching the theoretical limit of the VBS.

Performance metrics for the PMS Crafted benchmark, demonstrating ISAC+'s dominance over base solvers and previous ISAC iterations.

The real-world efficacy of the framework was confirmed at the 2013 MaxSAT Evaluation, where ISAC+ portfolios won 6 out of 11 categories. Cross-validation further showed that ISAC+ consistently outperformed the previous ISAC-MSC approach, particularly in complex categories like PMS MIX, where it solved significantly more instances than the base solvers.

Conclusion and Future Work

The primary insight of this research is that the mechanism used to generate a configuration (clustering) need not be the same as the mechanism used to select it (portfolio selection). By treating tuned configurations as "specialists" within a broader portfolio, ISAC+ achieves superior robustness.

Future work will focus on deeper feature engineering to better capture the structure of weighted constraints, as current features remain largely SAT-centric. Additionally, while the offline training cost of ISAC+ is high due to the extensive tuning required, the authors argue that the resulting online performance gains justify the initial computational investment.

Summary updated

BibTeX
@inproceedings{ansotegui2014maxsat,
  author = {Carlos Ansótegui and Yuri Malitsky and Meinolf Sellmann},
  title = {{MaxSAT by Improved Instance-Specific Algorithm Configuration}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2014},
  doi = {10.1609/aaai.v28i1.9128},
}
Figure