TAILIEUCHUNG - New variable neighbourhood search based 0-1 MIP heuristics
In recent years many so-called matheuristics have been proposed for solving Mixed Integer Programming (MIP) problems. Though most of them are very efficient, they do not all theoretically converge to an optimal solution. In this paper we suggest two matheuristics, based on the variable neighbourhood decomposition search (VNDS), and we prove their convergence. | Yugoslav Journal of Operations Research 25 (2015), Number 3, 343–360 DOI: NEW VARIABLE NEIGHBOURHOOD SEARCH BASED 0-1 MIP HEURISTICS ´ 4,5 ,Nenad MLADENOVIC ´ 4,5 , Sa¨ıd HANAFI1,2,3 ,Jasmina LAZIC 1,2,3 1,2,3 ´ Christophe WILBAUT ,Igor CREVITS 1: Univ Lille Nord de France, F-59000 Lille, France 2: UVHC, LAMIH - F-59313 Valenciennes, France 3:CNRS, UMR 8201, F-59313 Valenciennes, France 4: Brunel University, UK 5: Mathematical Institute, Serbian Academy of Sciences and Arts,Serbia , Received: February 2014 / Accepted: May 2014 Abstract: In recent years many so-called matheuristics have been proposed for solving Mixed Integer Programming (MIP) problems. Though most of them are very efficient, they do not all theoretically converge to an optimal solution. In this paper we suggest two matheuristics, based on the variable neighbourhood decomposition search (VNDS), and we prove their convergence. Our approach is computationally competitive with the current state-of-the-art heuristics, and on a standard benchmark of 59 0-1 MIP instances, our best heuristic achieves similar solution quality to that of a recently published VNDS heuristic for 0-1 MIPs within a shorter execution time. Keywords: 0-1 Mixed integer programming, Matheuristics, Variable neighbourhood search, Pseudo-cuts, Convergence. MSC: 90C11,90C27. et al., / New Variable Neighbourhood Search 344 1. INTRODUCTION The 0-1 Mixed Integer Programming (0-1 MIP) problems can be expressed as follows: (0-1 MIP) max{cT x
đang nạp các trang xem trước
