Optimization: principles and algorithms, by Michel Bierlaire
ksLocalSearchDeterministic.m
Go to the documentation of this file.
1 %> \file
2 %> Algorithm 27.3: local search for the knapsack problem. Implementation of algorithm 27.3 of \cite Bier15-book
3 %>
4 %> @note Tested with \ref run2702localSearchDeterministic.m
5 %>
6 %> @author Michel Bierlaire
7 %> @date Tue Apr 14 13:08:52 2015
8 %> @ingroup Algorithms
9 %> @ingroup chap27
10 %>
11 %> Perform a local search for the knapsack problem with a neighborhood of a given size, with a complete enumeration of the neighbors
12 %> @param u utility of each item
13 %> @param w weight of each item
14 %> @param c capacity of the knapsack
15 %> @param x0 current solution
16 %> @param s size of the neighborhood
17 %> @return x local optimum
18 function x = ksLocalSearchDeterministic(u,w,c,x0,s)
19  n = size(u,1) ;
20  if (size(w) != n)
21  error("Vectors of incompatible sizes: %d and %d\n",n,size(w))
22  endif
23  current = x0 ;
24 % The next statement generates all possible combinations of s indices among n
25  neighbors = nchoosek(1:n,s)'
26  totalWeight = w'*x0 ;
27  if (totalWeight > c)
28  error("The initial solution is infeasible. Total weight: %f. Capacity %f.",totalWeight,c)
29  endif
30  currentValue = u'*x0 ;
31  iter = 0 ;
32  contin = 1 ;
33  while (contin)
34  contin = 0 ;
35  iter += 1 ;
36  neighborsVisited = 0 ;
37  for index = neighbors
38  neighborsVisited += 1 ;
39  candidate = current ;
40  for j = index'
41  candidate(j) = 1-candidate(j) ;
42  endfor
43  printf("%d (%d):\t%d\t%d\t%d\t%d\t%d\t%d\t%d\t%d\t%d\t%d\t%d\t%d\t%d\t%d\t%d\n",iter,neighborsVisited,candidate',w'*candidate,u'*candidate,u'*current) ;
44  if (w'*candidate <= c)
45  if (u'*candidate > currentValue)
46  current = candidate ;
47  currentValue = u'*candidate ;
48  contin = 1 ;
49  break ;
50  endif
51  endif
52  endfor
53  endwhile
54  x = current ;
55 endfunction
function ksLocalSearchDeterministic(in u, in w, in c, in x0, in s)