1

这是我的问题场景：

我有几千个对象。每个对象有 256 个布尔维度（真或假）。我想找到这样的集群

  1. 每个集群都有最小数量的真实维度（集群的维度是真实的，如果该集群中的任何对象都将该维度市场设为真实）。
  2. 所有集群上所有真实维度的总和是最小的。
  3. 每个簇不大于某个预定义值。

不需要解决方案的最优性，但是算法应该很快。

我应该如何最好地解决这个问题？有推荐的算法吗？

注意：我已经对这个问题实施了蛮力方法，但速度很慢。

4

2 回答 2

2

您可以将其写为混合整数线性程序 (MILP)：

您有固定数量的集群和对象。
每个集群最多可以有 256 个真实维度。
如果对象 k 中的维度 i 为真，则参数D_{k,j}等于 1。

您有以下变量：

  1. d_{i,j}是一个二元变量，如果维度 j 是集群 i 的真实维度，则等于 1。
  2. o_{i,k}是一个二进制变量，如果对象 k 在集群 i 中，则该变量为真。

您有以下限制：

  1. 每个对象只能在一个集群中
  2. 一个维度在集群中为真，如果它在集群内的所有对象中都为真
  3. 每个簇只能容纳 M 个对象

第二个约束是一个棘手的约束，因为它感觉不是线性的，但实际上你可以线性地编写它。约束可以写成：

  1. C1对于所有 k
  2. C2对于所有 i 和 j
  3. C3对于所有我

目标函数可以是所有 的总和，d_{i,j}因此您可以最小化所有集群中所有真实维度的总和。

让我解释第二个约束：在右侧，您计算集群 i 内的元素数量，减去维度 j 设置为 1 的对象数量。如果所有对象都具有维度 j，则这等于零，否则为正值。

如果计算结果为零，则d_{i,j} 必须等于 1 以避免违反约束。如果不是，d_{i,j}可以是任何东西（零或一）。这是有效的，因为d_{i,j}会出现在目标函数中，这意味着当程序在零或一之间进行选择时，它将选择零。

写完后，您可以使用商业求解器（如果有的话，他们会向学生提供免费许可证，如果您是其中之一）或Coin-OR来解决它。

提醒一下：解决 MILP 是一个NP 完全问题。

于 2012-11-19T21:55:58.493 回答
0

所以我决定写下我想出的（理论）解决方案。部分是因为它可能对我有帮助（有关此内容的更多信息，请参见下文），部分是因为它可以为任何感兴趣的人提供一个体面的解决方案。这是一个线性方程组，可以使用Simplex Algorithm 求解。

我想出的约束是：

1) 每个对象都在一个簇中

2）每个簇最多有 M 个（常量）对象

3) 集群的维度为真，当且仅当该集群中的至少一个对象将该维度设置为真时

我将解释现在如何强制执行约束：

假设有 n 个对象和 k 个簇。我们考虑总和（在下面这是一行）

x 1 1 + x 2 1 + x 3 1 + ... + x n 1 + d 1 1 + d 2 1 + d 3 1 + ... + d n 1 +

x 1 2 + x 2 2 + x 3 2 + ... + x n 2 + d 1 2 + d 2 2 + d 3 2 + ... + d n 2 +

...

x 1 k + x 2 k + x 3 k + ... + x n k + d 1 k + d 2 k + d 3 k + ... + d n k

在哪里

x a c为真当且仅当对象 a 为 int 簇 c

如果集群 c 中的维度 b 为真，则d b c为真

由于集群对象总是更好（或至少从不有害），我们知道集群的数量是ceil(objects 除以 M)。为简单起见，我现在将省略变量，只写系数。

1)每个对象都在一个簇中

10...0 0...0 10...0 0...0 10...0 0...0 ... 10...0 0...0 = 1

010...0 0...0 010...0 0...0 010...0 0...0 ... 010...0 0...0 = 1

...

0..01 0...0 0...01 0...0 0...01 0...0 ... 0...01 0...0 = 1

这将强制每个对象都在一个集群中。这理论上可以允许对象在几个集群中具有部分（<1）。但是因为我们正在寻找最佳解决方案，所以这不会发生。

2）每个簇最多有 M 个（常量）对象

11...1 0...0 0...0 0...0 0...0 0...0 ... 0...0 0...0 <= M

0...0 0...0 11...1 0...0 0...0 0...0 ... 0...0 0...0 <= M

...

0...0 0...0 0...0 0...0 0...0 0...0 ... 11...1 0...0 <= M

对象的总和不大于 M。这个约束应该是明确的。

现在是棘手的部分：

3)集群的维度为真，当且仅当该集群中的至少一个对象将该维度设置为真时

对于每个维度和每个集群，考虑那些将该维度设置为 true 的元素（我们也可以考虑 false 元素，但它们无关紧要）。我们现在为它们中的每一个（以及每个集群）写一行

0..010...0 -10...0 0...0 0...0 ... 0...0 0...0 <= 0

其中 1 表示此对象（在此集群中）的此维度设置为 true，而 -1 表示该维度（在本例中为第一个）。如果对象被设置在这个集群中，那么这个集群的维度必须是 1 (1*1 -1*d <= 0)，如果没有设置，维度也可以是零 (0*1 - 1*d < = 0)。

对于第一个集群中的第二个维度，这看起来像这样：

0..010...0 0-10...0 0...0 0...0 ... 0...0 0...0 <= 0

对于最后一个集群和最后一个维度，像这样

0...0 0...0 0...0 0...0 ... 0..010..0 0...0-1 <= 0

现在我们可以简单地最小化 x a c的总和，我们就完成了。

这可能会以更好的方式写下来，但我希望它是可以理解的。

现在问题如下：我正在处理 70 个集群、3000 个对象和 2300 个维度。使用上述方法会产生 371000 个变量（集群 * 对象 + 集群 * 维度）和 1292095 行（将行估计为对象 + 集群 + 维度 * log(objects) * 集群）

我倾向于认为最佳解决方案是不可行的。即使您仍然可以优化此处描述的方法，类似的方法也不太可能表现得更好。所以现在我正在寻找好的近似值，欢迎任何关于如何解决这个问题的想法。

谢谢 ：）

于 2013-02-10T17:49:09.963 回答