9
$\begingroup$

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

Improve this question
$\endgroup$
4
  • 3
    $\begingroup$ 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? $\endgroup$
    – prubin ♦
    Commented Aug 11, 2019 at 15:08
  • $\begingroup$ @prubin Yes, each item type $i$ can be selected multiple times without a priori limit. I edited the question to clarify this point. $\endgroup$
    – Libra
    Commented Aug 12, 2019 at 7:21
  • 2
    $\begingroup$ 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. $\endgroup$
    – prubin ♦
    Commented Aug 12, 2019 at 18:10
  • $\begingroup$ @prubin you are right, the average weight is meaningless, better if we can use a lower bound for the distribution. $\endgroup$
    – Libra
    Commented Aug 14, 2019 at 9:36

1 Answer 1

Reset to default
3
$\begingroup$

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.

Improve this answer
$\endgroup$
1
  • $\begingroup$ @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. $\endgroup$
    – Libra
    Commented Aug 12, 2019 at 15:36

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.