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

Online Learning for Scheduling MIP Heuristics

  • Mixed Integer Programming (MIP) is NP-hard, and yet modern solvers often solve large real-world problems within minutes. This success can partially be attributed to heuristics. Since their behavior is highly instance-dependent, relying on hard-coded rules derived from empirical testing on a large heterogeneous corpora of benchmark instances might lead to sub-optimal performance. In this work, we propose an online learning approach that adapts the application of heuristics towards the single instance at hand. We replace the commonly used static heuristic handling with an adaptive framework exploiting past observations about the heuristic’s behavior to make future decisions. In particular, we model the problem of controlling Large Neighborhood Search and Diving – two broad and complex classes of heuristics – as a multi-armed bandit problem. Going beyond existing work in the literature, we control two different classes of heuristics simultaneously by a single learning agent. We verify our approach numerically and show consistent node reductions over the MIPLIB 2017 Benchmark set. For harder instances that take at least 1000 seconds to solve, we observe a speedup of 4%.
Metadaten
Author:Antonia ChmielaORCiD, Ambros GleixnerORCiD, Pawel Lichocki, Sebastian Pokutta
Document Type:In Proceedings
Parent Title (English):Integration of Constraint Programming, Artificial Intelligence, and Operations Research
Volume:13884
First Page:114
Last Page:123
Series:Lecture Notes in Computer Science
Publisher:Springer, Cham
Year of first publication:2023
Preprint:urn:nbn:de:0297-zib-89142
DOI:https://doi.org/10.1007/978-3-031-33271-5_8
Accept ✔
Diese Webseite verwendet technisch erforderliche Session-Cookies. Durch die weitere Nutzung der Webseite stimmen Sie diesem zu. Unsere Datenschutzerklärung finden Sie hier.