2

我有一个有向图。每条边都有一个固有的“权重” w_ij，这是固定的。每个节点都有一个v_i可以配置的值，除了“根节点”（没有传入边）和“叶节点”（没有传出边）的值是固定的。

每条边的“按节点调整”边值由下式给出： s_ij = w_ij + v_j - v_i也就是说，我们通过其相邻节点值的差异来调整边的值。当然，改变节点的值会影响 的值s_ij。

我对 的值感兴趣min{s_ij}，并希望找到将值分配给节点的最优值，从而使这个“瓶颈”值最大化。

关于如何做到这一点的任何想法？

注意：从根到叶的循环和“固定路径”为最小值提供了上限（例如，在循环中，节点差异的总和始终为 0，因此您可以获得的最好结果是边缘固有的平均值权重）。但由于循环和“固定路径”可能重叠，因此尚不清楚是否可以达到最小上限。该解决方案很可能首先涉及找到此类路径/循环。

4

2 回答 2

4

如果我理解正确，这个问题可以表述为这个线性程序。调整输入，v_i = 0以便每个顶点i都是源或汇。

maximize z

subject to
for every ij,
    z + v_i - v_j <= w_ij  (i.e., z <= w_ij + v_j - v_i = s_ij)

variables
z unbounded
for every vertex i not a source or sink,
    v_i unbounded

这是双重程序。

minimize sum_ij of w_ij y_ij

subject to
sum_ij y_ij >= 1
for every vertex i not a source or sink,
    sum_j y_ij - sum_j y_ji = 0

variables
for every ij,
    y_ij >= 0

如果我们不从守恒约束中排除源和汇，这将是最小平均成本周期的线性规划。就目前情况而言，我们仍然可以使用流分解技术来证明存在最优值，即源-汇路径或循环，我相信对寻找最小平均成本循环的简单算法稍作修改是适用于此。

一旦获得最佳值，您就可以通过使用权重运行 Bellman-Fordz*来找到潜力。我很抱歉没有提供更多细节，但我有一种唠叨的感觉，我正在做你的功课。v_iw_ij - z*

于 2013-06-23T17:09:04.257 回答
1

我可以立即想到两种不同的方法：

首先，你可以对答案进行二分搜索。 检查你是否可以获得给定的最小边权重与最短路径问题密切相关——你有一堆关于节点权重差异的约束，每个约束的形式为 w i - w j >= l ij具有一定的 w 是固定的。

其次，您可以进行次梯度优化。您想要最大化边缘权重的最小值。在这里计算一个次梯度真的很容易。

这个问题可能有很多有用的结构，我在这里没有利用。您可以尝试写下线性编程放松并尝试一下。这样做——更深入地分析问题——几乎肯定会导致比上述任何一种方法更快的算法。

于 2013-06-23T17:02:27.147 回答