algorithm - 最长路径实现的分支定界策略

Question

我正在研究一个必须用分支定界算法解决的问题。假设我们有 n 个加油站，距起点的距离值不同。站有不同的利润。我们希望利润最大化，但每个站必须远离至少 K 长度。我用动态算法解决了这个问题，但找不到分支定界算法的解决方案。实际上，我需要一个好的目标函数来确定界限。我尝试了很多功能，但都失败了。谢谢。

例子: n=5 k=10

距离值 l1=5, l2=15, l3=23, l4=30, l5=38

利润: p1=7, p2=3, p3=10, p4=12, p5=6

Answer 1

这是一个相当典型的打包问题。我们可以像这样将它表述为一个整数程序。如果我们打开 i 站，则 x_i 为 1，否则为 0。那么目标就是

          n
maximize sum profit_i x_i.
         i=1

约束条件是我们不能在 k 距离内开设两个站点。我们可以在站点上滑动一个长度为 k 的窗口，为每个最大子集发出一个约束。对于距离值 l_1 = 5、l_2 = 15、l_3 = 23、l_4 = 30、l_5 = 38 和 k = 16，我们有约束

x_1 + x_2       <= 1    (y_1)    { 5, 15}
x_2 + x_3 + x_4 <= 1    (y_2)    {15, 23, 30}
x_3 + x_4 + x_5 <= 1    (y_3)    {23, 30, 38}.

最后各站开不开。

for all i, x_i in {0, 1}

二元性

我们遇到所有这些麻烦的原因如下。首先，我们可以通过将 x_i in {0, 1} 替换为 x_i >= 0 来放宽约束。现在我们有一个线性程序。我们知道

value of linear program >= value of integer program,

因为整数规划的每个解都是线性规划的有效解。线性规划的美妙之处在于它们有一个对偶规划，在某些技术约束下，通过 LP 对偶，满足

value of dual program = value of linear program >= value of integer program.

这很重要，因为这里的对偶规划是一个最小化，所以任何旧的解决方案都会给我们一个原始整数规划的界限(即我们真正关心的问题)。

双程式

这是从线性程序中机械导出的。下面我将直观地解释一下。通用版本:

          m
minimize sum y_j
         j=1
for all i, sum over windows j containing station i of y_j >= profit_i
for all j, y_j >= 0.

具体版本(上述具体 LP 的双重版本):

minimize y_1 + y_2 + y_3
y_1       >= profit_1    (x_1)
y_1 + y_2 >= profit_2    (x_2)
y_2 + y_3 >= profit_3    (x_3)
y_2 + y_3 >= profit_4    (x_4)
y_3       >= profit_5    (x_5).
y_1, y_2, y_3 >= 0.

直觉上，我们正在计算对每个窗口征税多少，这样 build 任何车站都是一个收支平衡的提议。我们征收的税越少，车站的值(value)就越低。

原始对偶近似

对偶程序可以通过 LP 求解(实际上可能是整数最优；这是变相的最短路径问题)。这是一个更容易实现的近似算法。

如果每个 y_i 出现在未满足的对偶约束的左侧，则它是事件的。当一些 y_i 处于事件状态时，我们以相同的速率连续增加所有事件的 y_i。在实践中，我们首先找出满足哪个约束，然后直接将时间步长到该点。

让我们假设约束和以前一样

y_1       >= profit_1 = 1
y_1 + y_2 >= profit_2 = 2
y_2 + y_3 >= profit_3 = 4
y_2 + y_3 >= profit_4 = 5
y_3       >= profit_5 = 3.

最初所有变量都为 0 并且处于事件状态。当它们达到 1 时，profit_1 和 profit_2 约束得到满足。因此 y_1 被停用，因为它不参与任何其他约束。我们继续将y_2和y_3增加到2，然后满足profit_3约束。这两个变量都参与了 profit_4 约束，因此它们保持事件状态。当我们增加到 2.5 时，profit_4 约束得到满足，y_2 不再有效。我们继续，将 y_3 增加到 3 以获得 y_1 = 1 和 y_2 = 2.5 和 的最终解决方案>y_3 = 3，值 6.5。最优值是(例如)y_1 = 1 和 y_2 = 2 和 y_3 = 3，对于值 6。