Data Mining Approach for Feature Based Parameter Tunning for Mixed-Integer Programming Solvers

摘要

Integer Programming (IP) is the most successful technique for solving hard combinatorial optimization problems. Modern IP solvers are very complex programs composed of many different procedures whose execution is embedded in the generic Branch & Bound framework. The activation of these procedures as well the definition of exploration strategies for the search tree can be done by setting different parameters. Since the success of these procedures and strategies in improving the performance of IP solvers varies widely depending on the problem being solved, the usual approach for discovering a good set of parameters considering average results is not ideal. In this work we propose a comprehensive approach for the automatic tuning of Integer Programming solvers where the characteristics of instances are considered. Computational experiments in a diverse set of 308 benchmark instances using the open source COIN-OR CBC solver were performed with different parameter sets and the results were processed by data mining algorithms. The results were encouraging: when trained with a portion of the database the algorithms were able to predict better parameters for the remaining instances in 84% of the cases. The selection of a single best parameter setting would provide an improvement in only 56% of instances, showing that great improvements can be obtained with our approach.