Optimization: principles and algorithms, by Michel Bierlaire
ksLocalSearchRandom.m
Go to the documentation of this file.
1 %> \file
2 %> Implementation of a variant of the local search algorithm with random neighbors for the knapsack problen.
3 %>
4 %> @note Tested with \ref run2702localSearchRandom.m
5 %> @note Calls \ref ksRandomNeighbor
6 %> @note Called by \ref ksVns
7 %>
8 %> @author Michel Bierlaire
9 %> @date Wed Apr 15 09:02:29 2015
10 %> @ingroup Algorithms
11 %> @ingroup chap27
12 %>
13 %> Perform a variant of the local search for the knapsack problem with a neighborhood of a given size, where neighbord are selected randomly, and accepted if hey improve the objective function.
14 %> @param u utility of each item
15 %> @param w weight of each item
16 %> @param c capacity of the knapsack
17 %> @param x0 current solution
18 %> @param s size of the neighborhood
19 %> @param maxiter number of candidates being evaluated (Default: 1000)
20 %> @return x local optimum
21
22 function x = ksLocalSearchRandom(u,w,c,x0,s,maxiter=1000)
23  current = x0 ;
24  totalWeight = w'*x0 ;
25  if (totalWeight > c)
26  error("The initial solution is infeasible. Total weight: %f. Capacity %f.",totalWeight,c)
27  endif
28  currentValue = u'*x0 ;
29  iter = 0 ;
30  while (iter <= maxiter)
31  iter += 1 ;
32  candidate = ksRandomNeighbor(current,s) ;
33  if (w'*candidate <= c)
34  if (u'*candidate > currentValue)
35  current = candidate ;
36  currentValue = u'*candidate ;
37  iter = 0 ;
38  endif
39  endif
40  endwhile
41  x = current ;
42 endfunction
function ksVns(in u, in w, in c, in x0)
function ksRandomNeighbor(in x0, in s)
function ksLocalSearchRandom(in u, in w, in c, in x0, in s, in maxiter)