Optimization Online


Adaptive Algorithmic Behavior for Solving Mixed Integer Programs Using Bandit Algorithms

Gregor Hendel(hendel***at***zib.de)
Matthias Miltenberger(miltenberger***at***zib.de)
Jakob Witzig(witzig***at***zib.de)

Abstract: 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.

Keywords: mixed integer programming, primal heuristics, multi armed bandit

Category 1: Integer Programming ((Mixed) Integer Linear Programming )

Citation: July 2018, ZIB-Report 18-36, Zuse Institute Berlin, Takustr. 7, 14195 Berlin, Germany

Download: [PDF]

Entry Submitted: 07/20/2018
Entry Accepted: 07/20/2018
Entry Last Modified: 07/20/2018

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society