You are here

Very Large-Scale Neighborhoods

In Local Search, one defines - for each solution S of the problem - a set N(S) of solutions similar to S. These solutions are often built by making small changes to S. N(S) is called the neighborhood of S. In order to solve a problem, one starts from an initial solution S_0, select one neighbor in S_1 = N(S_0) and move to it. It goes on by moving from solution to one of its neighbor until some termination criteria is met (e.g. no solution of increasing quality can be found in the neighborhood of the current solution).

It is well admit that the the larger the size of the neighborhood used, the better the quality of the best solution found. However, by defining a large neighborhood, the time required to search for the best neighbors in N(S) is increased. Very Large-Scale Neighborhoods (VLSN) are neighborhoods which size is very large (often exponential in the size of the problem) while having a nice structure that allows to find best neighbors very quickly. For example one could define N(S) as the set of paths in a well-defined acyclic graph. There is an exponential number of such paths, but one can find a path having the most negative weight in polynomial time.

VLSN were defined on a large set of applications and successfully used to find optimal or almost optimal solutions to a lot of problems from combinatorial optimization: traveling salesman problem (TSP), vehicle routing problem (VRP), set partitionning (SP),…

The main drawback of the VLSN is the time and energy required to efficiently implement them. Our final goal in this research area is to allow the user to define a VLSN in a declarative way without any care at implementation details. This definition would be done by mean of a high-level language. An internal engine would analyse the definition provided by the user and automatically generate a search procedure capable of finding the best neighbor in a VLSN.