Geodesic
Variable and Single Neighborhood Diving for MIP Feasibility
Yugoslav journal of operations research, Tome 26 (2016) no. 2, p. 131 Cet article a éte moissonné depuis la source eLibrary of Mathematical Institute of the Serbian Academy of Sciences and Arts

Voir la notice de l'article

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 neighborhood (SN) diving, respectively. They perform systematic hard variable fixing (i.e. diving) by exploiting the information obtained from a series of LP relaxations in order to generate a sequence of sub-problems. Pseudo cuts are added during the search process to avoid revisiting the same search space areas. VN diving is based on the variable neighborhood decomposition search framework. Conversely, SN diving explores only a single neighborhood 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 (i.e. either return a feasible solution of the input problem, or prove its infeasibility).We show that our proposed algorithms significantly outperform the CPLEX 12.4 MIP solver and the recent variants of feasibility pump regarding the solution quality.
Classification : 90B06, 90C05, 90C08
Keywords: Mixed Integer Programming, Constructive Heuristics, Feasibility Pump, CPLEX. 
@article{YJOR_2016_26_2_a0,
     author = {Jasmina Lazi\'c and Raca Todosijevi\'c and Sa{\"\i}d Hanafi and Nenad Mladenovi\'c},
     title = {Variable and {Single} {Neighborhood} {Diving} for {MIP} {Feasibility}},
     journal = {Yugoslav journal of operations research},
     pages = {131 },
     year = {2016},
     volume = {26},
     number = {2},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/YJOR_2016_26_2_a0/}
}
TY  - JOUR
AU  - Jasmina Lazić
AU  - Raca Todosijević
AU  - Saïd Hanafi
AU  - Nenad Mladenović
TI  - Variable and Single Neighborhood Diving for MIP Feasibility
JO  - Yugoslav journal of operations research
PY  - 2016
SP  - 131 
VL  - 26
IS  - 2
UR  - http://geodesic.mathdoc.fr/item/YJOR_2016_26_2_a0/
LA  - en
ID  - YJOR_2016_26_2_a0
ER  - 
%0 Journal Article
%A Jasmina Lazić
%A Raca Todosijević
%A Saïd Hanafi
%A Nenad Mladenović
%T Variable and Single Neighborhood Diving for MIP Feasibility
%J Yugoslav journal of operations research
%D 2016
%P 131 
%V 26
%N 2
%U http://geodesic.mathdoc.fr/item/YJOR_2016_26_2_a0/
%G en
%F YJOR_2016_26_2_a0
Jasmina Lazić; Raca Todosijević; Saïd Hanafi; Nenad Mladenović. Variable and Single Neighborhood Diving for MIP Feasibility. Yugoslav journal of operations research, Tome 26 (2016) no. 2, p. 131 . http://geodesic.mathdoc.fr/item/YJOR_2016_26_2_a0/