Optimization: principles and algorithms, by Michel Bierlaire
ksVns.m
Go to the documentation of this file.
1 %> \file
2 %> Algorithm 27.5: VNS for the knapsack problem. Implementation of algorithm 27.5 of \cite Bier15-book
3 %>
4 %> @note Tested with \ref run2702vns.m
5 %> @note Calls \ref ksLocalSearchRandom
6 %>
7 %> @author Michel Bierlaire
8 %> @date Wed Apr 15 09:21:56 2015
9 %> @ingroup Algorithms
10 %> @ingroup chap27
11 %>
12 %> VNS algorithm for the knapsack problem.
13 %> @param u utility of each item
14 %> @param w weight of each item
15 %> @param c capacity of the knapsack
16 %> @param x0 current solution
17 %> @return x local optimum
18 %> @return The file \c ksIters.dat is also created, containing the details of the iterations.
19 function best = ksVns(u,w,c,x0)
20  [fff,msg] = fopen("ksIters.dat","w") ;
21  fprintf(fff,"Neighborhood\Candidate\tBest\n") ;
22  n = size(u,1) ;
23  if (size(w) != n)
24  error("Vectors of incompatible sizes: %d and %d\n",n,size(w))
25  endif
26  best = x0 ;
27  s = 1 ;
28  while (s <= n)
29  candidate = ksLocalSearchRandom(u,w,c,best,s) ;
30  fprintf(fff,"%d\t%f\t%f\n",s,u'*candidate,u'*best) ;
31  if (u'*candidate > u'*best)
32  best = candidate ;
33  s = 1 ;
34  else
35  s += 1 ;
36  endif
37  endwhile
38  fclose(fff) ;
39 endfunction
function ksVns(in u, in w, in c, in x0)
function ksLocalSearchRandom(in u, in w, in c, in x0, in s, in maxiter)