In this paper, we propose two new diving heuristics for finding a feasible solution for a mixed integer programming problem, called variable neighbourhood (VN) diving and single neighbourhood (SN) diving, respectively. They perform systematic hard variable fixing (. diving) by exploiting the information obtained from a series of LP relaxations in order to generate a sequence of subproblems. | Yugoslav Journal of Operations Research 26 (2016), Number 2, 131–157 DOI: VARIABLE AND SINGLE NEIGHBOURHOOD DIVING FOR MIP FEASIBILITY ´ Jasmina LAZIC Brunel University, West London UB8 3PH, UK Mathematical Institute, Serbian Academy of Sciences and Arts ´ Raca TODOSIJEVIC LAMIH - Universit´e de Valenciennes, ISTV 2 Le Mont Houy, 59313 Valenciennes Cedex 9, France Mathematical Institute, Serbian Academy of Sciences and Arts Sa¨ıd HANAFI LAMIH - Universit´e de Valenciennes, ISTV 2 Le Mont Houy, 59313 Valenciennes Cedex 9, France CNRS, FRE 3304, 59313 Valenciennes Cedex 9, France Universit´e Lille Nord de France, 59000 Lille, France ´ Nenad MLADENOVIC Mathematical Institute, Serbian Academy of Sciences and Arts nenad@ Received: April 2014 / Accepted: September 2014 Abstract: In this paper, we propose two new diving heuristics for finding a feasible solution for a mixed integer programming problem, called variable neighbourhood (VN) diving and single neighbourhood (SN) diving, respectively. They perform systematic hard variable fixing (. diving) by exploiting the information obtained from a series of LP relaxations in order to generate a sequence of subproblems. Pseudo cuts are added during the search process to avoid revisiting the same search space areas. VN diving is based on the variable neighbourhood decomposition search framework. Conversely, SN diving explores only a single neighbourhood in each iteration: if a feasible solution is not found, then the next reference solution is chosen using the feasibility pump principle and the search history. Moreover, we prove that the two proposed algorithms converge in a finite number of iterations (. either return a feasible solution of the input problem, or prove its infeasibility).We show that our proposed algorithms significantly outperform the CPLEX MIP solver and the recent .
