Variable Neighborhood Search

From CometPublic

Contents 1 What's the Variable Neighborhood Search (VNS) ? 2 The k-Median Problem 2.1 Search 2.2 Implementation in Comet 2.3 Results 3 Exam scheduler 3.1 Model 3.1.1 Description 3.1.2 Implementation 3.2 Search 3.3 Results

[edit] What's the Variable Neighborhood Search (VNS) ?

The local search algorithms, by definition, sacrifies quality guarantee for performance because of the local behavior. So, a greedy local search algorithm will find in a really short time a solution, but it's a local solution. The goal of the Variable neighborhood search is to escape from these local optimum.

The idea is to restart a new greedy local search from a state that differs a bit from the last best solution found ; even if the value of the objective function is worse.

The step that consists to find the start state for the next local search is called the diversification phase.

Let N_d be the set of states that can be reached in d moves from the current best solution. A move have to be define for each problem.

The diversification phase consists in randomly selecting a member of N_d.

If the solution found with this new start state is worse then, d is increased, if it's better, d is reseted at 1.

Here's a generic template of the algorithm.

• s  : start for next local search

• s+ : result of local search (candidate)

• s* : best solution until now

• d  : diversification level

   function VariableNeighborhoodSearch(f, N, L, S){
       s := GenerateInitialSolution();
       s* := s;
       d := 1;
       while d <= MaxShaking do
           s := Select n in Nd(s);
           s+ := LocalSearch(f, N, L, S, s);
           d := d+1;
           if f(s+) < f(s*) then
               s := s+;
               s* := s;
               d := 1;
       return s*;
   }

The variable neighborhood search mobilizes ressources only when they are needed and makes many short steps rather than a few big ones. It relies on the well known principle of Divide and conqueer.

To illustrate VNS, let's introduce two problems : the k-Median problem and an exam scheduler.

[edit] The k-Median Problem

Let W be a set of warehouses and S, a set of stores.

Exactly k warehouses in W can be opened at the same time.

Let also c_ws be the cost of serving store s by warehouse w.

The objective is to find th set of k warehouses to open in order to minimize the costs knowning that each store must be served by a single warehouse but each warehouse can serve more than a single store.

This is an optimization problem that can be resume like that :

min

| Open | = k

[edit] Search

The core is a greedy local search algorithm that selects the closed warehouse c and the open warehouse o whose swap reduces the objective function the most.

This greedy local search procedure terminates when no swap reduces the cost, in which case a local minimum has been reached.

Then the diversification step is executed. It consists of selecting a random open warehouse o and swapping it with a closed warehouse c.

The closed warehouse is chosen to minimize the cost but the move may actually increase the objective function. This is intentional, since the goal of the diversification is to escape the current local minimum. This random selection is executed d times. As mention above, if the current step does not improve the best solution found so far, the level of diversification d is increased. Otherwise d is reseted to one.

[edit] Implementation in Comet

The file that contains the code for this example is available in the program library page of the Comet Web Site

[edit] Results

The variable neighborhood search was compared with a simple greedy local search. As expected, VNS was a bit slower than the greedy search because, it is made of several greedy searches. On the other hand, solutions found by a variable neighborhood search are always better than the ones found by the greedy searches. This proves that the diversification step can successfully escape from local minimum.

Note that the difference between the two methods is more obvious when the number of warehouses to open is greater than 20.

[edit] Exam scheduler

The problem consists in designing an exam session. There are several student profiles that have to sit for some exams. Each exam is associated to a weight that can be different according to the profile.

The goal is to find a date for each exam in the exam period such that :

• each profile can have only one exam in a slot,

• the gap before each exam have to be proportional to its weight.

[edit] Model

[edit] Description

To achieve a balanced scheduling, the idea is to minimize the difference between the current gap value and the optimal gap value.

Let p be a profile and e, an exam :

• weight(p,e) is the weight of the exam e in the profile p.

• sumAllWeight(p) is the sum of the weights of all exams in profile p.

The optimal gap value is computed this way :

The objective function to minimize is the following :

[edit] Implementation

In comet, a differentiable invariant is used. It allows to combine constraints satisfaction and the optimization of the objective function.

Objective function to minimize :

   ObjectiveSum OS (m);
   forall(p in Profils){
       forall(e in Events : profilsEvents[p,e] != 0){
           OS.post( abs(gap[p,e] - optimalGaps[p,e]) );
       }
   }

The differential invariant is :

   Objective O = weight * Sys + OS;

where Sys are the violations of the constraint system. A weight is used to ensure that the constraint satisfaction is satisfied if possible.

The Comet implementation is available here : scheduler.co

This file requires an input file that describes the current problem, here are two examples : infile & infile2

A README explains how to use the program and how to create an input file : README

[edit] Search

The principle of the search is the same as the one depicted for the k-median problem.

In this case, the diversification step consists of d random swaps between two exams. A first exam is randomly selected, then, a second one is chosen by minimizing the objective function. A degradation in the objective function can occur due to the random part of the procedure. Thus the algorithm can get out of local minima.

[edit] Results

In order to compare a variable neighborhood search and a greedy local search, the program was run 2000 times for different number of free slots.

The tables show the mean values for each search. We can see that the VNS always gives better results.

Objective value without violations for infile1

Free slots	VNS	GREEDY
10	65	82
15	50	66
20	65	95
25	79	100

Objective value without violations for infile2

Free slots	VNS	GREEDY
10	43	109
15	81	114
20	112	168
25	149	225

Number of remaining violations for infile1

Free slots	VNS	GREEDY
10	4	5
15	0	0
20	0	0
25	0	0

Objective value without violations for infile2

Free slots	VNS	GREEDY
10	12	16
15	0	0
20	0	0
25	0	0