Interpretable Algorithm Selection via Multi-Objective Evolutionary Decision Trees

The Algorithm Selection Problem (ASP) aims to identify the most suitable algorithm for a given problem instance. This paper introduces MODT-ASP, a multi-objective evolutionary framework designed to construct interpretable decision trees for ASP. The proposed approach overcomes the limitations of existing methods, such as scalability constraints and the challenge of balancing competing objectives, by employing a customized encoding scheme and specialized genetic operators. These components effectively explore trade-offs between predictive accuracy and model complexity via Pareto optimization. An enhanced version, EMODT-ASP, further integrates refined control mechanisms to improve generalization. Comprehensive experimental evaluations demonstrate the robustness and effectiveness of the proposed framework. In a large-scale linear programming benchmark comprising 1,004 problems and 532 algorithms, MODT-ASP consistently produces high-quality Pareto-optimal solutions. Furthermore, in the Open Algorithm Selection Challenge (OASC), evaluated across 8 heterogeneous scenarios, the proposed approach achieves third place overall, outperforming 6 of 8 OASC competitors and all 3 IP+VND variants reported in the recent literature. These results confirm its strong cross-domain applicability.