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.
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.
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