In this paper, we study the behavior of feasible rounding approaches for mixed-integer linear and nonlinear optimization problems (MILP and MINLP, respectively) when integrated into tree search of branch-and-bound. Our research addresses two important aspects. First, we develop insights into how an (enlarged) inner parallel set, which is the main component for feasible rounding approaches, behaves when we move down a search tree. Our theoretical results show that the number of feasible points obtainable from the inner parallel set is nondecreasing with increasing depth of the search tree. Thus, they hint at the potential benefit of integrating feasible rounding approaches into branch-and-bound methods. Second, based on those insights, we develop a novel primal heuristic for MILPs that fixes variables in a way that promotes large inner parallel sets of child nodes. Our computational study shows that combining feasible rounding approaches with the presented diving ideas yields a significant improvement over their application in the root node. Moreover, the proposed method is able to deliver best solutions for SCIP for a significant share of problems which hints at its potential to support solving MILPs.
Citation
Optimization Online, Preprint-ID 2021-10-8630, 2021