Adaptive Algorithmic Behavior for Solving Mixed Integer Programs Using Bandit Algorithms

Gregor Hendel (), Matthias Miltenberger () and Jakob Witzig ()
Additional contact information
Gregor Hendel: Zuse Institute Berlin
Matthias Miltenberger: Zuse Institute Berlin
Jakob Witzig: Zuse Institute Berlin

A chapter in Operations Research Proceedings 2018, 2019, pp 513-519 from Springer

Abstract: 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 (search for similar items in EconPapers)
Date: 2019
References: Add references at CitEc
Citations:

There are no downloads for this item, see the EconPapers FAQ for hints about obtaining it.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:oprchp:978-3-030-18500-8_64

Ordering information: This item can be ordered from
http://www.springer.com/9783030185008

DOI: 10.1007/978-3-030-18500-8_64

Access Statistics for this chapter

More chapters in Operations Research Proceedings from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().