# Static stochastic knapsack problem: unbounded version

In the static stochastic knapsack problem (SSKP) the weights $$w_i$$ of the items are distributed according to a probability distribution. Each item $$i \in I$$ can be selected at most once.

So, considering a binary variable $$x_i \in \{0, 1\}$$ and a set of $$N$$ scenarios $$W = \{\mathbf{w^1},\dots,\mathbf{w^N}\}$$ we can write constraints like the following (i.e. worst-case robust optimization):

$$\sum_{i \in I} w_{i}^{\xi} \cdot x_i \le C \qquad \forall \xi =1,\dots, N$$

where $$C$$ is the capacity of the knapsack. Or, in terms of a chance constraint program:

$$Pr\left(\sum_{i \in I} \tilde{w}_{i} \cdot x_i \le C\right) \ge 1-\alpha$$

where $$\tilde{w}_{i}$$ are random variables. Or other similar formulations (i.e. stochastic optimization)...

QUESTION: Considering the unbounded version of the SSKP, that is a problem in which:

• each item $$i$$ can be selected multiple times, without a priori limit besides what imposed by the total capacity $$C$$ of the knapsack (i.e. type $$i$$ with average weight $$\bar w_i$$ can be selected at most about $$\left \lfloor{\frac{C}{\bar w_i}}\right \rfloor$$ times),
• the weight of each item is stochastic,
• items of the same type $$i$$ can have different weights.

how can I express the constraints?

For example (I know it is not correct, just to "formalize" what I mean), let $$x_i \in \mathbb{N}$$ represent the number of items $$i$$ included in the selection, and $$\tilde{w}_{ij}$$ be the (stochastic) weight of the $$j$$-th instance of the $$i$$-th type, I would formally express the probabilistic constraint as follows (notice the variable $$x_i$$ in the summation, which is where I think I abused the notation):

$$Pr\left(\sum_{i \in I}\sum_{j=0}^{x_i} \tilde{w}_{ij} \le C \right)\ge 1-\alpha$$

Is it possible to deal with this type of constraint with a MIP formulation (not necessarily for the chance constraint)?

• When you say "unbounded version", do you mean that there is no a priori limit on the number of items of a given type $i$ that can be selected?
– prubin
Aug 11, 2019 at 15:08
• @prubin Yes, each item type $i$ can be selected multiple times without a priori limit. I edited the question to clarify this point. Aug 12, 2019 at 7:21
• If the distribution of weights for each item is bounded away from 0 (i.e., $w_i \ge L_i > 0$ with probability 1 for constant $L_i$, then you can put an upper bound of $\left\lfloor \frac{C}{L_{i}}\right\rfloor$ on the number of instances of item $i$. I don't think the bound based on the average weight is correct in general.
– prubin
Aug 12, 2019 at 18:10
• @prubin you are right, the average weight is meaningless, better if we can use a lower bound for the distribution. Aug 14, 2019 at 9:36

Couldn't you just introduce binary variables $$x_{ij}$$ and consider the sum
$$Pr\left(\sum_{i \in I}\sum_{j=0}^{\text{max}} \tilde{w}_{ij} x_{ij} \le C \right)\ge 1-\alpha$$
where max is chosen with respect to the capacity and the minimal appearing weight? If you want the elements chosen "in order", you could introduce constraints like $$x_{ij} \geq x_{ij+1}$$, but due to the stochasticity of the problem, this seems unnecessary.
• @j-fabian-meier thanks, I was thinking about something like this starting from a formulation of the (1D) Bin Packing Problem. Perhaps, customizing the $max$ for each type $i$ I can avoid introducing too many variables. Aug 12, 2019 at 15:36