algorithm - 我如何有效地找到这个约束系统中变量的最小值和最大值？

Question

我有一个系统，我需要计算每个变量的可能值范围(我不需要找到系统的解决方案)。这是示例系统的说明:

每条蓝线是一个节点(由其上方的标签命名)，灰线是节点之间的边。给定一个初始约束:比如边BC可以是0到1之间的任意实数，边BE可以是任意大于等于9的数，节点不能跨越其他节点。将它们想象成可以拉伸(stretch)和缩回并插入蓝色板的金属棒会很有帮助。

我的目标是计算每条边的最小和最大长度。起始约束建立了系统，但最终结果可能比它们更受约束。例如，边 DF 的起始最小值/最大值为 (2,∞)，但您可以看到它实际上不能小于 3，因为收缩它会将 D 拉入 E，将 E 拉向 F，而 EF 有一个最少 3 个。我相信最终结果是这样的:

需要注意的是，我需要一种可以扩展到数十万个节点的算法，这将比这个例子连接得更密集。它的运行时间不能呈指数增长，因为我还必须运行该算法数十万次。

我尝试了一种方法，它给出了一些更受约束的值，但不是最受约束的值。为了可视化该方法，我基本上将所有盘子尽可能地拉到左边，然后记录每个盘子的最大位置。然后我也这样做，把他们拉到右边。然后，对于每条边，我只是找出每个板的值之间的差异。此方法非常有效地找到最大值，但问题是当您遇到本例中的情况时，其中 CD 被 BC 和 DE 有点“锁定”为 BE。它不能是 6，因为系统只允许它比 9 短 2。我需要一种方法来找到真正的最小值 7。我的方法没有捕捉到这种“锁定”关系:当你拉 C all一直往左拉，BC 为 0，D 一直往右拉，DE 为 0，但 CD 为 6 时，它们不能都为 0。

在这个例子中，很容易看出 CD 受 BE 约束，但在实践中，系统会比这个例子更密集、更大，找到这种情况似乎并不容易。如果该方法涉及在本地搜索，我担心它的扩展性会很差，但这可能是唯一的方法。

如果将其建模为线性规划问题(AB + BC = AC，AB>1 等)，也许可以利用该系统的某些属性:约束的所有系数都是1，约束中只有加减法。

有没有人对如何解决这个问题有任何建议？或者对我实际希望的运行时复杂性有什么见解？谢谢!

Answer 1

给定

I need an algorithm that can scale up to hundreds of thousands of nodes, which would be more densely connected than this example. It can't exponentially increase in running time, since I also have to run this algorithm hundreds of thousands of times

你好像有麻烦了。

对我来说这看起来像是以下问题:

ICSP (Interval Constraint Satisfaction Problem). “Given a set E of equations relating a set of variables associated with interval domains. Refine the domains as far as possible without losing possible exact solutions of E, i.e., determine for each variable the minimal consistent subinterval within its domain.”

对 E(线性不等式)做了一些假设。很难读出您正在寻找哪种隐含界限(数值与积分)，这可能会产生巨大影响。

虽然这看起来像是一个多项式时间问题(如果不做更多研究就很难掌握循环/非收敛属性；请参阅引用论文；可能与 float 学限制与区间算术有关)，这些方法可能不会根据您的数字进行缩放。

看看

Belotti, Pietro, et al. "On feasibility based bounds tightening." (2012).

给出了一些概述。

您会发现许多关键字指向不同的研究社区(数学优化、约束规划、AI)，例如:

• 基于可行性的界限收紧
• 边界传播
• 限制/范围缩小
• 域过滤/减少。

有一种简单的2n LP 求解 方法，但考虑到您的数字，无论使用单纯形法还是内点法，这似乎都不够。

该论文还介绍了一种单 LP 方法，但它可能无法扩展。

如果全局选择不可行(给定一些时间范围)，则取决于这个问题对你有多重要，你想投资多少以及你的确切目标是什么，你可以查看那篇论文，它是引用文献和关键字并可能检查数学优化求解器中的内容，包括(链接指向这个核心问题):

• Couenne (这与论文有一定联系；尽管实现的方法可能与论文不同)
• SCIP
  • (许可!-> 不得用于商业用途)
• Clp

和其他人，其中每一个都应该包括一些限制边界的方法(用于线性等式)。总的来说，我希望像 Couenne 这样的全局解决者在这一步投入更多时间；因为与 Clp 等 LP 求解器相比，剩余的优化通常很容易控制这一点。