algorithm - 整数线性规划特例

Question

我正在尝试解决整数线性规划问题的一个特例，但我似乎在算法上有问题。

具体来说，假设您有一些二进制变量 x_{1}, ... x_{n} 和一些形式的不等式:

i.e. x_{2} + x_{3} + x_{10} <= 2

请注意，不等式的系数均为 1，右侧始终为左侧的变量数减 1。

另外，请记住变量 x_{1}, ..., x_{n} 可以取 0 或 1 的值。

这是一个家庭作业(编写程序)，但我找不到可以开始的算法。

我尝试了 DP 和 Network Flow，但没有结果。

目标函数(在编辑中迷路了)是最大化总和:

x_{1} + ... + x_{n}

Answer 1

问题等同于Set Cover: http://en.wikipedia.org/wiki/Set_cover_problem#Integer_linear_program_formulation .一种容易理解的方法是将 x_{i} 替换为 1-y{i}，这给出了一个等效的 0-1 线性规划问题，即

maximize (1-y_{1}) + (1-y_{2}) + ... + (1-y_{n}) = n - (y_{1} + ... + y_{n}),
which is equivalent to minimizing y_{1} + ... + y_{n},

subject to the following family of inequalities indexed by j: 
  (1-y_{i_{1j}}) + (1-y_{i_{2j}}) + ... + (1-y_{i_{kj}) <= k-1,
which are equivalent to:
  y_{i_{1j}} + y_{i_{2j}} + ... + y_{i_kj} >= 1

该问题的等效公式是 Set Cover 的 0-1 整数线性规划公式。

在这种情况下，贪婪算法会提供一个合理的近似值。确定 x_{i0} 中哪个出现在约束中最频繁，并将其设置为 0。现在满足 x_{i0} 出现的所有约束，因此可以将它们从考虑中移除，并且变量 x_{i0} 可以从目标中移除。对在剩余约束中最常出现的变量 x_{i1} 重复，等等。

或者，实线性规划也将提供近似值。

由于 Set Cover 是 NP-hard，您将能够找到的最佳精确解在时间上呈指数级增长。一个简单的算法会尝试所有可能性(遍历从 x_{n}x_{n-1}...x_{1}x_{0} = 00...00 到x_{n}x_{n-1}...x_{1}x_{0} = 11...11 = 2^(n+1)-1。肯定有更快的 (但仍然是指数时间)算法，如果你搜索的话。