ReACTR: Realtime Algorithm Configuration through Tournament Rankings

Tadhg Fitzgerald, Yuri Malitsky, Barry O'SullivanIJCAI 2015

ReACTR: Realtime Algorithm Configuration through Tournament Rankings

Introduction

High-performance solvers for combinatorial problems, such as Boolean Satisfiability (SAT) or Mixed-Integer Programming (MIP), typically feature hundreds of tunable parameters. Identifying the optimal configuration for a specific problem domain is a significant challenge. Traditional Automated Algorithm Configuration (AAC) tools like SMAC or ParamILS operate on a "train-once, use-forever" paradigm, requiring extensive offline compute time and static benchmark sets. However, in dynamic environments like high-frequency ad auctions or evolving logistics, problem characteristics shift over time, and "offline" windows are non-existent. ReACTR addresses this by providing an online, realtime framework that configures algorithms on-the-fly as problem instances arrive.

Methodology: Tournament-Based Configuration

ReACTR treats parameter configurations as competitors in a tournament. To manage the inherent noise in solver performance—where a fast solve might result from an easy instance rather than an efficient configuration—ReACTR utilizes the TrueSkill ranking system.

Bayesian Ranking with TrueSkill

TrueSkill, originally developed for matchmaking in competitive gaming, tracks both a "skill" level ($μ$) and an "uncertainty" level ($σ$) for each configuration. This Bayesian approach allows ReACTR to statistically distinguish between consistently high performers and those that were merely "lucky" on a small sample of instances. As shown in Figure 1, TrueSkill's ability to model uncertainty leads to lower cumulative solving times compared to alternative systems like Glicko.

Comparison of cumulative solving time using TrueSkill versus Glicko ranking systems.

Sampling and Pool Maintenance

When a new instance arrives, ReACTR selects a subset of configurations to run in parallel. Empirical testing identified a "Top 2 + Random" strategy—running the two highest-ranked configurations alongside four random ones—as the optimal balance between exploitation of known good settings and exploration of the parameter space. To maintain a high-quality pool, ReACTR periodically "cleans" configurations that are statistically likely to be underperformers and replenishes the pool using a crossover operator, which combines parameters from top-ranked "parents" to create new "child" configurations.

Experimental Results

The authors evaluated ReACTR across three benchmarks: Combinatorial Auctions (Regions and Arbitrary datasets) using the IBM CPLEX optimizer, and Circuit Fuzz (SAT) using the Lingeling solver.

Rapid Convergence and Superior Performance

A key strength of ReACTR is its ability to improve performance without adding overhead. By running configurations in parallel and terminating losing runs once the first configuration finishes, the learning process is essentially "free" given available CPU cores.

Rolling average solving time across three benchmarks: (a) Circuit Fuzz, (b) Arbitrary CA, and (c) Regions CA.

As illustrated in Figure 6, ReACTR (specifically the "Merged" variant which utilizes prior knowledge) consistently achieves lower rolling average solving times than solver defaults. Notably, in the "Regions" auction dataset, ReACTR Merged achieved a total solving time of 88,000 seconds, significantly outperforming the industry-standard SMAC tool (102,000 seconds), despite SMAC being granted 48 hours of offline training. Even starting from zero knowledge ("ReACTR Test"), the system converges rapidly to high-performing configurations.

Conclusion

ReACTR demonstrates that online, tournament-based algorithm configuration is not only feasible but can outperform state-of-the-art offline tools. By treating uncertainty as a first-class citizen through TrueSkill and employing evolutionary crossover for pool replenishment, ReACTR provides a robust, "green," and time-efficient solution for tuning solvers in dynamic, real-world environments.

Summary updated

BibTeX
@inproceedings{fitzgerald2015reactr,
  author = {Tadhg Fitzgerald and Yuri Malitsky and Barry O'Sullivan},
  title = {{ReACTR: Realtime Algorithm Configuration through Tournament Rankings}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2015},
}
Figure