2

下面的不等式系统在整数上求解 x1 和 x2。

x1 + x2 = l

x1 >= y1

x2 >= y2

x1 <= z1

x2 <= z2

l - z1 <= x2

l - z2 <= x1

l,y1,y2,z1,z2 是任意但固定且 >= 0。

使用示例值

l = 8

y1 = 1

y2 = 2

z1 = z2 = 6

求解系统并得到以下方程:

2 <= x1 <= 6

x2 = 8 - x1

当我告诉 WolframAlpha 它应该对整数求解时,它只输出所有可能的值。

我的问题是我是否可以以编程方式为任何给定的 l,y1,y2,z1,z2 推导出 x1 和 x2 的方程/范围。这个问题与约束规划有关,我发现了一篇关于这个问题的旧论文: Harvey 等人的“Compiling Constraint Solveving using Projection”

这种方法是否用于任何现代约束求解库?

我问这个的原因是我需要用不同的参数来解决像上面这样的系统几千次,如果整个系统被一遍又一遍地读取/优化/解决,这需要很长时间。因此,如果我可以编译一次我的参数化系统,然后只使用编译后的版本,我预计会有巨大的速度提升。

4

0 回答 0