Introduction
In the field of meta-algorithmics, the challenge of algorithm selection—identifying the most efficient algorithm for a specific problem instance—has traditionally treated software as a "black box." Selection models typically rely on historical performance data and problem instance characteristics, remaining entirely agnostic to the internal structure and implementation details of the algorithms themselves. This paper challenges that status quo, proposing that the source code of an algorithm contains vital "coding signatures" that can significantly improve performance prediction.
Methodology
The researchers moved away from building individual performance models for every algorithm in a portfolio. Instead, they developed a unified performance model that integrates two distinct data streams:
- Instance Features: Standard characteristics of the problem being solved.
- Algorithmic Features: Static software metrics extracted directly from the solver's source code.
To extract these algorithmic features, the authors utilized Metrix++, an open-source tool, to measure five key software engineering metrics: Cyclomatic Complexity (execution paths), Maxindent Complexity (logic depth), Lines of Code, Size in Bytes, and the Number of Files (modularity). By feeding these metrics into a single model for the entire portfolio, the system learns the relative strengths and weaknesses of different solvers based on their structural differences.
Experimental Results
The approach was evaluated using the ASlib benchmark library, covering scenarios in Boolean Satisfiability (SAT), the Traveling Salesperson Problem (TSP), and Machine Learning tool selection. Success was measured using the Misclassification Penalty (MCP)—the performance cost incurred by selecting a sub-optimal algorithm.
The results demonstrate that software metrics are powerful performance predictors. In the TSP-LION2015 scenario, the inclusion of source code features improved the MCP by a staggering 82%. Across the four scenarios where the method was successful, the researchers observed an average relative improvement of 34.07%. As shown in the heatmap above, the combined feature set (instance and solver) outperformed instance-only features in four out of the seven tested scenarios.
Discussion and Future Work
While the results are promising, the approach is not a universal solution. In three of the seven scenarios, performance slightly decreased, suggesting that basic static metrics like "lines of code" may be too noisy for certain algorithmic domains. This indicates that the relationship between code structure and computational performance is domain-dependent.
Future work will explore more sophisticated software analysis techniques. Moving beyond basic static metrics, the authors suggest that granular source code analysis or dynamic analysis—observing how code behaves during execution—could further refine the selection process and provide even deeper insights into the "black box" of algorithmic performance.
Summary updated