2 %> Algorithm 27.3: local search
for the knapsack problem. Implementation of algorithm 27.3 of \cite Bier15-book
4 %> @note Tested with \ref run2702localSearchDeterministic.m
6 %> @author Michel Bierlaire
7 %> @date Tue Apr 14 13:08:52 2015
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
21 error(
"Vectors of incompatible sizes: %d and %d\n",n,size(w))
24 % The next statement generates all possible combinations of s indices among n
25 neighbors = nchoosek(1:n,s)
' 28 error(
"The initial solution is infeasible. Total weight: %f. Capacity %f.",totalWeight,c)
30 currentValue = u
'*x0 ; 36 neighborsVisited = 0 ; 38 neighborsVisited += 1 ; 41 candidate(j) = 1-candidate(j) ;
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)
47 currentValue = u
'*candidate ; function ksLocalSearchDeterministic(in u, in w, in c, in x0, in s)