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.