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

G-2000-03

Variable Neighborhood Search: A Chapter of Handbook of Applied Optimization

et

Variable Neighborhood Search is a recent metaheuristic based on the idea of systematic change of neighborhood during both a descent phase and an exploration phase, allowing to get out of local optima. A basic scheme and extensions allowing solution of large problems are presented. Applications to well-known combinatorial optimization problems, as well as to stabilization of column generation algorithms and computer-aided discovery of conjectures in graph theory are outlined.

, 20 pages