Or-Tools CP-SAT优化中如何实现直角三角形斜边整数赋值

核心思路 #

由于CP-SAT是整数约束求解器，不支持直接的浮点平方根运算，因此需要将四舍五入的数学定义转换为等价的整数不等式约束：

对于整数变量x、y（直角边）和z（四舍五入后的斜边），四舍五入的定义是：

z - 0.5 ≤ √(x² + y²) < z + 0.5

将不等式两边同时平方（所有项均非负，不等号方向不变），再乘以4消去小数，得到纯整数约束：

1. (2z - 1)² ≤ 4*(x² + y²)
2. 4*(x² + y²) < (2z + 1)²

同时需要处理x和y均为0的特殊情况（此时z必须为0）。

实现步骤与代码示例 #

以下是完整的Python实现代码：

from ortools.sat.python import cp_model

def main():
    # 初始化模型
    model = cp_model.CpModel()
    
    # 定义直角边x、y的取值范围（可根据实际需求调整）
    max_side = 100
    x = model.NewIntVar(0, max_side, 'x')
    y = model.NewIntVar(0, max_side, 'y')
    
    # 定义斜边z的取值范围：最小为0，最大为x+y（三角不等式）
    min_z = 0
    max_z = max_side + max_side
    z = model.NewIntVar(min_z, max_z, 'z')
    
    # 计算x²和y²
    x_sq = model.NewIntVar(0, max_side**2, 'x_sq')
    model.AddMultiplicationEquation(x_sq, x, x)
    y_sq = model.NewIntVar(0, max_side**2, 'y_sq')
    model.AddMultiplicationEquation(y_sq, y, y)
    
    # 计算x² + y²
    sum_sq = model.NewIntVar(0, 2*(max_side**2), 'sum_sq')
    model.Add(sum_sq == x_sq + y_sq)
    
    # 处理x=0且y=0的特殊情况
    model.Add(z == 0).OnlyEnforceIf([x == 0, y == 0])
    
    # 定义布尔变量标记x/y是否非零
    non_zero = model.NewBoolVar('non_zero')
    model.Add(x != 0).Or(y != 0).OnlyEnforceIf(non_zero)
    model.Add(x == 0).And(y == 0).OnlyEnforceIf(non_zero.Not())
    
    # 约束1：(2z - 1)² ≤ 4*sum_sq
    two_z_minus_1 = model.NewIntVar(2*min_z -1, 2*max_z -1, 'two_z_minus_1')
    model.Add(two_z_minus_1 == 2*z - 1)
    left_sq = model.NewIntVar(0, (2*max_z -1)**2, 'left_sq')
    model.AddMultiplicationEquation(left_sq, two_z_minus_1, two_z_minus_1)
    model.Add(left_sq <= 4 * sum_sq).OnlyEnforceIf(non_zero)
    
    # 约束2：4*sum_sq < (2z + 1)²
    two_z_plus_1 = model.NewIntVar(2*min_z +1, 2*max_z +1, 'two_z_plus_1')
    model.Add(two_z_plus_1 == 2*z + 1)
    right_sq = model.NewIntVar(0, (2*max_z +1)**2, 'right_sq')
    model.AddMultiplicationEquation(right_sq, two_z_plus_1, two_z_plus_1)
    model.Add(4 * sum_sq < right_sq).OnlyEnforceIf(non_zero)
    
    # 可根据需求添加目标函数，例如最小化z
    # model.Minimize(z)
    
    # 求解并输出结果
    solver = cp_model.CpSolver()
    status = solver.Solve(model)
    
    if status in [cp_model.OPTIMAL, cp_model.FEASIBLE]:
        print(f"x = {solver.Value(x)}")
        print(f"y = {solver.Value(y)}")
        print(f"四舍五入后的斜边z = {solver.Value(z)}")
        actual_hypotenuse = (solver.Value(x)**2 + solver.Value(y)**2)**0.5
        print(f"实际斜边值: {actual_hypotenuse:.2f}")
    else:
        print("未找到可行解")

if __name__ == '__main__':
    main()

关键细节说明 #

• 整数约束转换：通过将浮点不等式转换为纯整数运算，完全适配CP-SAT的整数求解能力，避免浮点精度问题。
• 变量范围优化：通过三角不等式限定z的最大取值为x+y，缩小求解空间，提升求解效率。
• 特殊情况处理：单独约束x和y均为0时z=0，避免数学上的矛盾（此时(2z-1)²=1 > 0=4*sum_sq）。

内容的提问来源于stack exchange，提问作者Vincente