Automated Feature Extraction for Algorithm Selection in Combinatorial Optimization

Given a combinatorial problem, there could be multiple ways to model it into a constraint optimization model that could be solved by a solver. Choosing the right combination of a model and a target solver can have significant impact on the effectiveness of the solving process. Furthermore, the choice of the best combination of constraint model and solver can be instance-dependent, i.e., there may not exist a single combination that works best for all instances of the same problem. In this paper, we consider the task of building machine learning models to automatically select the best combination for a problem instance. A critical part of the learning process is to define instance features, which serve as input to the selection model. Our contribution is the automatic learning of instance features directly from the high-level representation of a problem instance using a transformer encoder. We evaluate the performance of our approach using the Essence modelling language with a case study involving three different problem classes.