Variable neighborhood search

VNS systematically changes the neighborhood in two phases: firstly, descent to find a local optimum and finally, a perturbation phase to get out of the corresponding valley.

Applications are rapidly increasing in number and pertain to many fields: location theory, cluster analysis, scheduling, vehicle routing, network design, lot-sizing, artificial intelligence, engineering, pooling problems, biology, phylogeny, reliability, geometry, telecommunication design, etc.

There are several books important for understanding VNS, such as: Handbook of Metaheuristics, 2010,[3] Handbook of Metaheuristics, 2003[4] and Search methodologies, 2005.[5] Earlier work that motivated this approach can be found in

1. Davidon, W.C.[6]
2. Fletcher, R., Powell, M.J.D.[7]
3. Mladenović, N.[8] and
4. Brimberg, J., Mladenović, N.[9]

Recent surveys on VNS methodology as well as numerous applications can be found in 4OR, 2008[10] and Annals of OR, 2010.

Define one deterministic optimization problem with

${\displaystyle \min {\{f(x)|x\in X,X\subseteq S\}}}$, (1)

where S, X, x, and f are the solution space, the feasible set, a feasible solution, and a real-valued objective function, respectively. If S is a finite but large set, a combinatorial optimization problem is defined. If ${\displaystyle {S=R^{n}}}$, there is continuous optimization model.

A solution ${\displaystyle {x^{*}\in X}}$ is optimal if

${\displaystyle {f(x^{*})\leq f(x),\qquad \forall {x}\,\in X}}$.

Exact algorithm for problem (1) is to be found an optimal solution x*, with the validation of its optimal structure, or if it is unrealizable, in procedure have to be shown that there is no achievable solution, i.e., ${\displaystyle X=\varnothing }$, or the solution is unbounded. CPU time has to be finite and short. For continuous optimization, it is reasonable to allow for some degree of tolerance, i.e., to stop when a feasible solution ${\displaystyle x^{*}}$ has been found such that

${\displaystyle {f(x^{*})\leq f(x)+\epsilon ,\qquad \forall {x}\,\in X}}$ or ${\displaystyle {(f(x^{*})-f(x))/f(x^{*})<\epsilon ,\qquad \forall {x}\,\in X}}$

Some heuristics speedily accept an approximate solution, or optimal solution but one with no validation of its optimality. Some of them have an incorrect certificate, i.e., the solution ${\displaystyle x_{h}}$ obtained satisfies

${\displaystyle {(f(x_{h})-f(x))/f(x_{h})\leq \epsilon ,\qquad \forall {x}\,\in X}}$ for some ${\displaystyle \epsilon }$, though this is rarely small.

Heuristics are faced with the problem of local optima as a result of avoiding boundless computing time. A local optimum ${\displaystyle x_{L}}$ of problem is such that

${\displaystyle {f(x_{L})\leq f(x),\qquad \forall {x}\,\in N(x_{L})\cap X}}$

where ${\displaystyle N(x_{L})}$ denotes a neighborhood of ${\displaystyle x_{L}}$

According to (Mladenović, 1995), VNS is a metaheuristic which systematically performs the procedure of neighborhood change, both in descent to local minima and in escape from the valleys which contain them.

VNS is built upon the following perceptions:

1. A local minimum with respect to one neighborhood structure is not necessarily a local minimum for another neighborhood structure.
2. A global minimum is a local minimum with respect to all possible neighborhood structures.
3. For many problems, local minima with respect to one or several neighborhoods are relatively close to each other.

Unlike many other metaheuristics, the basic schemes of VNS and its extensions are simple and require few, and sometimes no parameters. Therefore, in addition to providing very good solutions, often in simpler ways than other methods, VNS gives insight into the reasons for such a performance, which, in turn, can lead to more efficient and sophisticated implementations.

There are several papers where it could be studied among recently mentioned, such as (Hansen and Mladenović 1999, 2001a, 2003, 2005; Moreno-Pérez et al.;[11])

A local search heuristic is performed through choosing an initial solution x, discovering a direction of descent from x, within a neighborhood N(x), and proceeding to the minimum of f(x) within N(x) in the same direction. If there is no direction of descent, the heuristic stops; otherwise, it is iterated. Usually the highest direction of descent, also related to as best improvement, is used. This set of rules is summarized in Algorithm 1, where we assume that an initial solution x is given. The output consists of a local minimum, denoted by x', and its value. Observe that a neighborhood structure N(x) is defined for all x ∈ X. At each step, the neighborhood N(x) of x is explored completely. As this may be time-consuming, an alternative is to use the first descent heuristic. Vectors ${\displaystyle x^{i}\in N(x)}$ are then enumerated systematically and a move is made as soon as a direction for the descent is found. This is summarized in Algorithm 2.

Function BestImprovement(x)
  1: repeat
  2:     x' ← x
  3:     x ← argmin_{ f(y) }, y ∈ N(x)
  4: until ( f(x) ≥ f(x') )
  5: return x'

Function FirstImprovement(x)
  1: repeat
  2:    x' ← x; i ← 0
  3:    repeat
  4:       i ← i + 1
  5:       x ← argmin{ f(x), f(x^i)}, x^i ∈ N(x)
  6:    until ( f(x) < f(x^i) or i = |N(x)| )
  7: until ( f(x) ≥ f(x') )
  8: return x'

Function NeighborhoodChange (x, x', k)
 1: if f (x') < f(x) then
 2:    x ← x'     // Make a move
 3:    k ← 1      // Initial neighborhood
 4: else
 5:    k ← k+1    // Next neighborhood

Function VNS (x, kmax, tmax)
 1: repeat
 2:    k ← 1
 3:    repeat
 4:       x' ← Shake(x, k)                   // Shaking
 5:       x'' ← BestImprovement(x' )         // Local search
 6:       x ← NeighbourhoodChange(x, x'', k) // Change neighbourhood
 7:    until k = kmax
 8:    t ← CpuTime()
 9: until t > tmax

• VND[13]

The variable neighborhood descent (VND) method is obtained if a change of neighborhoods is performed in a deterministic way. In the descriptions of its algorithms, we assume that an initial solution x is given. Most local search heuristics in their descent phase use very few neighborhoods. The final solution should be a local minimum with respect to all ${\displaystyle k_{max}}$ neighborhoods; hence the chances to reach a global one are larger when using VND than with a single neighborhood structure.

• RVNS[14]

The reduced VNS (RVNS) method is obtained if random points are selected from ${\displaystyle {\mathcal {N}}_{k}(x)}$ and no descent is made. Rather, the values of these new points are compared with that of the incumbent and an update takes place in case of improvement. It is assumed that a stopping condition has been chosen like the maximum CPU time allowed ${\displaystyle t_{max}}$ or the maximum number of iterations between two improvements.

To simplify the description of the algorithms it is used ${\displaystyle t_{max}}$ below. Therefore, RVNS uses two parameters: ${\displaystyle t_{max}}$ and ${\displaystyle k_{max}}$. RVNS is useful in very large instances, for which local search is costly. It has been observed that the best value for the parameter ${\displaystyle k_{max}}$ is often 2. In addition, the maximum number of iterations between two improvements is usually used as a stopping condition. RVNS is akin to a Monte-Carlo method, but is more systematic.

• Skewed VNS

The skewed VNS (SVNS) method (Hansen et al.)[15] addresses the problem of exploring valleys far from the incumbent solution. Indeed, once the best solution in a large region has been found, it is necessary to go some way to obtain an improved one. Solutions drawn at random in distant neighborhoods may differ substantially from the incumbent and VNS can then degenerate, to some extent, into the Multistart heuristic (in which descents are made iteratively from solutions generated at random, a heuristic which is known not to be very efficient). Consequently, some compensation for distance from the incumbent must be made.

• Variable Neighborhood Decomposition Search

The variable neighborhood decomposition search (VNDS) method (Hansen et al.)[16] extends the basic VNS into a two-level VNS scheme based upon decomposition of the problem. For ease of presentation, but without loss of generality, it is assumed that the solution x represents the set of some elements.

• Parallel VNS

Several ways of parallelizing VNS have recently been proposed for solving the p-Median problem. In García-López et al.[17]  three of them are tested: (i) parallelize local search; (ii) augment the number of solutions drawn from the current neighborhood and make a local search in parallel from each of them and (iii) do the same as (ii) but update the information about the best solution found. Three Parallel VNS strategies are also suggested for solving the Travelling purchaser problem in Ochi et al.[18]

• Primal-dual VNS

For most modern heuristics, the difference in value between the optimal solution and the obtained one is completely unknown. Guaranteed performance of the primal heuristic may be determined if a lower bound on the objective function value is known. To this end, the standard approach is to relax the integrality condition on the primal variables, based on a mathematical programming formulation of the problem.

However, when the dimension of the problem is large, even the relaxed problem may be impossible to solve exactly by standard commercial solvers. Therefore, it seems a good idea to solve dual relaxed problems heuristically as well. It was obtained guaranteed bounds on the primal heuristics performance. In Primal-dual VNS (PD-VNS) (Hansen et al.)[19] one possible general way to attain both the guaranteed bounds and the exact solution is proposed.

• Variable Neighborhood Branching[20]

The mixed integer linear programming (MILP) problem consists of maximizing or minimizing a linear function, subject to equality or inequality constraints, and integrality restrictions on some of the variables.

• Variable Neighborhood Formulation Space Search[21]

FSS is a method which is very useful because, one problem could be defined in addition formulations and moving through formulations is legitimate. It is proved that local search works within formulations, implying a final solution when started from some initial solution in first formulation. Local search systematically alternates between different formulations which was investigated for circle packing problem (CPP) where stationary point for a nonlinear programming formulation of CPP in Cartesian coordinates is not strictly a stationary point in polar coordinates.

Applications of VNS, or of varieties of VNS are very abundant and numerous. Some fields where it could be found collections of scientific papers:

• Industrial applications
• Design problems in communication
• Location problems
• Data mining
• Graph problems
• Knapsack and packing problems
• Mixed integer problems
• Time tabling
• Scheduling
• Vehicle routing problems
• Arc routing and waste collection
• Fleet sheet problems
• Extended vehicle routing problems
• Problems in biosciences and chemistry
• Continuous optimization
• Other optimization problems
• Discovery science

VNS implies several features which are presented by Hansen and Mladenović[22] and some are presented here:

1. Simplicity: VNS is simple, clear and universally applicable
2. Precision: VNS is formulated in precise mathematical definitions
3. Coherence: all actions of the heuristics for solving problems follow from the VNS principles
4. Effectiveness: VNS supplies optimal or near-optimal solutions for all or at least most realistic instances
5. Efficiency: VNS takes a moderate computing time to generate optimal or near-optimal solutions
6. Robustness: the functioning of the VNS is coherent over a variety of instances
7. User friendliness: VNS has no parameters, so it is easy for understanding, expressing and using
8. Innovation: VNS is generating new types of application
9. Generality: VNS is inducing to good results for a wide variety of problems
10. Interactivity: VNS allows the user to incorporate his knowledge to improve the resolution process
11. Multiplicity: VNS is able to produce a certain near-optimal solutions from which the user can choose;

Interest in VNS is growing quickly, evidenced by the increasing number of papers published each year on this topic (10 years ago, only a few; 5 years ago, about a dozen; and about 50 in 2007). Moreover, the 18th EURO mini-conference held in Tenerife in November 2005 was entirely devoted to VNS. It led to special issues of IMA Journal of Management Mathematics in 2007, European Journal of Operational Research (http://www.journals.elsevier.com/european-journal-of-operational-research/), and Journal of Heuristics (https://www.springer.com/mathematics/applications/journal/10732/) in 2008.

• EURO Mini Conference XXVIII on Variable Neighbourhood Search
• The 5th International Conference on Variable Neighborhood Search
• The 8th International Conference on Variable Neighborhood Search