Authors: Lazić, Jasmina
Todosijević, Raca 
Hanafi, Saïd
Mladenović, Nenad 
Affiliations: Mathematical Institute of the Serbian Academy of Sciences and Arts 
Title: Variable and single neighbourhood diving for MIP feasibility
Journal: Yugoslav Journal of Operations Research
Volume: 26
Issue: 2
First page: 131
Last page: 157
Issue Date: 1-Jan-2016
Rank: M51
ISSN: 0354-0243
DOI: 10.2298/YJOR140417027L
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 (i.e. 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 (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.
Keywords: Constructive heuristics | CPLEX | Feasibility pump | Mixed integer programming
Publisher: Faculty of Organizational Sciences, University of Belgarde
Project: Mathematical Modelas and Optimization Methods on Large-Scale Systems 

Show full item record


checked on May 21, 2024

Page view(s)

checked on May 9, 2024

Google ScholarTM




Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.