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()

You must be logged in to post a comment.