## Knapsack Problem Using Simulated Annealing Example

A combinatorial optimization problem is one where the goal is to find the optimal ordering / permutation of a set of discrete items. A standard example is called the knapsack problem. It’s best explained by example.

Here’s an example I found lurking about the Internet. Suppose you have 10 items, numbered 0 through 9. Each item has a money value and a size. You have a knapsack (a kind of bag) that can hold a maximum of 101 size-units. Your goal is to select the items that maximize the total value, subject to the condition that the total size can’t exceed 101.

```items  0  1  2  3  4  5  6  7  8  9
valus 79 32 47 18 26 85 33 40 45 59
sizes 85 26 48 21 22 95 43 45 55 52

max size = 101
```

One possibility is to load items [6] and [8], when the total value is 33 + 45 = 78, with total size 43 + 55 = 98 (less than the limit of 101). Another possibility is to load items [1], [4], [7] when the total value is 32 + 26 + 40 = 98 (with total size = 93).

There are several techniques to solve combinatorial optimization problems. One approach is called simulated annealing. The idea is to set up a permutation like [0, 0, 1, 0, 0, 0, 0, 0, 0, 1] which means load items [2] and [9].

Expressed in pseudo-code:

```create a random initial permutation
loop many times
if candidate is better than curr solution then
curr solution = candidate (accept)
else if candidate is worse then
accept candidate anyway with small prob
end-if

decrease prob of accepting worse candidate
end-loop
return best solution found
```

There are a lot of details to deal with but overall simulated annealing is simple and usually (but not always) effective.

I coded up a short demo. Good fun.

I was chatting with a female work colleague about the knapsack problem. She mentioned that at one point, a popular fashion trend was for women (even her friends who work in tech) to wear very small designer bags. These bags cost hundreds or even thousands of dollars. I don’t think they’re well-suited for the knapsack problem. From left to right: Balanciaga, Jacquemus, Louis Vuitton. Life is endlessly interesting.

Demo code. Replace “lt” and “gt” with less-than and greater-than operators — my blog editor chokes on the symbols.

```# knapsack_annealing.py
# using classical simulated annealing
# Python 3.7.6 (Anaconda3 2020.02)

# items  0  1  2  3  4  5  6  7  8  9
# valus 79 32 47 18 26 85 33 40 45 59
# sizes 85 26 48 21 22 95 43 45 55 52
# max size = 101

# maximize value

import numpy as np

def total_valu_size(packing, valus, sizes, max_size):
# total value and size of a specified packing
v = 0.0  # total valu of packing
s = 0.0  # total size of packing
n = len(packing)
for i in range(n):
if packing[i] == 1:
v += valus[i]
s += sizes[i]
if s "gt" max_size:  # too big to fit in knapsack
v = 0.0
return (v, s)

n = len(packing)
result = np.copy(packing)
i = rnd.randint(n)
if result[i] == 0:
result[i] = 1
elif result[i] == 1:
result[i] = 0
return result

def solve(n_items, rnd, valus, sizes, max_size, \
max_iter, start_temperature, alpha):
# solve using simulated annealing
curr_temperature = start_temperature
curr_packing = np.ones(n_items, dtype=np.int64)
print("Initial guess: ")
print(curr_packing)

(curr_valu, curr_size) = \
total_valu_size(curr_packing, valus, sizes, max_size)
iteration = 0
interval = (int)(max_iter / 10)
while iteration "lt" max_iter:
# pct_iters_left = \
#  (max_iter - iteration) / (max_iter * 1.0)
valus, sizes, max_size)

else:          # adjacent packing is worse
accept_p = \
np.exp( (adj_v - curr_valu ) / curr_temperature )
p = rnd.random()
if p "lt" accept_p:  # accept worse packing anyway
# else don't accept

if iteration % interval == 0:
print("iter = %6d : curr value = %7.0f : \
curr temp = %10.2f " \
% (iteration, curr_valu, curr_temperature))

if curr_temperature "lt" 0.00001:
curr_temperature = 0.00001
else:
curr_temperature *= alpha
# curr_temperature = start_temperature * \
# pct_iters_left * 0.0050
iteration += 1

return curr_packing

def main():
print("\nBegin knapsack simulated annealing demo ")
print("Goal is to maximize value subject \
to max size constraint ")

valus = np.array([79, 32, 47, 18, 26, 85, 33, 40, 45, 59])
sizes = np.array([85, 26, 48, 21, 22, 95, 43, 45, 55, 52])
max_size = 101

print("\nItem values: ")
print(valus)
print("\nItem sizes: ")
print(sizes)
print("\nMax total size = %d " % max_size)

rnd = np.random.RandomState(5)  # 3 .98 = 117,100
max_iter = 1000
start_temperature = 10000.0
alpha = 0.98

print("\nSettings: ")
print("max_iter = %d " % max_iter)
print("start_temperature = %0.1f " \
% start_temperature)
print("alpha = %0.2f " % alpha)

print("\nStarting solve() ")
packing = solve(10, rnd, valus, sizes,
max_size, max_iter, start_temperature, alpha)
print("Finished solve() ")

print("\nBest packing found: ")
print(packing)
(v,s) = \
total_valu_size(packing, valus, sizes, max_size)
print("\nTotal value of packing = %0.1f " % v)
print("Total size  of packing = %0.1f " % s)

print("\nEnd demo ")

if __name__ == "__main__":
main()
```
This entry was posted in Machine Learning. Bookmark the permalink.