如何高效地找到此约束系统中变量的最小和最大值？

Question

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

每条蓝线都是一个节点（由上面的标签命名），灰色线是节点之间的边缘。有一个初始约束条件：例如，边缘BC可以是0到1之间的任何实数，边缘BE可以是大于或等于9的任何数字。节点不能穿过其他节点。将它们想象为可以伸展和收缩的金属棒，推动蓝色板子四处移动会很有帮助。

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

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

我尝试了一种方法，给出了一些更受限制的值，但不是最受限制的值。为了可视化该方法，我基本上将所有板子拉到左边尽可能远的位置，然后记录每个板子的最大位置。然后我做了同样的事情，把它们拉到右边。然后，对于每条边，我只需找到每个板子值之间的差异。这种方法非常有效地找到了最大值，但问题在于当您遇到像此示例中那样的情况时，CD被BC和DE所“锁定”。它不能是6，因为系统只允许它比9短2。我需要一种方式来找到真正的最小值7。我的方法没有捕捉到这种“锁定”关系：当您将C全部移到左侧时，BC为0，当您将D全部移到右侧时，DE为0，但如果CD为6，则它们不能都为0。

在这个例子中，很容易看出CD受BE限制，但实际上，系统会比例子更加密集和庞大，找到这样的情况似乎并不容易。如果该方法涉及在局部周围搜索，我担心它的可扩展性会很差，但那可能是唯一的方法。

如果将其建模为线性规划问题（AB + BC = AC，AB > 1等），也许可以利用该系统的某些属性：所有限制的系数都是1，且限制中只有加法和减法。

有人有什么建议来解决这个问题吗？或者对于我应该现实地希望的运行时间复杂度有任何见解吗？谢谢！

- lifeformed

Answer 1

给定：

我需要一个算法，可以扩展到数十万个节点，这些节点比这个示例更密集地连接在一起。它不能呈指数级增长，因为我还必须运行这个算法数十万次。

你似乎有困难。

对我来说，这看起来像以下问题：

ICSP（区间约束满足问题）。“给定一组关于与区间域相关联的变量的方程集E。在不失去E的可能精确解的情况下尽可能细化域，即确定每个变量的最小一致子区间。”

在E上进行了一些假设（线性不等式）。很难读出您正在寻找什么样的隐含界限（数字 vs. 整数），这可能会产生巨大影响。

虽然这看起来像是一个多项式时间问题（难以掌握循环/非收敛属性，而不进行更多研究；请参见引用论文；可能与浮点数学限制与区间算术相关联），但这些方法可能不适用于您的数字。

看一下

Belotti，Pietro等人的“基于可行性的边界收紧”（2012）。

它提供了一些概述。

您将找到许多关键字，引导到不同的研究社区（数学优化，约束编程，人工智能），例如：

可行性为基础的边界收紧

边界传播

边界/范围缩减

域过滤/缩减。

有一个简单的2n LP求解方法，但是鉴于您的数字，似乎这不够用，无论是使用Simplex还是Interior-point方法。

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

根据这个问题对您的重要性，您想要投资多少以及如果全局优化不可行（在某个时间范围内），您的确切目标是什么，您可以查看该论文，其参考文献和关键字，以及可能检查数学优化求解器中的内容（链接指向此核心问题）：

• Couenne（与论文有些关联，但实现的方法可能与论文不同）
• SCIP
  • （需许可证！-> 不适用于商业用途）
• Clp

其他一些求解器也包括了某些界限收紧方法（用于线性等式）。通常，我期望像Couenne这样的全局求解器在这一步骤上投入更多时间；因为与LP求解器（如Clp）相比，剩余优化问题通常很容易支配此步骤。

- sascha

Answer 2

听起来Satisfiability Modulo Theory在这里会有帮助。将您的长度约束作为初始公理（即0 <= BC <= 1等），使用一个允许您添加距离的理论（即AB + BC = AC对于所有A，B，C），并让SMT求解器计算它可以从中推断出的约束条件。我不会感到惊讶，如果您正在寻找的“最优”约束条件在近线性时间内被找到，因为它们似乎很容易推断出。

但请注意，SMT求解器是以SAT为基础构建的，而SAT是NP-hard问题，因此你不能保证运行时间是次指数级别。如果您需要实际可接受的运行时间，则实际SMT求解器（配合手工制定的停止条件）可能是我的最佳猜测，因为它们在实践中非常高效，尽管它们的最坏情况复杂度是指数级别。如果您还需要最坏情况运行时间的理论保证，我建议编写自己的类SMT证明生成器，并证明您的模型可以生成的非冗余约束的上限，这似乎也是可以做到的，但可能会转化为指数级别。

您提到了线性规划，并且找到满足您约束条件的实例确实是一个LP问题。但是，在这里您对约束条件的实际最优化缩紧感兴趣，而不是解决方案。这表明LP并不是您在这里寻找的（或至少不是原样）。LP问题的形式与您提到的相同，但会产生满足给定约束条件的解决方案，似乎很难将其转换回约束条件，而不必枚举解决方案，这并不是您想要的。另一方面，可满足性试图推断出由原始约束条件暗示的隐藏约束条件，并希望找到一些不可满足的东西（在这种情况下，它只返回UNSAT）。如果您的约束确实是可满足的，则生成的“隐藏约束”将比原始约束更紧，您只需要提取您感兴趣的子集即可。

这就是为什么我建议深入研究SMT而不是LP。但请注意，这个问题可能比看起来更难，因为似乎可以在其中编码SAT，这意味着您可能需要为最坏情况付出指数时间，但您也许能够在合理的时间内找到近似解决方案，或者确保平均复杂度仍然可接受。

- Robindar

Answer 3

我认为你的问题正是在“简单时间网络”上实施“部分路径一致性”的问题。

“简单时间网络” [1] 是具有决策变量 t_i（它们对应于您的节点/标签）和约束形式的约束网络：L_ij <= t_j-t_i <= U_ij（其中 L_ij 和 U_ij 是某些节点之间已知的边界，例如在您的例子中：6<=D-C<=+oo）。问题是找到与约束兼容的每个弧（因此对于每个t_j-t_i）的最紧密边界。

这些问题在时间推理和调度方面得到了广泛研究。

特别地，您的问题是多项式的。一种简单的方法是运行 Floyd-Warshall 算法来计算所有对最短路径，如[1]所示。但这将以 O(n^3) 运行，这可能对您来说太昂贵了。还存在更有效的算法，例如[2]中提出的算法。

[1] Dechter, R.; Meiri, I.; and Pearl, J. 1991. Temporal constraint networks. Artificial Intelligence 49(1–3):61–95.

[2] Planken L. ; de Weerdt M.; and van der Krogt R. P3C: A New Algorithm for the Simple Temporal Problem. Proceedings of the Eighteenth International Conference on Automated Planning and Scheduling (ICAPS 2008).

当然，如果您只对约束网络的一致性或查找满足约束的节点的可行值感兴趣，则问题要简单得多。如果您只想计算节点的最紧密可能边界（而不是弧），则情况也是如此。

- Philippe Laborie

Answer 4

好了，我想我已经搞清楚了。感谢所有回应的人，他们让我找到了一些有用的研究资料。

我能够利用这个事实，即我不是每次在不同的图上运行算法，而是在一个不断被修改的相同图上运行算法。我可以保留旧值，并每次更新它，包含对局部改变区域的更新。如果新的更改不太激烈，传播就不会扩散得太远。

该算法相当直观。我走错了路，但我缺少传播步骤。它如下所示：

看一下问题中的图片，并将其想象成一个物理系统：有蓝色的板子和介于它们之间可以收缩和扩展的条形构件。为了找到特定条形构件的最短长度，我要将所有的板子都向左拉，尽可能地靠拢。保持对条形构件右侧板的向左压力，我尽可能地将其左侧板向其拉近。运动将通过与其连接的所有条形构件传播位置的变化。它可能会稍微向后移动右边的板子，但这没关系。运动的能量被周围条形构件的额外松弛消耗。一旦能量在系统中波动并稳定下来，我就记录板之间的最终距离。

找到最长的酒吧也是一样的：我把所有的盘子都移到最左边，然后把右边的盘子尽可能地推开离左边。

如果我缓存从左移动所有东西和从右移动所有东西的位置，这些值有助于快速计算结果。当图形发生变化时，我可以以类似的方式更新这些位置，使大部分工作局部化。

虽然它不是技术上的线性，但对于我的数据来说，它大多数时间都是。

- lifeformed