我如何有效地找到这个约束系统中变量的最小值和最大值？
How would I efficiently find the min and max values of the variables in this constraint system?
我有一个系统，我需要计算每个变量的可能值范围（我不需要找到系统的解决方案）。这是示例系统的说明：
每条蓝线是一个节点（由上面的标签命名），灰线是节点之间的边。给定一个初始约束：比如边BC可以是0到1之间的任意实数，边BE可以是任意大于等于9的数，节点不能跨越其他节点。将它们想象成可以伸缩的金属条会很有帮助，从而推动蓝色板。
我的目标是计算每条边的最小和最大长度。起始约束建立了系统，但最终结果可能比它们更受约束。例如，边 DF 的起始 min/max 为 (2,∞)，但您可以看到它实际上不能短于 3，因为收缩它会将 D 拉入 E，将 E 拉向 F，然后将 EF至少有3个。我相信最终的结果是这样的：
需要注意的是，我需要一种可以扩展到数十万个节点的算法，这将比这个例子连接得更密集。它不能在 运行ning 时间内呈指数增长，因为我还必须 运行 这个算法数十万次。
我尝试了一种方法，它给出了一些更受约束的值，但不是最受约束的值。为了可视化该方法，我基本上将所有盘子尽可能地拉到左边，然后记录每个盘子的最大位置。然后我也这样做，把他们拉到右边。然后，对于每条边，我只是找出每个板的值之间的差异。此方法非常有效地找到最大值，但问题是当您遇到此示例中的情况时，其中 CD 是 BC 和 DE 的 "locked" 到 BE。它不能是 6，因为系统只允许它比 9 短 2。我需要一种方法来找到真正的最小值 7。我的方法没有捕获 "locking" 关系：当你拉C一直往左拉，BC是0，D一直往右拉，DE是0，但CD是6的时候不能都为0
在这个例子中，很容易看出 CD 受 BE 约束，但在实践中，系统会比这个例子更密集、更大，找到这种情况似乎并不容易。如果该方法涉及在本地搜索它，我担心它的扩展性会很差，但这可能是唯一的方法。
如果将其建模为线性规划问题（AB + BC = AC，AB>1 等），也许可以利用该系统的某些属性：事实上约束为1，约束中只有加减法。
有人对如何解决这个问题有什么建议吗？或者对我实际希望的 运行 时间复杂度有什么看法？谢谢！
听起来可满足性模理论在这里会有帮助。将您的长度约束作为初始公理（即 0 <= BC <= 1 等），以及一个可以让您添加距离的理论（即 AB + BC = AC 用于所有 A、B、C），并让 SMT 求解器计算它可以从中推断出的约束。如果您正在寻找的 "optimal" 约束是在近线性时间内找到的，我不会感到惊讶，因为它们似乎很容易推断出来。
但是请注意，SMT 求解器是在考虑 SAT 的情况下构建的，这是 NP-hard，因此您在 运行 时间上不会有任何次指数理论保证。如果你需要的是实际的 运行 时间才能被接受，实际的 SMT 求解器（具有手工制作的停止条件）将是我最好的猜测，因为它们在实践中非常有效，即使它们在最坏情况下的复杂性是指数级的.如果您还需要对最坏情况 运行 时间的理论保证，我建议您编写自己的类似 SMT 的证明生成器并证明您的模型可以生成的非冗余约束数量的上限，这似乎也可行，但结果可能呈指数增长。
你提到了线性规划，找到一个满足你的约束的实例确实是一个 LP 问题。但是，您在这里对约束的解决方案不感兴趣，而是对实际的最优收紧约束感兴趣。这表明 LP 不是您在这里寻找的东西（或者至少不是原样）。 LP 问题是您提到的形式，但会产生满足给定约束的解决方案，而且如果不详尽列出您不想要的解决方案，似乎很难将其转回约束。另一方面，可满足性试图推断出原始约束隐含的隐藏约束，并希望找到不可满足的东西（在这种情况下它只是 returns UNSAT）。如果你的约束确实是可满足的，那么产生的 "hidden constraints" 将比你原来的约束更严格，你只需要提取其中你感兴趣的子集。
这就是为什么我建议深入研究 SMT 而不是 LP。请注意，这个问题可能比看起来更难，因为似乎可以在其中对 SAT 进行编码，这意味着您必须为最坏的情况支付指数时间，但您也许能够找到在合理的时间内近似解，或者确保平均复杂度仍然可以接受。
给定
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（线性不等式）做了一些假设。很难读出您正在寻找哪种隐含界限（数值与积分），这可能会产生巨大影响。
虽然这看起来像是一个多项式时间问题（如果不做更多研究就很难掌握 cycle/non-convergence 属性；请参阅参考论文；可能与浮点数学限制与区间算术有关），这些方法可能不适用于您的数字。
看看
Belotti, Pietro, et al. "On feasibility based bounds tightening." (2012).
其中给出了一些概述。
你会发现很多关键词导致不同的研究社区（数学优化、约束规划、人工智能），比如：
- 基于可行性的边界收紧
- 边界传播
- bound/range减少
- 域名filtering/reduction.
有一个简单的 2n LP-solving 方法，但考虑到您的数字，这似乎是不够的，无论是使用单纯形法还是内点法。
该论文还介绍了一种单 LP 方法，但它可能无法扩展。
根据这个问题对你有多重要，你想投资多少，如果全局选择不可行（给定一些时间范围），你的确切目标是什么，你可以查看那篇论文，它是参考资料和关键字，并可能检查数学优化求解器中的内容，包括（链接指向这个核心问题）：
和其他人，其中每一个都应该包括 一些 边界收紧方法（对于线性等式）。总的来说，我希望像 Couenne 这样的全球解决者在这一步投入更多时间；因为与 Clp 这样的 LP 求解器相比，剩余的优化通常很容易控制这一点。
我认为你的问题正是在“简单时间网络”上强制执行“部分路径一致性”的问题。
简单时间网络 [1] 是具有决策变量 t_i 的约束网络（它们对应于您的 nodes/labels）和以下形式的约束：L_ij <= t_j-t_i <= U_ij（其中 L_ij 和 U_ij 是某些节点对之间的已知边界，例如在您的示例中：6<=D-C<=+oo ).问题是为每个弧找到与约束兼容的最紧边界（因此对于每个 t_j-t_i）。
这些问题在时间推理和调度中得到了大量研究。
特别是，您的问题是多项式的。一个简单的方法是运行一个Floyd-Warshall算法计算出一条all-pairs最短路径，如[1]所示。但是它会在 O(n^3) 中 运行 这对你来说可能太贵了。还存在更有效的算法，例如 [2] 中提出的算法。
[1]德克特，R.；梅里，我。和 Pearl, J. 1991。时间约束网络。人工智能 49(1–3):61–95.
[2] 普兰肯 L.; de Weerdt M.；和 van der Krogt R. P3C：简单时间问题的新算法。第十八届自动化规划与调度国际会议论文集 (ICAPS 2008)。
当然，如果您只对约束网络的一致性感兴趣，或者对满足约束的节点寻找可行值感兴趣，那么问题就容易多了。如果您只想计算节点的最严格边界（而不是弧线），则同样如此。
好的，我想我已经弄明白了。感谢所有回复的人，它让我进行了一些有用的研究。
我能够利用这样一个事实，即我不是 运行 算法每次都在不同的图表上，而是在不断修改的同一个图表上。我可以保留旧值并每次更新它，包含对本地更改区域的更新。如果新变化不是太剧烈，传播应该不会太远。
该算法相当直观。我在正确的轨道上，但我错过了传播步骤。它是这样的：
看看有问题的图片，把它想象成一个物理系统：有蓝色的板，它们之间有可以收缩和膨胀的条。为了找到最短的特定杆，我尽可能地将所有板一直拉到左边。在杠铃的右板上保持向左的压力，我尽可能地将左板拉向它。该运动将位置变化传播到与其连接的所有条。它可能会将右板向后移动一点，这很好。运动的能量被周围杆的额外松弛所消耗。一旦能量在系统中波动并稳定下来，我就会记录板之间的最终距离。
找到最长的柱子是一样的：我把盘子一直移到左边，然后把右边的盘子尽可能地推离左边。
如果我缓存所有东西向左移动和所有东西向右移动的位置，这些值有助于快速计算结果。我可以在图形更改时以类似的方式更新这些位置，从而使大部分工作保持本地化。
它在技术上不是线性的，但根据我的数据，大部分时间都是线性的。
我有一个系统，我需要计算每个变量的可能值范围（我不需要找到系统的解决方案）。这是示例系统的说明：
每条蓝线是一个节点（由上面的标签命名），灰线是节点之间的边。给定一个初始约束：比如边BC可以是0到1之间的任意实数，边BE可以是任意大于等于9的数，节点不能跨越其他节点。将它们想象成可以伸缩的金属条会很有帮助，从而推动蓝色板。
我的目标是计算每条边的最小和最大长度。起始约束建立了系统，但最终结果可能比它们更受约束。例如，边 DF 的起始 min/max 为 (2,∞)，但您可以看到它实际上不能短于 3，因为收缩它会将 D 拉入 E，将 E 拉向 F，然后将 EF至少有3个。我相信最终的结果是这样的：
需要注意的是，我需要一种可以扩展到数十万个节点的算法，这将比这个例子连接得更密集。它不能在 运行ning 时间内呈指数增长，因为我还必须 运行 这个算法数十万次。
我尝试了一种方法，它给出了一些更受约束的值，但不是最受约束的值。为了可视化该方法，我基本上将所有盘子尽可能地拉到左边，然后记录每个盘子的最大位置。然后我也这样做，把他们拉到右边。然后，对于每条边，我只是找出每个板的值之间的差异。此方法非常有效地找到最大值，但问题是当您遇到此示例中的情况时，其中 CD 是 BC 和 DE 的 "locked" 到 BE。它不能是 6，因为系统只允许它比 9 短 2。我需要一种方法来找到真正的最小值 7。我的方法没有捕获 "locking" 关系：当你拉C一直往左拉，BC是0，D一直往右拉，DE是0，但CD是6的时候不能都为0
在这个例子中，很容易看出 CD 受 BE 约束，但在实践中，系统会比这个例子更密集、更大，找到这种情况似乎并不容易。如果该方法涉及在本地搜索它，我担心它的扩展性会很差，但这可能是唯一的方法。
如果将其建模为线性规划问题（AB + BC = AC，AB>1 等），也许可以利用该系统的某些属性：事实上约束为1，约束中只有加减法。
有人对如何解决这个问题有什么建议吗？或者对我实际希望的 运行 时间复杂度有什么看法？谢谢！
听起来可满足性模理论在这里会有帮助。将您的长度约束作为初始公理（即 0 <= BC <= 1 等），以及一个可以让您添加距离的理论（即 AB + BC = AC 用于所有 A、B、C），并让 SMT 求解器计算它可以从中推断出的约束。如果您正在寻找的 "optimal" 约束是在近线性时间内找到的，我不会感到惊讶，因为它们似乎很容易推断出来。
但是请注意，SMT 求解器是在考虑 SAT 的情况下构建的，这是 NP-hard，因此您在 运行 时间上不会有任何次指数理论保证。如果你需要的是实际的 运行 时间才能被接受，实际的 SMT 求解器（具有手工制作的停止条件）将是我最好的猜测，因为它们在实践中非常有效，即使它们在最坏情况下的复杂性是指数级的.如果您还需要对最坏情况 运行 时间的理论保证，我建议您编写自己的类似 SMT 的证明生成器并证明您的模型可以生成的非冗余约束数量的上限，这似乎也可行，但结果可能呈指数增长。
你提到了线性规划，找到一个满足你的约束的实例确实是一个 LP 问题。但是，您在这里对约束的解决方案不感兴趣，而是对实际的最优收紧约束感兴趣。这表明 LP 不是您在这里寻找的东西（或者至少不是原样）。 LP 问题是您提到的形式，但会产生满足给定约束的解决方案，而且如果不详尽列出您不想要的解决方案，似乎很难将其转回约束。另一方面，可满足性试图推断出原始约束隐含的隐藏约束，并希望找到不可满足的东西（在这种情况下它只是 returns UNSAT）。如果你的约束确实是可满足的，那么产生的 "hidden constraints" 将比你原来的约束更严格，你只需要提取其中你感兴趣的子集。
这就是为什么我建议深入研究 SMT 而不是 LP。请注意，这个问题可能比看起来更难，因为似乎可以在其中对 SAT 进行编码，这意味着您必须为最坏的情况支付指数时间，但您也许能够找到在合理的时间内近似解，或者确保平均复杂度仍然可以接受。
给定
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（线性不等式）做了一些假设。很难读出您正在寻找哪种隐含界限（数值与积分），这可能会产生巨大影响。
虽然这看起来像是一个多项式时间问题（如果不做更多研究就很难掌握 cycle/non-convergence 属性；请参阅参考论文；可能与浮点数学限制与区间算术有关），这些方法可能不适用于您的数字。
看看
Belotti, Pietro, et al. "On feasibility based bounds tightening." (2012).
其中给出了一些概述。
你会发现很多关键词导致不同的研究社区（数学优化、约束规划、人工智能），比如：
- 基于可行性的边界收紧
- 边界传播
- bound/range减少
- 域名filtering/reduction.
有一个简单的 2n LP-solving 方法，但考虑到您的数字，这似乎是不够的，无论是使用单纯形法还是内点法。
该论文还介绍了一种单 LP 方法，但它可能无法扩展。
根据这个问题对你有多重要，你想投资多少，如果全局选择不可行（给定一些时间范围），你的确切目标是什么，你可以查看那篇论文，它是参考资料和关键字，并可能检查数学优化求解器中的内容，包括（链接指向这个核心问题）：
和其他人，其中每一个都应该包括 一些 边界收紧方法（对于线性等式）。总的来说，我希望像 Couenne 这样的全球解决者在这一步投入更多时间；因为与 Clp 这样的 LP 求解器相比，剩余的优化通常很容易控制这一点。
我认为你的问题正是在“简单时间网络”上强制执行“部分路径一致性”的问题。
简单时间网络 [1] 是具有决策变量 t_i 的约束网络（它们对应于您的 nodes/labels）和以下形式的约束：L_ij <= t_j-t_i <= U_ij（其中 L_ij 和 U_ij 是某些节点对之间的已知边界，例如在您的示例中：6<=D-C<=+oo ).问题是为每个弧找到与约束兼容的最紧边界（因此对于每个 t_j-t_i）。
这些问题在时间推理和调度中得到了大量研究。
特别是，您的问题是多项式的。一个简单的方法是运行一个Floyd-Warshall算法计算出一条all-pairs最短路径，如[1]所示。但是它会在 O(n^3) 中 运行 这对你来说可能太贵了。还存在更有效的算法，例如 [2] 中提出的算法。
[1]德克特，R.；梅里，我。和 Pearl, J. 1991。时间约束网络。人工智能 49(1–3):61–95.
[2] 普兰肯 L.; de Weerdt M.；和 van der Krogt R. P3C：简单时间问题的新算法。第十八届自动化规划与调度国际会议论文集 (ICAPS 2008)。
当然，如果您只对约束网络的一致性感兴趣，或者对满足约束的节点寻找可行值感兴趣，那么问题就容易多了。如果您只想计算节点的最严格边界（而不是弧线），则同样如此。
好的，我想我已经弄明白了。感谢所有回复的人，它让我进行了一些有用的研究。
我能够利用这样一个事实，即我不是 运行 算法每次都在不同的图表上，而是在不断修改的同一个图表上。我可以保留旧值并每次更新它，包含对本地更改区域的更新。如果新变化不是太剧烈，传播应该不会太远。
该算法相当直观。我在正确的轨道上，但我错过了传播步骤。它是这样的：
看看有问题的图片，把它想象成一个物理系统：有蓝色的板，它们之间有可以收缩和膨胀的条。为了找到最短的特定杆，我尽可能地将所有板一直拉到左边。在杠铃的右板上保持向左的压力，我尽可能地将左板拉向它。该运动将位置变化传播到与其连接的所有条。它可能会将右板向后移动一点，这很好。运动的能量被周围杆的额外松弛所消耗。一旦能量在系统中波动并稳定下来，我就会记录板之间的最终距离。
找到最长的柱子是一样的：我把盘子一直移到左边，然后把右边的盘子尽可能地推离左边。
如果我缓存所有东西向左移动和所有东西向右移动的位置，这些值有助于快速计算结果。我可以在图形更改时以类似的方式更新这些位置，从而使大部分工作保持本地化。
它在技术上不是线性的，但根据我的数据，大部分时间都是线性的。