我有一个有趣的小问题,我相信可以用优化或约束规划来表述。我有几十个变量,,...以及在它们之间建立关系的一组约束,例如. 其中一些约束被二进制指标变量“打开”:. 我们知道其中一些二进制变量的值,但不是全部。这里的目标是解决系统问题,以便我们可以快速回答有关非二元变量对之间关系的问题(“之间的关系是什么?和?”)。答案可能是:
- 之间的关系和无法根据现有信息确定。
我的第一直觉是将其表述为一个约束满足问题。我将每个非二进制变量的域定义为一组正非零整数,编码条件约束为(如果指标为 0 则始终为真,如果指标为 1,则仅在以下情况下为真),并提供无条件约束 () 原样。然后我会采取一种可行的解决方案,例如:
PROBLEM:
a < b
b < c
a < d
SOLUTION:
a = 0
b = 1
c = 2
d = 1
这对于回答一些问题很有用——例如,如果我们询问之间的关系和,我们可以得出结论和那.
但是如果我们问之间的关系和, 事实上具有误导性,因为以下也是可行的解决方案:
a = 0
b = 1
c = 2
d = 99
其实之间的关系和鉴于现有信息无法确定。我们可以迭代这个 CSP 的所有可行解决方案,并检查它们之间的关系和在每一个中,但这太慢了。我们也可以尝试添加约束并解决可行性,然后对等,但这似乎也很麻烦。
有没有更优雅的方式来表述这个我不知道的问题?任何想法或建议将不胜感激。谢谢!