线性编程可轻松用于MKP [英] linear programming relaxed for MKP

问题描述

如何计算以找到这种松弛.我应该怎么知道才能找到它.假设我有n个物品，有m个背包.所以我想知道放松的次数.至少有人能给我一些想法吗?我已经搜索了一段时间了.互联网上有一些文章，但不清楚.请至少有人对我说，你应该读这个东西，你应该知道这个东西，所以我将不胜感激

谢谢

解决方案

我认为您真正的问题是线性松弛背包问题的确切定义是什么?"，因此我将假设是正确的.

简短的答案是线性松弛 KP是0-1 KP [1]的小数部分.

在数学上，您要做的就是将限制"x_i属于{0，1}集"转换为"x_i必须是0到1之间的任何实数"，其中x_i是解决方案背包中的第i个物品.

名称来自0-1 KP是整数编程问题的事实. 线性"一词表示解决方案变量可以采用连续值.

但是，并非所有松弛都是线性的.您可能想查看此 Wikipedia页面他们.

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

how to calculate to find this relaxation. What should i know to find it. Suppose i have n items and m knapsack . So i wanted to know the number of m relaxation. Does anybody can give me some idea at least. I have been searching it for while. There is some article on internet but not much clear. Please at least someone say to me you should read this thing , you should know this thing e.i so i will very appreciate

Thank you

解决方案

I think your real question is "what is the exact definition of a Linear-Relaxed Knapsack Problem?", so I'm going to answer assuming it is.

The short answer is that a linear-relaxed KP is the fractionary version of a 0-1 KP [1].

Mathemathically, all you have to do is to convert the restriction "x_i belongs to the {0, 1} set" and convert it to "x_i must be any real number between 0 and 1", where x_i is the quantity of the i-th item in your solution backpack.

The name comes from the fact that the 0-1 KP is an integer programming problem. The 'linear' term means that the solution variables can assume continuous values.

Not all relaxations are linear, though. You might want to check out this Wikipedia page for them.

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

这篇关于线性编程可轻松用于MKP的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！