线性规划轻松为MKP

Question

如何计算找到这种放松。我应该知道什么才能找到它。假设我有n件物品和m件背包。所以我想知道m放松的次数。至少有人能给我一些想法吗？我一直在寻找它。网上有一些文章，但不太清楚。请至少有人对我说，你应该阅读这件事情，你应该知道这件事EI，所以我会非常感激

谢谢

Answer 1

我认为你真正的问题是“什么是线性 - 的确切定义轻松的背包问题？“，所以我会假设它是回答。

简短的回答是一个线性松弛 KP是0-1 KP的用分数版本[1]。

在数学上，您所要做的就是将限制“x_i属于{0,1}集合”并将其转换为“x_i必须是0到1之间的任何实数”，其中x_i是数量您的解决方案背包中的第i个项目。

该名称来源于0-1 KP是整数规划问题。 “线性”术语意味着解决方案变量可以假定为连续值。不过，并非所有的放松都是线性的。你可能想看看他们的this维基百科页面。

[1] http://en.wikipedia.org/wiki/Linear_programming_relaxation