Exploring relaxation induced neighborhoods to improve MIP solutions

By Emilie Danna, Edward E. Rothberg, Claude Le Pape. Mathematical programming, 2005

599 citations recorded by the source corpus.

Subfields: Computational Theory and Mathematics, Computer Networks and Communications, Industrial and Manufacturing Engineering

View Paper: https://www.semanticscholar.org/paper/74e86f325ddfb08f2f79b488ebfac2a43fd5e529

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Computational Theory and Mathematics

In Computer Networks and Communications

In Industrial and Manufacturing Engineering

Citations in the corpus

Integer-Programming Software Systems (2005, background): “Fortunately, several researchers have produced promising computational results using novel ideas, such as local branching [25] and its variants [17].”
Mixed-integer nonlinear optimization*† (2013, methodology): “An incumbent solution may additionally be used for “guided dives” (Danna et al., 2005), that is, selecting a child node during a dive.”
Combining Metaheuristics and Exact Algorithms in Combinatorial Optimization: A Survey and Classification (2005, methodology): “[10] present an approach called Relaxation Induced Neighborhood Search (RINS) in order to explore the neighborhoods of promising MIP”
SCIP: solving constraint integer programs (2009, background): “Other heuristics without special support in SCIP include local search heuristics like tabu search [54], rounding heuristics which try to round the current fractional LP solution to a feasible integral solution, and improvement heuristics like local branching [48] or RINS [40], which try to generate ”
Integer and Combinatorial Optimization (2013, background): “Achtenberg and Berthold (2007), Danna et al. (2005), Fischetti et al. (2009), and Rothberg (2007) provide descriptions of heuristics built into current packages.”
The feasibility pump (2005, background): “…192 3312 [8] manpower4 10009 10008 23914 [22] B1C1S1 3872 288 3904 [8] manpower4a 10009 10008 23866 [22] B2C1S1 3872 288 3904 [8] ljb2 771 681 1482 [6] sp97ic 12497 12497 1033 [8] ljb7 4163 3920 8133 [6] sp98ar 15085 15085 1435 [8] ljb9 4721 4460 9231 [6] sp98ic 10894 10894 825 [8] ljb10 5496…”
The SCIP Optimization Suite 3.2 (2016, methodology): “In contrast to other LNS heuristics for MIP like rins [22], rens [12], and Local Branching [27] they do not rely on a feasible or LP solution to define the neighborhood, but rather use two structures globally available in SCIP, the clique table and the variable bound graph.”
Hybrid metaheuristics in combinatorial optimization: A survey (2011, background): “In particular, including reverse local branching constraints to exclude already searched neighborhoods from consideration in further iterations has not turned out to be fruitful [105].”
Algorithms and Software for Convex Mixed Integer Nonlinear Programs (2012, methodology): “We note that several other heuristic principles could be used such as RINS [40] or Local Branching [50] but as far as we know, these have not been applied yet to (convex) MINLPs and we will not cover them here.”
Integer programming techniques for the nurse rostering problem (2014, methodology): “Considering the results obtained with recent uses of RINS heuristics [18], we proposed two different neighborhood structures that are based on the resolution of small partitions of the original problem to optimality.”
Active-constraint variable ordering for faster feasibility of mixed integer linear programs (2007, background): “Danna, Rothberg and Le Pape [ 10 ] recently introduced the Relaxation”
Primal Heuristics for Mixed Integer Programs (2006, methodology): “One year later, Danna, Rothberg, and Le Pape [21] presented Rins, also known as Relaxation Induced Neighborhood Search.”