The knapsack problem

Imagine that you are going to a trip, and everything you have just a knapsack to carry on everything.
New-Unisex-black-backpack-students-backpack-small-travel-knapsack.jpg
The maximum weight you can carry is limited, say 14 kg.
There are a list of itens you’re considering to choose from. Each item has a weight and a value.
ValueWeight.PNG
Item, Value and Weight

 

Which of the itens do I choose, to maximize the value I can carry on my backpack?

 


The “Human method”

The first method described is the “human method”. How you and me would choose the itens.
I would choose the itens with greatest value for me, one by one, till the maximum weight.

In this example, I would choose itens 1 and 2, whose sum of values is 13.000 and sum of weights is 14. It is the “greedy” method, heuristically simple but can be suboptimal.

valueWeight2.png
First choice, the greedy method

 

In the end, I would take a look on my selection, and try to find if I can replace one of the chosen itens for two itens not choosed with greater value.
In this example, a simple inspection shows that the item 2 is too heavy for its benefits. It is better to replace it for itens 3 and 4.
valueWeight3.png
Picking after a more detailed inspection
The final selection contains itens {1, 3, 4}, with total value 14.000 (10.000 + 2000 + 2000) and weight 13 (8 +2+3).
The problem is when the list is very large, with tens or hundreds of itens. It is several timer harder to figure out a good solution.
The human method is very important. It is suboptimal, but it is fast. Humans are good problem solvers. We use intuition and millions of years of understanding of nature, to solve this kind of problem. Human reasoning can be a source for fast approximation algorithms.
Even when the problem is large, humans can solve in a heuristically interesting way. The world is also Pareto, what means that 20% of itens will have 80% of the value. In a intuitive way, I would focus my attention in those 20% and apply the above described method.
In real world application problems, I always respect a lot the people who make the analysis and try to someway incorporate some of theirs thinking in my models – a human centered analytics.

Mathematical formulation

The formulation of the knapsack problem via integer programming is straightforward.
If xi is the decision variable, binary (1 is to carry the item, 0 is to not carry) then
KnapsackFormulation.PNG
In the next posts I’ll show how to solve it with computational methods, as dynamic programming,  integer programming using solver and evolutive metaheuristics.
Arnaldo Gunzi
A big fan of real world heuristics