0

我正在尝试实现分支定界技术，以用轴平行线覆盖点。对于每个子问题，我将我的 LP 解决方案视为 LB，将迭代舍入解决方案视为 UB。首先，我正在考虑一个小数值变量（在应用 LP 之后），对于 0 和 1 值，我正在考虑 SP1 和 SP2 作为我的子问题。对于每个 SP1，我有 UB1 和 LB1，对于每个 SP2，我有前面提到的 UB2 和 LB2。然后我正在检查

i) 如果 (LB1=UB1 或 LB2=UB2) 然后停止

ii) 如果 (UB1 >= LB2) 然后求解 SP2

iii) 如果 (UB2 >= LB1) 然后求解 SP1

我不确定，我正在考虑正确的方法。因为在大多数节点中，ii) 和 iii) 都在发生（尽管一次只有一个“if”正在执行）。我使用正确的方法吗？任何帮助将不胜感激。

谢谢。

4

1 回答 1

1

我不熟悉您的“迭代舍入”过程，但我认为它是正确的。

如果你比较上限和下限，你可能会满足条件 ii) 和 iii)，特别是在求解过程的开始，因为你的解 GAP 可能很大。一种更常见的方法是使用所有可用子问题中最有希望的下限来解决子问题。

你得到的答案是否合理？

于 2015-05-09T19:37:33.810 回答