Timo Berthold: The role of primal heuristics in MIP (and MINLP) solvers

Date: 2023-07-05

Time: 09:00 - 10:00

Speaker

Timo Berthold, FICO/The Zuse Institute Berlin

Abstract

Primal heuristics play a fundamental role in MIP solver development, but their real value only shows at a second glance. We will discuss the benefits of primal heuristics in MIP solvers, how we can measure their impact, and why they might be even more crucial for MINLP solvers. In this presentation, we will also describe various types of primal heuristics, including rounding heuristics, diving heuristics, sub-MIP heuristics, and local search-based heuristics, highlighting their individual strengths and limitations. We will focus on integrating primal heuristics within MIP and MINLP solvers, illustrating how these techniques can be seamlessly combined with other solution strategies such as branch-and-bound, cutting planes, and constraint propagation. The efficacy of primal heuristics will be demonstrated through empirical studies on MIP and MINLP benchmarks, showcasing their impact on solving large-scale optimization problems within a reasonable time.