如何在ortools中获取整数规划的所有解？

Question

我正在尝试通过 ortools 获取混合整数程序的所有解决方案。我有两个大小为 4 的列表 x 和 y。我想获得满足 sum(x) = 4 * sum(y) 的所有解决方案。我创建了一个函数，它将过去的解决方案列表作为输入并返回下一个解决方案。尽管有更多解决方案，但我只能得到 2 个解决方案。我在这里做错了什么？

我期待以下解决方案

解决方案1： xs1 = [0,0,0,0], ys1 = [0,0,0,0]

解决方案2： xs2 = [4,0,0,0], ys2 = [1,0,0,0]

解决方案3： xs3 = [0,4,0,0], ys3 = [1,0,0,0]

解决方案4： xs4 = [0,0,4,0], ys4 = [0,0,1,0]

很快

from ortools.linear_solver import pywraplp

def opt(xs, ys):
    solver = pywraplp.Solver.CreateSolver('SCIP')

    infinity = solver.infinity()
    # x and y are integer non-negative variables.

    n = 4
    M = 20

    x = [0]* n
    y = [0]* n

    w = [[0]* n]*len(xs)

    δ = [[0]* n]*len(xs)

    for i in range(0,n):
        x[i] = solver.IntVar(0, 20, 'x'+str(i))
        y[i] = solver.IntVar(0, 20, 'y'+str(i))

        for j in range(len(xs)):
            w[j][i] = solver.IntVar(0, 20, 'zp'+str(j)+ '-' + str(i))
            δ[j][i] = solver.IntVar(0, 1, 'δ'+str(j)+ '-' + str(i))

    for j in (range(len(xs))):
        for i in range(0,n):
            solver.Add((w[j][i] - x[i] + xs[j][i]) >=0) 
            solver.Add((w[j][i] - x[i] + xs[j][i]) <= M*(1-δ[j][i])) 
            
            solver.Add((w[j][i] + x[i] - xs[j][i]) >=0) 
            solver.Add((w[j][i] + x[i] - xs[j][i]) <= M*δ[j][i])

    for j in range(len(xs)):
        solver.Add(solver.Sum([w[j][i] for i in range(0,n)]) >= 1)
        
    solver.Add(solver.Sum([x[i] for i in range(0, n)]) - 4 * solver.Sum([y[i] for i in range(0, n)]) == 0)


    solver.Minimize(solver.Sum([x[i] for i in range(0, n)]))

    status = solver.Solve()

    if status == pywraplp.Solver.OPTIMAL:
        solver_x = [0]*n
        solver_y = [0]*n
        for i in range(0,n):
            solver_x[i] = x[i].solution_value()
            solver_y[i] = y[i].solution_value() 
        return ([solver_x, solver_y, solver.Objective().Value()])
    else:
        print('No Solution')
        return ([[0], [0]], -1) 



psx = [[0,0,0,0], [0,4,0,0]]
psy = [[0,0,0,0], [1,0,0,0]]

ns = opt(psx, psy)
print(ns)

输出：

No Solution
([[0], [0]], -1)

参考：

1. 寻找一般整数线性规划的多重解
2. 如何编写绝对值和的约束

Answer 1

如果您有纯整数规划模型，您可以使用 CP-SAT 求解器，它允许您打印所有解决方案 [参见 this]。