Optimal Decision Trees for Feature Based Parameter Tuning: Integer Programming Model and VNS Heuristic

In this paper we propose a hybrid approach for the Feature Based Parameter Tuning Problem (FBPTP) of Mixed-Integer Programming (MIP) solvers. These solvers are complex programs composed of many procedures whose execution is embedded in the Branch-and-Bound framework and their execution can be configured by setting different parameters. The diversity of models that can be formulated as MIP problems can be exploited to devise better parameter settings for groups of problems, considering lessons learned from previous experiments. Decision trees can be used to define the best parameter settings for different problem types. However the construction of optimal decision trees is a NP-Hard problem. Thus, we propose an Integer Programming Model to construct optimal decision trees for FBPTP. A Variable Neighborhood Search heuristic is employed to accelerate the production of high quality solutions. Encouraging computational results were obtained for the open source MIP solver COIN-OR CBC: executions in the test sets considering decisions based on our decision trees built using training sets prove the effectiveness of the proposed method compared to default settings, an improvement of 7% in solver's performance was obtained both in execution times as well in the number of solved instances.