1520
eng
reportzib
0
2012-04-26
2012-04-26
--
RENS – the optimal rounding
This article introduces RENS, the relaxation enforced neighborhood search, a large neighborhood search algorithm for mixed integer nonlinear programming (MINLP) that 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 in Z and bounding the remaining integer variables to x_j in {floor(x'_j), ceil(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 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 publically 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 root node heuristics in SCIP and improves the overall performance.
1438-0064
urn:nbn:de:0297-zib-15203
Timo Berthold
Timo Berthold
ZIB-Report
12-17
eng
uncontrolled
Primal Heuristic
eng
uncontrolled
Mixed-Integer Nonlinear Programming
eng
uncontrolled
Large Neighborhood Search
eng
uncontrolled
Mixed-Integer Quadratically Constrained Programming
eng
uncontrolled
Mixed-Intger Programming
Optimization
Mixed integer programming
Quadratic programming
Nonlinear programming
Approximation methods and heuristics
Mathematical Optimization
Berthold, Timo
https://opus4.kobv.de/opus4-zib/files/1520/rens.pdf
https://opus4.kobv.de/opus4-zib/files/1520/ZR_12_17_rev.pdf