Overview Statistic: PDF-Downloads (blue) and Frontdoor-Views (gray)

Adaptive Algorithmic Behavior for Solving Mixed Integer Programs Using Bandit Algorithms

Please always quote using this URN: urn:nbn:de:0297-zib-69563
  • 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.

Download full text files

Export metadata

Additional Services

Share in Twitter Search Google Scholar Statistics - number of accesses to the document
Metadaten
Author:Gregor HendelORCiD, Matthias MiltenbergerORCiD, Jakob WitzigORCiD
Document Type:ZIB-Report
Tag:mixed integer programming; multi armed bandit; primal heuristics
MSC-Classification:90-XX OPERATIONS RESEARCH, MATHEMATICAL PROGRAMMING
Date of first Publication:2018/07/20
Series (Serial Number):ZIB-Report (18-36)
ISSN:1438-0064
Licence (German):License LogoCreative Commons - CC BY - Namensnennung 4.0 International
Accept ✔
Diese Webseite verwendet technisch erforderliche Session-Cookies. Durch die weitere Nutzung der Webseite stimmen Sie diesem zu. Unsere Datenschutzerklärung finden Sie hier.