具有条件约束和一些未知指标变量的约束规划问题

计算科学 优化 约束优化 约束
2021-12-24 02:14:49

我有一个有趣的小问题,我相信可以用优化或约束规划来表述。我有几十个变量a,b,c...以及在它们之间建立关系的一组约束,例如a<b. 其中一些约束被二进制指标变量“打开”:b<c|(indx=True). 我们知道其中一些二进制变量的值,但不是全部。这里的目标是解决系统问题,以便我们可以快速回答有关非二元变量对之间关系的问题(“之间的关系是什么?ac?”)。答案可能是:

  • a<c
  • a=c
  • a>c
  • 之间的关系ac无法根据现有信息确定。

我的第一直觉是将其表述为一个约束满足问题。我将每个非二进制变量的域定义为一组正非零整数,编码条件约束为bindx<c(如果指标为 0 则始终为真,如果指标为 1,则仅在以下情况下为真b<c),并提供无条件约束 (a<b) 原样。然后我会采取一种可行的解决方案,例如:

PROBLEM:
a < b
b < c
a < d

SOLUTION:
a = 0
b = 1 
c = 2
d = 1

这对于回答一些问题很有用——例如,如果我们询问之间的关系ac,我们可以得出结论a=0c=1a<c.

但是如果我们问之间的关系bd, 事实上b=d=1具有误导性,因为以下也是可行的解决方案:

a = 0
b = 1 
c = 2
d = 99

其实之间的关系bd鉴于现有信息无法确定。我们可以迭代这个 CSP 的所有可行解决方案,并检查它们之间的关系bd在每一个中,但这太慢了。我们也可以尝试添加约束b<d并解决可行性,然后对b>d等,但这似乎也很麻烦。

有没有更优雅的方式来表述这个我不知道的问题?任何想法或建议将不胜感激。谢谢!

1个回答

您应该看看Satisfiability Modulo Theories或简称 SMT。可以将大量问题视为特定理论的 SMT 实例。例如,正确设计某些类型的集成电路可以表述为 SMT 问题。您描述的问题符合无量词线性整数算术理论。还有实际算术理论和许多其他理论。正如您所指出的,其中许多问题都有不止一个答案。大多数 SMT 求解器会告诉您(1)公式不可满足或(2)公式可满足并给您一个特定的答案。

如果您正在寻找可以解决 SMT 问题的软件工具,我推荐Z3无论您使用哪种工具,都有一种用于表达 SMT 问题的标准化领域特定语言,称为SMT-LIB如果您想了解 Z3 等工具如何在后台工作,您应该阅读Davis-Putnam-Logeman-Lowell或 DPLL 算法。

关于 SMT 求解器之类的问题可能会在CS stack exchange上得到更多答案,这可能是他们的职责所在。