TY - CHAP A1 - Chmiela, Antonia A1 - Gleixner, Ambros A1 - Lichocki, Pawel A1 - Pokutta, Sebastian T1 - Online Learning for Scheduling MIP Heuristics T2 - Integration of Constraint Programming, Artificial Intelligence, and Operations Research N2 - 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%. Y1 - 2023 U6 - https://doi.org/10.1007/978-3-031-33271-5_8 VL - 13884 SP - 114 EP - 123 PB - Springer, Cham ER - TY - CHAP A1 - Chmiela, Antonia A1 - Khalil, Elias B. A1 - Gleixner, Ambros A1 - Lodi, Andrea A1 - Pokutta, Sebastian T1 - Learning to Schedule Heuristics in Branch and Bound T2 - Thirty-fifth Conference on Neural Information Processing Systems, NeurIPS 2021 N2 - Primal heuristics play a crucial role in exact solvers for Mixed Integer Programming (MIP). While solvers are guaranteed to find optimal solutions given sufficient time, real-world applications typically require finding good solutions early on in the search to enable fast decision-making. While much of MIP research focuses on designing effective heuristics, the question of how to manage multiple MIP heuristics in a solver has not received equal attention. Generally, solvers follow hard-coded rules derived from empirical testing on broad sets of instances. Since the performance of heuristics is instance-dependent, using these general rules for a particular problem might not yield the best performance. In this work, we propose the first data-driven framework for scheduling heuristics in an exact MIP solver. By learning from data describing the performance of primal heuristics, we obtain a problem-specific schedule of heuristics that collectively find many solutions at minimal cost. We provide a formal description of the problem and propose an efficient algorithm for computing such a schedule. Compared to the default settings of a state-of-the-art academic MIP solver, we are able to reduce the average primal integral by up to 49% on a class of challenging instances. Y1 - 2021 ER - TY - CHAP A1 - Mexi, Gioni A1 - Besançon, Mathieu A1 - Bolusani, Suresh A1 - Chmiela, Antonia A1 - Hoen, Alexander A1 - Gleixner, Ambros T1 - Scylla: a matrix-free fix-propagate-and-project heuristic for mixed-integer optimization T2 - Proceedings of Conference of the Society for Operations Research in Germany Y1 - 2023 ER - TY - CHAP A1 - Gasse, Maxime A1 - Bowly, Simon A1 - Cappart, Quentin A1 - Charfreitag, Jonas A1 - Charlin, Laurent A1 - Chételat, Didier A1 - Chmiela, Antonia A1 - Dumouchelle, Justin A1 - Gleixner, Ambros A1 - Kazachkov, Aleksandr M. A1 - Khalil, Elias A1 - Lichocki, Pawel A1 - Lodi, Andrea A1 - Lubin, Miles A1 - Maddison, Chris J. A1 - Christopher, Morris A1 - Papageorgiou, Dimitri J. A1 - Parjadis, Augustin A1 - Pokutta, Sebastian A1 - Prouvost, Antoine A1 - Scavuzzo, Lara A1 - Zarpellon, Giulia A1 - Yang, Linxin A1 - Lai, Sha A1 - Wang, Akang A1 - Luo, Xiaodong A1 - Zhou, Xiang A1 - Huang, Haohan A1 - Shao, Shengcheng A1 - Zhu, Yuanming A1 - Zhang, Dong A1 - Quan, Tao A1 - Cao, Zixuan A1 - Xu, Yang A1 - Huang, Zhewei A1 - Zhou, Shuchang A1 - Binbin, Chen A1 - Minggui, He A1 - Hao, Hao A1 - Zhiyu, Zhang A1 - Zhiwu, An A1 - Kun, Mao T1 - The Machine Learning for Combinatorial Optimization Competition (ML4CO): results and insights T2 - Proceedings of Conference on Neural Information Processing Systems Y1 - 2022 ER -