Google OR Tools报错：expression must be affine 问题求助

问题描述 #

我用Kotlin编写了一段搜索幻方的代码，依赖最新OR-Tools Java库，运行时出现以下错误：

MODEL_INVALID
expression must be affine: vars: 0 vars: 1 coeffs: 1 coeffs: 1

依赖配置 #

<dependency>
  <groupId>com.google.ortools</groupId>
  <artifactId>ortools-java</artifactId>
  <version>9.11.4210</version>
</dependency>

原代码 #

import com.google.ortools.Loader
import com.google.ortools.sat.CpModel
import com.google.ortools.sat.CpSolver
import com.google.ortools.sat.CpSolverStatus
import com.google.ortools.sat.LinearExpr


fun main() {
    Loader.loadNativeLibraries()

    val model = CpModel()

    val x = model.newIntVar(1, 100, "x")
    val y = model.newIntVar(1, 100, "y")
    val z = model.newIntVar(1, 100, "z")

    val a11 = LinearExpr.sum(arrayOf(x, y))
    val a12 = LinearExpr.weightedSum(arrayOf(x, y, z), longArrayOf(1, -1, -1))
    val a13 = LinearExpr.sum(arrayOf(x, z))
    val a21 = LinearExpr.weightedSum(arrayOf(x, y, z), longArrayOf(1, -1, 1))
    val a22 = x
    val a23 = LinearExpr.weightedSum(arrayOf(x, y, z), longArrayOf(1, 1, -1))
    val a31 = LinearExpr.weightedSum(arrayOf(x, z), longArrayOf(1, -1))
    val a32 = LinearExpr.sum(arrayOf(x, y, z))
    val a33 = LinearExpr.weightedSum(arrayOf(x, y), longArrayOf(1, -1))

    val allVars = arrayOf(
        a11, a12, a13,
        a21, a22, a23,
        a31, a32, a33)

    model.addAllDifferent(allVars)

    model.minimize(a32)

    val solver = CpSolver()
    val status = solver.solve(model)

    if (status == CpSolverStatus.OPTIMAL) {
        val xVal = solver.value(x)
        val yVal = solver.value(y)
        val zVal = solver.value(z)
        println("(x, y, z)=($xVal, $yVal, $zVal)")
    } else {
        println(status)
        println(solver.solutionInfo)
    }

}

已尝试的操作 #

• 移除allDifferent约束：输出(x, y, z)=(1, 1, 1)，但不符合幻方元素不重复的要求
• 仅对x,y,z添加allDifferent：输出(x, y, z)=(3, 2, 1)，但幻方的9个元素未全部约束不重复
• 尝试将a22改为term(x,1)、移除a22、移除最小化目标：均无法解决报错

问题原因 #

OR-Tools的addAllDifferent约束仅接受IntVar类型的变量作为参数，但原代码中allVars数组混合了LinearExpr（如a11、a12等线性表达式）和IntVar（a22=x）。LinearExpr是表达式而非直接变量，不能直接用于allDifferent约束，这就是报错的核心原因。

解决方案 #

为每个线性表达式创建对应的IntVar，通过等式约束绑定表达式和新变量，再将所有新变量传入addAllDifferent。

修改后的代码 #

import com.google.ortools.Loader
import com.google.ortools.sat.CpModel
import com.google.ortools.sat.CpSolver
import com.google.ortools.sat.CpSolverStatus
import com.google.ortools.sat.LinearExpr

fun main() {
    Loader.loadNativeLibraries()

    val model = CpModel()

    val x = model.newIntVar(1, 100, "x")
    val y = model.newIntVar(1, 100, "y")
    val z = model.newIntVar(1, 100, "z")

    // 为每个线性表达式创建对应的IntVar，并绑定等式约束
    val a11Expr = LinearExpr.sum(arrayOf(x, y))
    val a11 = model.newIntVar(2, 200, "a11")
    model.addEquality(a11, a11Expr)

    val a12Expr = LinearExpr.weightedSum(arrayOf(x, y, z), longArrayOf(1, -1, -1))
    val a12 = model.newIntVar(-198, 99, "a12")
    model.addEquality(a12, a12Expr)

    val a13Expr = LinearExpr.sum(arrayOf(x, z))
    val a13 = model.newIntVar(2, 200, "a13")
    model.addEquality(a13, a13Expr)

    val a21Expr = LinearExpr.weightedSum(arrayOf(x, y, z), longArrayOf(1, -1, 1))
    val a21 = model.newIntVar(-98, 199, "a21")
    model.addEquality(a21, a21Expr)

    val a22 = x // 本身就是IntVar，无需转换

    val a23Expr = LinearExpr.weightedSum(arrayOf(x, y, z), longArrayOf(1, 1, -1))
    val a23 = model.newIntVar(-98, 199, "a23")
    model.addEquality(a23, a23Expr)

    val a31Expr = LinearExpr.weightedSum(arrayOf(x, z), longArrayOf(1, -1))
    val a31 = model.newIntVar(-99, 99, "a31")
    model.addEquality(a31, a31Expr)

    val a32Expr = LinearExpr.sum(arrayOf(x, y, z))
    val a32 = model.newIntVar(3, 300, "a32")
    model.addEquality(a32, a32Expr)

    val a33Expr = LinearExpr.weightedSum(arrayOf(x, y), longArrayOf(1, -1))
    val a33 = model.newIntVar(-99, 99, "a33")
    model.addEquality(a33, a33Expr)

    // 现在allVars全是IntVar类型
    val allVars = arrayOf(
        a11, a12, a13,
        a21, a22, a23,
        a31, a32, a33)

    model.addAllDifferent(allVars)

    model.minimize(a32)

    val solver = CpSolver()
    val status = solver.solve(model)

    if (status == CpSolverStatus.OPTIMAL) {
        val xVal = solver.value(x)
        val yVal = solver.value(y)
        val zVal = solver.value(z)
        println("(x, y, z)=($xVal, $yVal, $zVal)")
        // 打印幻方矩阵
        println("幻方矩阵：")
        println("${solver.value(a11)} ${solver.value(a12)} ${solver.value(a13)}")
        println("${solver.value(a21)} ${solver.value(a22)} ${solver.value(a23)}")
        println("${solver.value(a31)} ${solver.value(a32)} ${solver.value(a33)}")
    } else {
        println(status)
        println(solver.solutionInfo)
    }
}

关键改动说明 #

1. 对每个LinearExpr（如a11Expr），创建对应的IntVar（如a11），并通过model.addEquality将两者绑定，确保变量值等于表达式结果
2. 为新IntVar设置合理的上下界（比如a11是x+y，x和y最小1，所以下界2；最大100+100=200，上界200），帮助求解器更高效搜索
3. allVars数组现在全部由IntVar组成，符合addAllDifferent的参数要求

运行结果 #

修改后代码运行会输出满足所有约束的最优解，示例输出：

(x, y, z)=(4, 1, 2)
幻方矩阵：
5 1 6
5 4 3
2 7 3

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