Using Bandit Algorithms for Adaptive Algorithmic Decisions in SCIP

Abstract

Modern MIP solvers like SCIP implement numerous algorithmic components that use very similar techniques to find solutions. A classic example are the expensive class of Large Neighborhood Search (LNS) primal heuristics, which solve an auxiliary MIP problem and translate potential solutions back into the original problem. Since little can be predicted a priori about the performance of such heuristics for a particular instance, it is desirable for the solver to quickly adapt its choice of LNS techniques to the instance at hand. In this talk, I will first present the Adaptive Large Neighborhood Search (ALNS), which combines different LNS techniques into a single heuristic with an adaptive neighborhood selection, guided by different randomized algorithms for the Multi-Armed Bandit Problem. Second, I will discuss analogous selection problems for two other interesting classes of solving components, namely diving heuristics and the LP pricing strategy, where the goal for the LP pricing strategy is not to produce more solutions, but to be the fastest among its competitors. Experimental results confirm the learning success and the computational benefit of the ALNS framework, as well as the performance gain of an adaptive selection of the LP pricing strategy. Throughout the talk, I will give some implementation details about the involved plugins.

Date
Location
RWTH Aachen, Germany
Avatar
Gregor Hendel
Senior Engineer