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
  create an adjacent candidate solution
  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)

def adjacent(packing, rnd):
  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)
    adj_packing = adjacent(curr_packing, rnd)
    (adj_v, _) = total_valu_size(adj_packing, \
      valus, sizes, max_size)

    if adj_v "gt" curr_valu:  # better so accept adjacent
      curr_packing = adj_packing; curr_valu = adj_v
    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
        curr_packing = adj_packing; curr_valu = adj_v 
      # 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.

Leave a Reply

Please log in using one of these methods to post your comment:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s