Groupe d’études et de recherche en analyse des décisions

G-2001-24

Developments of Variable Neighborhood Search

et

Proposed just a few years ago, Variable Neighborhood Search (VNS) is a new metaheuristic for combinatorial and global optimization, based upon systematic change of neighborhood within a possibly randomized local search. Its development has been rapid. After reviewing the basic scheme of VNS, several extensions aimed at solving large problem instances are surveyed. Issues in devising a VNS heuristic are discussed. Finally, recent applications are briefly summarized, with special attention given to VNS-based computer-aided discovery of conjectures in graph theory.

, 25 pages