DINS, a MIP improvement heuristic. We introduce Distance Induced Neighbourhood Search (DINS), a MIP improvement heuristic that tries to find improved MIP feasible solutions from a given MIP feasible solution. DINS is based on a variation of local search that is embedded in an exact MIP solver, namely a branch-and-bound or a branch-and-cut MIP solver. The key idea is to use a distancemetric between the linear programming relaxation optimal solution and the current MIP feasible solution to define search neighbourhoods at different nodes of the search tree generated by the exact solver. DINS considers each defined search neighbourhood as a new MIP problem and explores it by an exact MIP solver with a certain node limit. On a set of standard benchmark problems, DINS outperforms the MIP improvement heuristics Local Branching due to Fischetti and Lodi and Relaxation Induced Neighbourhood Search due to Danna, Rothberg, and Pape, as well as the generic commercial MIP solver Cplex.
Keywords for this software
References in zbMATH (referenced in 8 articles )
Showing results 1 to 8 of 8.
- Gamrath, Gerald; Berthold, Timo; Heinz, Stefan; Winkler, Michael: Structure-driven fix-and-propagate heuristics for mixed integer programming (2019)
- Munguía, Lluís-Miquel; Ahmed, Shabbir; Bader, David A.; Nemhauser, George L.; Shao, Yufen: Alternating criteria search: a parallel large neighborhood search algorithm for mixed integer programs (2018)
- Berthold, Timo; Hendel, Gregor: Shift-and-propagate (2015)
- Berthold, Timo: RENS. The optimal rounding (2014)
- Berthold, Timo; Gleixner, Ambros M.: Undercover: a primal MINLP heuristic exploring a largest sub-MIP (2014)
- Camargo, Victor C. B.; Toledo, Franklina M. B.; Almada-Lobo, Bernardo: HOPS -- Hamming-Oriented Partition Search for production planning in the spinning industry (2014)
- Sacchi, Luís Henrique; Armentano, Vinícius Amaral: A computational study of parametric tabu search for 0-1 mixed integer programs (2011)
- Ghosh, Shubhashis: DINS, a MIP improvement heuristic (2007)