Adaptive Algorithmic Behavior for Solving Mixed Integer Programs Using Bandit Algorithms

accepted for publication
  • State-of-the-art solvers for mixed integer programs (MIP) govern a variety of algorithmic components. Ideally, the solver adaptively learns to concentrate its computational budget on those components that perform well on a particular problem, especially if they are time consuming. We focus on three such algorithms, namely the classes of large neighborhood search and diving heuristics as well as Simplex pricing strategies. For each class we propose a selection strategy that is updated based on the observed runtime behavior, aiming to ultimately select only the best algorithms for a given instance. We review several common strategies for such a selection scenario under uncertainty, also known as Multi Armed Bandit Problem. In order to apply those bandit strategies, we carefully design reward functions to rank and compare each individual heuristic or pricing algorithm within its respective class. Finally, we discuss the computational benefits of using the proposed adaptive selection within the SCIP Optimization Suite on publicly available MIP instances.
Metadaten
Author:Gregor HendelORCiD, Matthias MiltenbergerORCiD, Jakob WitzigORCiD
Document Type:In Proceedings
Parent Title (English):OR 2018: International Conference on Operations Research
Series:Operations Research 2018 Proceedings
Year of first publication:2018
Preprint:urn:nbn:de:0297-zib-69563