Variable Neighborhood Search (VNS) is a recent metaheuristic, or framework for building heuristics, based on the idea of systematically changing neighborhoods both in the descent phase and as a means of escaping from local minima. The number of applications of VNS to combinatorial and global optimization problems is rapidly increasing. The aim is then to obtain in moderate computing time a near-optimal, or unproved optimal solution. We first recall the basics of VNS, discuss how to build efficient implementations and review selected applications by various researchers. But VNS can also be used in other ways and for other means: (i) as a tool for exploring the behaviour of heuristics, to better understand and then streamline them; (ii) as a tool for finding near-optimal solutions with a guarantee of performance; (iii) as an auxilliary tool within an exact algorithm, to enhance its performance, in particular in connection with stabilized column generation; (iv) as a tool to perform various tasks in graph theory, i.e., find graphs satisfying given constraints, find extremal graphs for a variety of invariants, refute conjectures, find or strengthen conjectures and suggest proof strategies. These non-standard uses will be reviewed in detail.