Authors: Lazić, Jasmina
Hanafi, Saïd
Mladenović, Nenad 
Urošević, Dragan 
Affiliations: Mathematical Institute of the Serbian Academy of Sciences and Arts 
Title: Solving 0-1 mixed integer programs with variable neighbourhood decomposition search
Journal: IFAC Proceedings Volumes (IFAC-PapersOnline)
Volume: 13
Issue: PART 1
First page: 2012
Last page: 2017
Conference: 13th IFAC Symposium on Information Control Problems in Manufacturing, INCOM'09; Moscow; Russian Federation; 3 June 2009 through 5 June 2009
Issue Date: 1-Dec-2009
ISBN: 978-3-902-66143-2
ISSN: 1474-6670
DOI: 10.3182/20090603-3-RU-2001.0501
In this paper we propose a new heuristic for solving 0-1 mixed integer programs based on the variable neighbourhood decomposition search principle. It combines variable neighbourhood search with general-purpose CPLEX MIP solver. We perform systematic hard variables fixing (or diving) following the variable neighbourhood search rules. 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 by exploiting boundary effects in this way, solution quality can be considerably improved. 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 CPLEX MIP solver, as well as three other recent most successful MIP solution methods.
Keywords: 0-1 mixed integer programming | Diving | Mathematical programming | Metaheuristics | Soft variable fixing | Variable neighbourhood search
Publisher: Elsevier

Show full item record

Page view(s)

checked on May 9, 2024

Google ScholarTM




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