Explainable Algorithm Selection for the Capacitated Lot Sizing Problem

Algorithm selection is a class of meta-algorithms that has emerged as a crucial approach for solving complex combinatorial optimization problems. Successful algorithm selection involves navigating a diverse landscape of solvers, each designed with distinct heuristics and search strategies. It is a classification problem in which statistical features of a problem instance are used to select the algorithm that should tackle it most efficiently. However, minimal attention has been given to investigating algorithm selection decisions. This work presents a framework for iterative feature selection and explainable multi-class classification in Algorithm Selection for the Capacitated Lot Sizing Problem (CLSP). The CLSP is a combinatorial optimization problem widely studied with important industrial applications. The framework reduces the features considered by the machine learning approach and uses SHAP analysis to investigate their contribution to the selection. The analysis shows which instance type characteristics positively affect the relative performance of a heuristic. The approach can be used to improve the algorithm selection’s transparency and inform the developer of an algorithm’s weak and strong points. The experimental analysis shows that the framework selector provides valuable insights with a narrow optimality gap close to a parallel deployment of the heuristic set that generalises well to instances considerably bigger than the training ones.