Feature-Based Algorithm Selection for Mixed Integer Programming

Please always quote using this URN: urn:nbn:de:0297-zib-68362
  • Mixed integer programming is a versatile and valuable optimization tool. However, solving specific problem instances can be computationally demanding even for cutting-edge solvers. Such long running times are often significantly reduced by an appropriate change of the solver's parameters. In this paper we investigate "algorithm selection", the task of choosing among a set of algorithms the ones that are likely to perform best for a particular instance. In our case, we treat different parameter settings of the MIP solver SCIP as different algorithms to choose from. Two peculiarities of the MIP solving process have our special attention. We address the well-known problem of performance variability by using multiple random seeds. Besides solving time, primal dual integrals are recorded as a second performance measure in order to distinguish solvers that timed out. We collected feature and performance data for a large set of publicly available MIP instances. The algorithm selection problem is addressed by several popular, feature-based methods, which have been partly extended for our purpose. Finally, an analysis of the feature space and performance results of the selected algorithms are presented.

Download full text files

Export metadata

Additional Services

Share in Twitter Search Google Scholar
Metadaten
Author:Alexander Georges, Ambros GleixnerORCiD, Gorana Gojic, Robert Lion GottwaldORCiD, David Haley, Gregor HendelORCiD, Bartlomiej Matejczyk
Document Type:ZIB-Report
Tag:algorithm selection; mixed integer programming
MSC-Classification:90-XX OPERATIONS RESEARCH, MATHEMATICAL PROGRAMMING
Date of first Publication:2018/04/10
Series (Serial Number):ZIB-Report (18-17)
ISSN:1438-0064