9

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

Libra
  • 937
  • 5
  • 14
  • 3
    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 '19 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. – Libra Aug 12 '19 at 07:21
  • 2
    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 '19 at 18:10
  • @prubin you are right, the average weight is meaningless, better if we can use a lower bound for the distribution. – Libra Aug 14 '19 at 09:36

1 Answers1

3

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
  • 1,110
  • 8
  • 17
  • @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. – Libra Aug 12 '19 at 15:36