Matheuristics Based on Variable Neighborhood Search

Abstract

Matheuristics represent heuristic optimization methods based on hybridizing exact solvers with metaheuristics. Usually, the exact solvers work on Mathematical Programming (more precisely Mixed Integer Linear Programming, MILP) formulation of the considered problem. Metaheuristic principles are used to define subproblems (e.g., by fixing values for a subset of variables) and exact solver is then invoked to determine values for the remaining variables. The main goal of this paper is to promote three matheuristics that explore Variable Neighborhood Search (VNS) as metaheuristic part. These are Variable Neighborhood Branching (VNB),Variable Neighborhood Decomposition Search for 0-1 MIP problems (VNDS-MIP), and Variable Intensity Neighborhood Search (VINS).