Survey of Metaheuristic Algorithms for Combinatorial Optimization <s> Variable Neighborhood Search <s> Variable neighborhood search (VNS) is a metaheuristic for solving combinatorial and global optimization problems whose basic idea is a systematic change of neighborhood both within a descent phase to find a local optimum and in a perturbation phase to get out of the corresponding valley. In this chapter we present the basic schemes of VNS and some of its extensions. We then describe a recent development, i.e., formulation space search. We then present five families of applications in which VNS has proven to be very successful: (i) exact solution of large-scale location problems by primal–dual VNS; (ii) generation of feasible solutions to large mixed integer linear programs by hybridization of VNS and local branching; (iii) generation of good feasible solutions to continuous nonlinear programs; (iv) generation of feasible solutions and/or improved local optima for mixed integer nonlinear programs by hybridization of sequential quadratic programming and branch and bound within a VNS framework, and (v) exploration of graph theory to find conjectures, refutations, and proofs or ideas of proofs. <s> BIB001 </s> Survey of Metaheuristic Algorithms for Combinatorial Optimization <s> Variable Neighborhood Search <s> Given an undirected graph with weights associated with its edges, the degree-constrained minimum spanning tree problem consists in finding a minimum spanning tree of the given graph, subject to constraints on node degrees. We propose a variable neighborhood search heuristic for the degree-constrained minimum spanning tree problem, based on a dynamic neighborhood model and using a variable neighborhood descent iterative improvement algorithm for local search. Computational experiments illustrating the effectiveness of the approach on benchmark problems are reported. <s> BIB002 </s> Survey of Metaheuristic Algorithms for Combinatorial Optimization <s> Variable Neighborhood Search <s> Descent methods for combinatorial optimization proceed by performing a sequence of local changes on an initial solution which improve each time the value of an objective function until a local optimum is found. Several metaheuristics have been proposed which extend in various ways this scheme and avoid being trapped in local optima. For example, Hansen and Mladenovic have recently proposed the variable neighborhood search method which has not yet been applied to many combinatorial optimization problems. The aim of this paper is to propose an adaptation of this new method to the graph coloring problem. � 2003 Published by Elsevier B.V. <s> BIB003 </s> Survey of Metaheuristic Algorithms for Combinatorial Optimization <s> Variable Neighborhood Search <s> The field of metaheuristics for the application to combinatorial optimization problems is a rapidly growing field of research. This is due to the importance of combinatorial optimization problems for the scientific as well as the industrial world. We give a survey of the nowadays most important metaheuristics from a conceptual point of view. We outline the different components and concepts that are used in the different metaheuristics in order to analyze their similarities and differences. Two very important concepts in metaheuristics are intensification and diversification. These are the two forces that largely determine the behavior of a metaheuristic. They are in some way contrary but also complementary to each other. We introduce a framework, that we call the I&D frame, in order to put different intensification and diversification components into relation with each other. Outlining the advantages and disadvantages of different metaheuristic approaches we conclude by pointing out the importance of hybridization of metaheuristics as well as the integration of metaheuristics and other methods for optimization. <s> BIB004 </s> Survey of Metaheuristic Algorithms for Combinatorial Optimization <s> Variable Neighborhood Search <s> We present a study on heuristic solution approaches to the minimum labelling Steiner tree problem, an NP-hard graph problem related to the minimum labelling spanning tree problem. Given an undirected labelled connected graph, the aim is to find a spanning tree covering a given subset of nodes of the graph, whose edges have the smallest number of distinct labels. Such a model may be used to represent many real world problems in telecommunications and multimodal transportation networks. Several metaheuristics are proposed and evaluated. The approaches are compared to the widely adopted Pilot Method and it is shown that the Variable Neighbourhood Search that we propose is the most effective metaheuristic for the problem, obtaining high quality solutions in short computational running times. <s> BIB005 </s> Survey of Metaheuristic Algorithms for Combinatorial Optimization <s> Variable Neighborhood Search <s> The Vertex Separation Problem belongs to a family of optimization problems in which the objective is to find the best separator of vertices or edges in a generic graph. This optimization problem is strongly related to other well-known graph problems; such as the Path-Width, the Node Search Number or the Interval Thickness, among others. All of these optimization problems are NP-hard and have practical applications in VLSI (Very Large Scale Integration), computer language compiler design or graph drawing. Up to know, they have been generally tackled with exact approaches, presenting polynomial-time algorithms to obtain the optimal solution for specific types of graphs. However, in spite of their practical applications, these problems have been ignored from a heuristic perspective, as far as we know. In this paper we propose a pure 0-1 optimization model and a metaheuristic algorithm based on the variable neighborhood search methodology for the Vertex Separation Problem on general graphs. Computational results show that small instances can be optimally solved with this optimization model and the proposed metaheuristic is able to find high-quality solutions with a moderate computing time for large-scale instances. <s> BIB006
Variable neighborhood search (VNS) was proposed by Mladenovic and Hansen in 1997. VNS BIB001 is a method based on the idea of dynamically changing neighborhood within a local search.VNS proceeds by a descent method to get from the neighbors to local optima exploring, systematically or at a random distant neighborhood of the incumbent solution. The method moves from this current solution to new one if there is an improvement in the solution. In this way, optimal variable is kept in the incumbent and obtains promising neighbors. Therefore VNS is not a trajectory following method. VNS main cycle consist of three phases. Shaking, local search and move. Basically VNS is extended into many forms. They are Variable Neighbor Descent, Reduced VNS, Basic VNS, Skewed VNS, General VNS, VNS Decomposition search and many more. P. BIB001 introduced VNS for PMedian problem. Experiment shows that the proposed variable neighborhood search heuristic is quite better than other heuristics  . A.S.Wade and V. J. Rayward Smith (2000) proposed VNS for solving Steiner tree problem by using an effective local search technique  . In 2001, N. Mladenovic and Urosevic proposed VNS for solving K cardinality tree problem  . BIB002 proposed a VNS for solving degree constrained minimum spanning tree problem. Here VNS heuristic is proposed which is based on dynamic neighborhood and a variable neighborhood descent iterative improvement algorithm is used for local search BIB002 . Avanthay at al. (2003) introduced an adaptation of the VNS method to graph coloring problem. The proposed technique has proved to be effective in determining high quality solutions BIB003 .  applied VNS to Multidimensional knapsack problem. Here a variant of VNS called Relaxation guided VNS is introduced. It is based on the general VNS scheme and a new variable neighborhood descent algorithm  .  proposed VNS for the job shop scheduling problem. The idea is to construct the best local search and shake operations based on neighborhood structure  . BIB005 proposed a VNS for minimum labeling Steiner tree problem. In this paper, a hybrid local search method known as Group-Swap Variable Neighborhood Search (GSVNS) is proposed. It is a hybrid of two metaheuristics named Variable Neighborhood Search and simulated Annealing. Experiment illustrates that the proposed heuristic quickly gives optimal or near optimal solutions BIB005 .  proposed a Variable neighborhood search for the matrix bandwidth minimization problem. In this paper, a VNS based heuristic is introduced which provide high quality solution to the problem  . Geiger et al. (2011) proposed neighborhood selection in VNS for solving single machine total weight tardiness problem  . BIB006 introduces a pure 0-1 optimization model and a metaheuristic algorithm based on the VNS methodology for the vertex separation problem on general graphs BIB006 . Other trajectory methods include Basic local search, Iterated local search, Guided local search. These can be found in BIB004 