What is Knapsack and Why We Use It

Knapsack problems are a type of problem that involves deciding which of a number of items should be placed into a limited amount of space. The problem type gets its name from trying to fill a backpack (knapsack) with items needed to go camping. In the classic scenario the items are a compass, matches, map, portable grill, food, clothes, tent, books, hunting equipment, etc. Each of these items has an assigned weight and value to the packer. If only 30 pounds can be held in the backpack which items should be chosen?

The problem boils down to a cost/value association in it's simplest form. Matches have a value of 10 and a weight of almost nothing, while a book has a relative value of 2 and a weight of maybe 2 pounds. It's a fairly simple decision to pack the matches before you pack the book. More decisions fall under this philosophy than realized. Anytime there is a choice between two items there is a potential knapsack problem.

Why am I explaining this? Well, not all problems are that cut and dry. Think about a distribution center and deciding the storage medium that should be used. It's a form of knapsack problem with several expandable size bags. Each rack type is a knapsack (Pallet Rack, Carton Storage, Floor Storage, Bin Shelving, etc.) and each item needs to be placed into one. Imagine the costs involved: real estate, labor, material handling equipment, cost of the storage medium. They all vary by rack type. The Value of each item is how quickly it moves through the warehouse (lines per day and seasonality). Now run this evaluation over 5,000+ SKU types. Not a simple problem anymore but it can make a big difference in the effectiveness of your distribution center or distribution network.

Thinking in terms of Knapsack provides definition to problems that previously would not have had much form. It allows an evaluation method for each of the options that must be considered as long as there is an ability to assign a Cost and Value. Cost could be anything from money to size to weight to business flexibility. Likewise, Value could be money, growth potential, profit potential or speed. Assuming that a very reliable and understandable Cost and Value are assigned to each decision variable, a solution can be reached.

Obviously not all problems can fall be solved using Knapsack and not all solutions reached by using this method will be optimal. There are some grey areas around the theory. For certain Cost/Value ratios it is better to not fill up the bag than to continue filling it. Some decisions allow you to pick an option multiple times with decreasing value each time (if you want to pack three books and two boxes of matches). However, it provides the framework to begin thinking through some of the decisions facing you today. Making decisions is one of the most difficult jobs in business and sometimes it is near impossible to make them without outside help. The cost of making a bad decision usually outweighs the cost of bringing in help to make the right one.



Technorati Tags: knapsack, consulting, decision making