Brunel University Research Archive (BURA) >
College of Engineering, Design and Physical Sciences >
Dept of Mathematics >
Dept of Mathematics Research Papers >

Please use this identifier to cite or link to this item: http://bura.brunel.ac.uk/handle/2438/3863

Title: Variable neighbourhood decomposition search for 0-1 mixed integer programs
Authors: Lazic, J
Hanafi, S
Mladenović, N
Urosevic, D
Keywords: 0-1 Mixed integer programming
Metaheuristics
Variable neighbourhood search
CPLEX
Publication Date: 2009
Publisher: Elsevier
Citation: Computers and Operations Research. 37(6): 1055-1067
Abstract: 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 di±cult 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.
URI: http://bura.brunel.ac.uk/handle/2438/3863
DOI: http://dx.doi.org/10.1016/j.cor.2009.09.010
ISSN: 0305-0548
Appears in Collections:Mathematical Science
Publications
Dept of Mathematics Research Papers

Files in This Item:

File Description SizeFormat
Fulltext.pdf306.85 kBAdobe PDFView/Open

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