Mathematical Programming Computation, Volume 6, Issue 1, March 2014


Timo Berthold

This article introduces rens, the relaxation enforced neighborhood search, a large neighborhood search algorithm for mixed integer nonlinear programs (MINLPs). It uses a sub-MINLP to explore the set of feasible roundings of an optimal solution ¯ x of a linear or nonlinear relaxation. The sub-MINLP is constructed by fixing integer variables x j with ¯ x j ? Z and bounding the remaining integer variables to x j ? {¯x j ,  ¯x j }. We describe two different applications of rens: as a standalone algorithm to compute an optimal rounding of the given starting solution and as a primal heuristic inside a complete MINLP solver. We use the former to compare different kinds of relaxations and the impact of cutting planes on the so-called roundability of the corresponding optimal solutions. We further utilize rens to analyze the performance of three rounding heuristics implemented in the branch-cut-and-price framework scip. Finally, we study the impact of rens when it is applied as a primal heuristic inside scip. All experiments were performed on three publicly available test sets of mixed integer linear programs (MIPs), mixed integer quadratically constrained programs (MIQCPs), and MINLPs, using solely software which is available in source code. It turns out that for these problem classes 60 to 70% of the instances have roundable relaxation optima and that the success rate of rens does not depend on the percentage of fractional variables. Last but not least, rens applied as primal heuristic complements nicely with existing primal heuristics in scip.

Full Text: PDF

Imprint and privacy statement

For the imprint and privacy statement we refer to the Imprint of ZIB.
© 2008-2023 by Zuse Institute Berlin (ZIB).