时间戳

首页 > 解决方案 > 使用 google or-tools SAT 求解器舍入 Non-LinearExpr

optimization - 使用 google or-tools SAT 求解器舍入 Non-LinearExpr

问题描述

使用谷歌或工具的 CP-SAT我正在尝试编写此约束：

q >= (50x + 100y + 150z + 200k + 250p + 300v) / (x + y + z + k + p + v)

哪里q是一个简单的整数。

问题是我需要对等式的右侧进行四舍五入（我们称之为expression），如下所示：

if(expression < 75) {
    expression = 50;
} else if(expression < 125) {
    expression = 100;
} else if(expression < 175) {
    expression = 150;
} else if(expression < 225) {
    expression = 200;
} else if(expression < 275) {
    expression = 250;
} else {
    expression = 300;
}

所以我需要对表达式进行四舍五入

(50x + 100y + 150z + 200k + 250p + 300v) / (x + y + z + k + p + v)

使其获得以下值之一：

{50, 100, 150, 200, 250, 300}

让我们回顾2个案例：

情况1

q = 180和expression = 176。

虽然条件180 >= 176是true，但是在四舍五入到 176 到 200 之后，测试的条件应该是180 >= 200which is false。

所以 forq = 180和expression = 176我想返回的条件false。

案例2

q = 210和expression = 218。

虽然条件210 >= 218是false，但在将 218 向下舍入到 200 后，测试的条件应该210 >= 200是true。

所以 forq = 210和expression = 218我想返回的条件true。

我在这里得到了一个很好的答案，可以通过线性表达式解决这个挑战，但现在我需要为非线性表达式解决它。

有什么建议么？

标签： optimizationnonlinear-optimizationor-toolssat

解决方案

让我们改写

你有一个整数变量e，其值在 0 到 300 之间。你想将它四舍五入到最接近的 50 倍数

如果你这样做：

(e div 50) * 50

您将获得小于或等于 50 的最大倍数e

(70 / 50) * 50 -> 50
(99 / 50) * 50 -> 50
(102 / 50) * 50 -> 100

要获得最近的一轮，您需要e在除法之前添加 25

((e + 25) div 50) * 50

哪个会做正确的舍入

((70 + 25) / 50) * 50 -> 50
((99 + 25) / 50) * 50 -> 100
((102 + 25) / 50) * 50 -> 100

使用正确的 or-tools CP-SAT python 代码：

numerator = model.NewIntVar(...)
model.Add(numerator == 50x + 100y + 150z + 200k + 250p + 300v)
denom = model.NewIntVar(...)
model.Add(denom == 50x + 100y + 150z + 200k + 250p + 300v)
e = model.NewIntVar(0, 300, 'e')
model.AddDivisionEquality(e, numerator, denom)

shifted_e = model.NewIntVar(25, 325, 'shifted_e')
model.Add(shifted_e == e + 25)
multiple_of_fifty = model.NewIntVar(0, 6, 'multiple_of_fifty')
model.AddDivisionEquality(multiple_of_fifty, shifted_e, 50)
result = model.NewIntVar(0, 300, 'result')
model.Add(result = multiple_of_fifty * 50)

推荐阅读