# Knapsack problem with uncertain profits

I am trying to find the optimal strategy for a game where the goal is to pick a number of items where the profit is uncertain but the weights are set. Each round of picking is a specific point in time, and each round is partially independent from the past (think sports games). This is basically a version of the knapsack problem. (see Knapsack Problem)

Here is the problem :
Maximize: $$\sum _{j=1}^{N}\sum _{j=1}^{\left | G_{i} \right |}p_{ij}x_{ij} +\sum _{j=1}^{\left | G_{s} \right |}p_{sj}x_{sj}$$ Subject to: \begin{align} (\sum _{i=1}^{n}\sum _{j=1}^{\left | G_{i} \right |}w_{ij}x_{ij} +\sum _{j=1}^{\left | G_{s} \right |}w_{sj}x_{sj})&\leq c \\ \sum _{j=1}^{\left | G_{i} \right |}x_{ij} &= 1 \\ \sum _{j=1}^{\left | G_{s} \right |}x_{sj} &= k \\ x_{ij} \in \{0,1\}\\ x_{sj} \in \{0,1\} \end{align} Notation:
N the number of items
n the number of groups
c the capacity of a single knapsack
G = {$G_{1},...,G_{n}$} the set of groups
${\left | G_{i} \right |}$ the number of items in group $G_{i}$
${\left | G_{s} \right |}$ the number of items in group $G_{s}$ (special group)
$p_{ij}$ the profit of item j of group $G_{i}$
$w_{ij}$ the weight of item j of group $G_{i}$
$p_{sj}$ the profit of item j of group $G_{s}$
$w_{sj}$ the weight of item j of group $G_{s}$
k restraint of group $G_{s}$

So for example, say you have 100 items per group where each item has a profit and a weight. In this particular instance, the profit is uncertain and therefore you must use regression to come up with a reasonable estimate.

So far, I am using linear regression paired with a k-NN algorithm to predict the profit of each item based on past observations. I also use a decision tree learner for a classification between items which have either a positive profit or a negative profit (again using past observations).

I'm going to use GLPK to solve the knapsack problem. In fact, I've already coded the module and its ready to go. The problem is with the uncertainty of the profits.

I'm having a tough time conceptualizing uncertainty and risk. Is there a way to segregate item choices according to risk? Perhaps I can look at the historical variance in profit value for each item? Is there any particular method that would be useful here? (Something akin to Monte Carlo, etc?)

• What exactly are you predicting? If you could add rephrasing of your question in mathematical terms, that would clarify things a bit. – mpiktas Jul 1 '13 at 10:18
• Okay, added the formula for the knapsack problem. To be 100% clear, I am trying to predict profit values of each item based on past observations of those items. I am facing uncertainty by using an algorithm or statistical method and I would like to try and account for that uncertainty and know how to manage it when picking items for the knapsack. – Aketay Jul 1 '13 at 14:49

In the case of a stochastic optimization such as this, you really should have an objective function that weights risk. Ideally, this would be a utility function, which can be converted to an expected utility when there's a probability distribution on reward and used instead. (Note this assumes that the utilities of items are independent of each other, and of whether the other items are included in your final selection or not.)

If you simply replace:

Maximize: $\sum _{j=1}^{N}\sum _{j=1}^{\left | G_{i} \right |}p_{ij}x_{ij}$

with maximizing the expected return:

Maximize: $\text{E}\sum _{j=1}^{N}\sum _{j=1}^{\left | G_{i} \right |}p_{ij}x_{ij} = \sum _{j=1}^{N}\sum _{j=1}^{\left | G_{i} \right |}\text{E}(p_{ij})x_{ij}$

you'll get an objective function where you are maximizing the expected return given the constraints. This requires nothing more than substituting $\text{E}p_{ij}$ for $p_{ij}$ in your objective function - and, from an estimation perspective, all you would need to do is substitute the predicted values of the $p_{ij}$ in the objective function. Grouping by risk (however measured) is irrelevant with this objective, unless for some reason it improves the estimation of the $p_{ij}$.

If, on the other hand, you can form a utility function $U(p)$, then the expected maximum utility function becomes:

Maximize: $\text{E}U(\sum _{j=1}^{N}\sum _{j=1}^{\left | G_{i} \right |}p_{ij}x_{ij}) = \sum _{j=1}^{N}\sum _{j=1}^{\left | G_{i} \right |}\text{E}U(p_{ij})x_{ij}$

(assuming, once again, a separable utility function) and the objective of your statistical analysis is to find a probability distribution (e.g., a posterior probability distribution) of the $p_{ij}$ that you can use to form $\text{E}U(p_ij)$. (See, for example, Savage, DeGroot, or Raiffa and Schlaifer on the very strong links between Bayesian statistics and utility theory.) You would then substitute $\text{E}U(p_{ij})$ into your objective function and solve just as if it were a deterministic problem - which it is, since you're maximizing an expected value and all the randomness is hidden inside the "expected value" part.

• I don't have to to implement this, but I assume this is a good solution. Anyone else confirm? – Aketay Oct 6 '13 at 18:45