RENS

  • 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.

Download full text files

Export metadata

Additional Services

Share in Twitter Search Google Scholar
Metadaten
Author:Timo Berthold
DOI:https://doi.org/10.1007/s12532-013-0060-9
ISSN:1867-2949
Parent Title (English):Mathematical Programming Computation
Subtitle (English):The optimal rounding
Publisher:Springer Science and Business Media LLC
Document Type:Article
Language:English
Year of Completion:2013
Tag:Software; Theoretical Computer Science
Volume:6
Issue:1
Page Number:22
First Page:33
Last Page:54
Mathematical Programming Computation :MPC 2014 - Issue 1
Verstanden ✔
Diese Webseite verwendet technisch erforderliche Session-Cookies. Durch die weitere Nutzung der Webseite stimmen Sie diesem zu. Unsere Datenschutzerklärung finden Sie hier.