optimization - Branch and Bound - 存储什么

Question

我读过不止一本书（包括 Wolsey），在实现分支定界算法时，不需要存储整个树，只需要存储活动节点的列表（据我所知，叶节点）。

问题是，如果我没有每个祖先的边界，我无法理解如何在分支后计算出新的边界。

对此进行一些澄清将不胜感激。

Answer 1

好的，让我们举个例子。假设您正在实现一个相当幼稚的整数程序求解器，它试图通过求解其 LP 松弛来求解二进制整数程序，如果它没有得到整数解，则在某个变量上分支。假设您有一个最大化问题。

让我们考虑一下恰好在一个分支之后会发生什么。你解决了根子问题，并假设它给你一个目标值为 10 的分数解。然后你在一个变量上进行分支，给你一个最优目标值为 9 的左子问题和一个最优目标值为 8 的右子问题。

我们从根子问题中得到了 10 的全局界限。我们还知道每个积分解都存在于左子问题或右子问题中，并且我们知道左子问题没有优于 9 的解，右子问题没有优于 8 的子问题。那么没有优于 9 的解到根子问题，即使根 LP 松弛不足以告诉我们这一点。

通常，您的最佳全局界限是任何活动子问题的最差界限。深思熟虑的子问题是无关紧要的，因为它们不能包含比您的现任者具有更好的客观价值的可行解决方案。已分支的子问题无关紧要，因为它们的边界应该由其子问题中最弱的边界支配。