algorithm - 具有附加约束的线性分配

Question

在一个标准的线性分配问题中，我可以使用匈牙利算法来实现 O(n^3)。如果添加额外的约束怎么办？示例:

具有 4 个智能体的“常规”LAP 具有约束矩阵

结果向量 b = [1 1 1 1]。

匈牙利算法将按预期解决此类问题。但是，如果添加另一个约束会怎样，使得约束矩阵为

结果向量 b = [1 1 1 1 0] ??

也就是说，除了在标准线性和约束下最小化成本函数外，我还必须考虑像这样的约束

这个总和产生上面附加矩阵的最后一行。

显然，生成的约束矩阵不再是完全幺模的。当然，标准的 MILP 可以解决这个问题，但是 NP 很难。我的问题是:是否有类似匈牙利的算法可以在多项式时间内解决这个 LAP？

Answer 1

通常，具有边约束的网络流问题是 NP-Hard。例如，具有非负边成本的最短路径问题是多项式可解的。例如，您可以使用 Dijkstra 的最短路径算法。 (分配问题是网络流问题的特例。)

但是，如果您添加单个约束，规定使用的边数应小于某个常数，则随之而来的约束最短路径问题就是 NP-Hard。

因此，您的问题不太可能有多项式算法。