我正在研究一个问题，我必须用分枝定界算法来解决。假设我们有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
最佳答案
这是一个相当典型的包装问题。我们可以这样把它表示成一个整数程序如果我们打开stationx_i或1则设i为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.
直观地说，我们正在计算每个窗口要缴税多少，以便建立任何车站都是一个盈亏平衡的提议我们要收的税越少，车站就越不值钱。
原始对偶逼近
对偶规划可以用lp（实际上可能是整数最优性，这是一个伪装的最短路径问题）来求解。这是一个更容易实现的近似算法。
如果每个
y_i出现在未满足的双重约束的左侧，则它处于活动状态当某些y_i处于活动状态时，我们以相同的速率连续增加所有活动y_is。在实际应用中，我们首先计算出满足哪个约束，然后将时间直接步长到该点。假设约束条件和以前一样
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。关于algorithm - 最长路径实现的分支定界策略，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/30019445/