algorithm - 组合最佳匹配

Question

假设我有一个 Group 数据结构，其中包含一个 Element 对象列表，这样每个组都有一个 唯一的 元素集。 :

public class Group
{
  public List<Element> Elements;
}

并假设我有一个需要某些元素的人群列表，这样每个人群都有一组唯一所需元素:

public class Population
{
  public List<Element> RequiredElements;
}

我对每个定义的组都有无限数量，即它们不会被人群消费。

假设我正在查看一个特定的Population。我想找到组的最佳匹配，这样多余的元素最少，并且没有不匹配的元素。

例如:我的人口需要木材、钢铁、 Cereal 和煤炭。唯一可用的组是 {wood, herbs}，{steel, coal, oil}，{grain, steel} 和 {herbs, meat}。

最后一组 - {herbs, meat} 我的人群根本不需要，所以没有使用。所有其他的都需要，但不需要草药和油，所以它被浪费了。此外，钢材在最小集合中存在两次，因此也浪费了一批钢材。此示例中的最佳匹配 的浪费为 3。

因此，对于几百个 Population 对象，我需要找到最小浪费最佳匹配并计算有多少元素被浪费了。

我该如何开始解决这个问题？一旦我找到匹配项，计算浪费就变得微不足道了。一开始就很难找到匹配项。我可以列举出所有的可能性，但对于几千人和数百个群体来说，这是一项艰巨的任务。特别是考虑到这整个事情都在模拟退火算法的每次迭代中。

我想知道我是否可以将整个事情表述为混合整数程序并在每次迭代时调用像 GLPK 这样的求解器。

希望我已经正确解释了问题。我可以澄清任何不清楚的地方。

---

这是我的二进制程序，对于那些感兴趣的人...

x 是决策向量，是 {0,1} 的一个元素，表示相关人群是否从第 i 组接收/未接收。每个组都有一个条目。

b 是列向量，是 {0,1} 的一个元素，表示相关人群需要/不需要哪些资源。每个资源都有一个条目。

A 是一个矩阵，是 {0,1} 的一个元素，表示什么资源属于什么组。

程序是:

最小化:((Ax - b)' * 1-向量) + (x' * 1-向量);

服从:Ax >= b;

约束只是说必须满足所有必需的资源。目标是尽量减少所有过量和使用的组总数。 (即使用 1 组时 0 过量优于使用 5 组时 0 过量)。

Answer 1

您可以为每个种群P 制定一个整数规划，如下所示。使用二进制变量 x_j 表示是否选择组 j。令 A 为二进制矩阵，当且仅当项目 i 出现在组 j 中时，A_ij 为 1。那么整数规划为:

min E_i,j (x_jA_ij)

s.t. E_j x_jA_ij>= 1 对于 P 中的所有 i。

x_j = 0, 1 表示所有 j。

请注意，您可以通过从上述 IP 的最优解中减去 |P| 来获得最小的浪费。