带概率分布L1偏差约束的有界背包最大化问题LP松弛的求解策略问询
带概率分布L1偏差约束的有界背包最大化问题LP松弛的求解策略问询
我现在遇到了一个和经典有界背包LP松弛问题很相似的优化问题,想请教下大家的求解思路:
首先先回顾下已知的经典情况:
权重$w_i=1$的有界背包最大化问题的LP松弛模型如下:
$$
\begin{align}
&\underset{x}{\max} \sum_i c_i x_i \
& st \sum_i x_i \leq W \
& \forall i, 0\leq x_i \leq n_i
\end{align}
$$
这个问题的最优解策略我已经明确:按照$c_i$从大到小的优先级选取物品即可。
而我当前面临的问题可以表述为如下LP模型:
$$
\begin{align}
&\underset{x, p}{\max} \sum_i c_i x_i \
& st \sum_i x_i \leq W \
& \forall i, 0\leq x_i \leq p_i \
& \lVert p-\hat{p}\rVert_1 \leq \delta
\end{align}
$$
这里的$p$和$\hat{p}$都是概率分布,且满足$W\leq 1$。简单来说,我们可以优化每个物品的选取数量,但$p$与参考分布$\hat{p}$的L1偏差不能超过$\delta$。
新增这个L1偏差约束后,最优解的策略会发生怎样的变化呢?有没有像经典问题那样直观的物品选取规则可以遵循呀?
备注:内容来源于stack exchange,提问作者Lweber17
相关产品推荐
相关产品推荐

