線性規劃輕鬆爲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