Authors: Lazić, Jasmina
Hanafi, Saïd
Mladenović, Nenad 
Urošević, Dragan 
Affiliations: Mathematical Institute of the Serbian Academy of Sciences and Arts 
Title: Variable neighbourhood decomposition search for 0-1 mixed integer programs
Journal: Computers and Operations Research
Volume: 37
Issue: 6
First page: 1055
Last page: 1067
Issue Date: 1-Jun-2010
Rank: M21
ISSN: 0305-0548
DOI: 10.1016/j.cor.2009.09.010
In this paper we propose a new hybrid heuristic for solving 0-1 mixed integer programs based on the principle of variable neighbourhood decomposition search. It combines variable neighbourhood search with a general-purpose CPLEX MIP solver. We perform systematic hard variable fixing (or diving) following the variable neighbourhood search rules. The variables to be fixed are chosen according to their distance from the corresponding linear relaxation solution values. If there is an improvement, variable neighbourhood descent branching is performed as the local search in the whole solution space. Numerical experiments have proven that exploiting boundary effects in this way considerably improves solution quality. With our approach, we have managed to improve the best known published results for 8 out of 29 instances from a well-known class of very difficult MIP problems. Moreover, computational results show that our method outperforms the CPLEX MIP solver, as well as three other recent most successful MIP solution methods.
Keywords: 0-1 mixed integer programming | CPLEX | Metaheuristics | Variable neighbourhood search
Publisher: Elsevier

Show full item record


checked on May 28, 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.