optimization - docplex 如何找到最佳界限？

Question

我真的不明白 CPLEX 首先是如何计算最佳界限的。据我了解，CPLEX 需要探索所有节点以找到最佳界限或最大化或最小化所有可行解决方案的目标值。知道在大多数情况下探索所有节点是不可行的，CPLEX 如何首先找到这个最佳界限？对论文或文件的任何参考表示赞赏。先感谢您。

Answer 1

最佳界限来自 LP 解决方案。如果变量不需要具有整数值，这是可能的解决方案。没有整数解决方案可能比这个“宽松”解决方案具有更好的目标值，因此它提供了目标的有效界限。随着 CPLEX 探索和消除 B&B 树的某些部分，它可以使用连续更好的值更新边界。