PACE 2026 Solver Suite
Three specialised C++ solvers for the heuristic, exact and lower-bound tracks of the PACE Maximum Agreement Forest Challenge.
THE CHALLENGE
What needed to change.
Maximum Agreement Forest asks for a minimum-component forest shared by rooted evolutionary trees. The underlying combinatorial search grows rapidly with tree size and disagreement, so competitive solvers need strong structural reductions, useful bounds and carefully selected search strategies—not just more compute.
THE APPROACH
How I structured the solution.
I engineered a three-track C++ solver suite around shared phylogenetic structures and track-specific objectives. The system combines subtree and chain kernelisation, cluster decomposition, adaptive routing, greedy and anytime improvement, exact search, certificate-aware validation, and SAT/ILP-backed optimisation through CaDiCaL and HiGHS.
THE SOLVER FAMILY
One problem. Three competitive objectives.
Each track demands a different notion of success, so each repository has a distinct job inside the suite.
Heuristic track
↗MAFia
Find strong feasible forests quicklyAn anytime heuristic solver that routes instances through structural reductions, cluster-aware subproblems and multiple improvement strategies while preserving a valid incumbent solution.
- Greedy 1/2-approximation
- Kernel reductions
- Adaptive portfolios
- Structured cut repair
Exact track
↗ClusterLuck
Prove an optimal agreement forestA specialised exact package that dispatches between two-tree and many-tree cores, combining combinatorial search with SAT and mathematical-optimisation machinery.
- Exact search
- CaDiCaL SAT
- HiGHS optimisation
- Certified validation
Lower-bound track
↗CutSetGo
Certify how good any solution can beA lower-bound solver built from approximation, kernel and cluster signals, with instance-aware routing and timeout-safe output for competition execution.
- Lower-bound construction
- Approximation
- Cluster analysis
- Runtime-aware routing
THE OUTCOME
What the work demonstrated.
The result is a complementary solver family: MAFia searches aggressively for high-quality feasible forests, ClusterLuck targets exact solutions, and CutSetGo computes defensible lower bounds. Together they demonstrate end-to-end algorithm engineering under strict correctness and runtime constraints.