1

我正在研究一个必须用分支定界算法解决的问题。假设我们有 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

4

1 回答 1

0

这是一个相当典型的包装问题。我们可以像这样将其表述为一个整数程序。如果我们打开车站或其他方式，请x_i允许。那么目标是1i0

          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.

直观地说，我们正在计算对每个窗口征收多少税，这样建造任何车站都是一个收支平衡的提议。我们必须征收的税款越少，车站的价值就越低。

原始对偶近似

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

如果每个都出现在未满足的对偶约束的左侧，则每个y_i都是活动的。虽然有些是活跃的，但我们以相同的速率连续y_i增加所有活跃的 s。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的最终解决方案，为 价值。对于 value ，最优值是 (eg) and and 。y_1 = 1y_2 = 2.5y_3 = 36.5y_1 = 1y_2 = 2y_3 = 36

于 2015-05-04T01:38:20.727 回答