如何通过OR-Tools调用SCIP获取MIP问题的Top N最优解？

希望通过SCIP获取MIP问题的前N个最优解——SAT求解器在解数量过多时耗时太长，已知OR-Tools仅支持Gurobi或SCIP实现多解获取，于是用OR-Tools的MIP示例测试，代码如下：

from ortools.linear_solver import pywraplp

solver = pywraplp.Solver.CreateSolver("SCIP")

infinity = solver.infinity()
x = solver.IntVar(0.0, infinity, "x")
y = solver.IntVar(0.0, infinity, "y")

solver.Add(x + 7 * y <= 17.5)
solver.Add(x <= 3.5)

solver.Maximize(x + 10 * y)

print(f"Solving with {solver.SolverVersion()}")
status = solver.Solve()

if status == pywraplp.Solver.OPTIMAL:

    for _ in range(5):

        print(f"Objective value = {solver.Objective().Value():0.3f}")
        print("x =", x.solution_value())
        print("y =", y.solution_value())

        if solver.NextSolution():
            print(f"There is another solution: ")
        else:
            print("No more solutions")
            break

else:
    print("The problem does not have an optimal solution.")

执行后仅得到两个解，第二个为非最优的0值解，不符合需求：

Solving with SCIP 9.0.0 [LP solver: Glop 9.10]
Objective value = 23.000
x = 3.0
y = 2.0
There is another solution:
Objective value = 0.000
x = 0.0
y = 0.0
No more solutions

尝试配置SCIP参数但无效果：

solver = pywraplp.Solver.CreateSolver("SCIP")

solver.SetSolverSpecificParametersAsString("limits/solutions=-1")
solver.SetSolverSpecificParametersAsString("limits/bestsol=-1")
solver.SetSolverSpecificParametersAsString("constraints/countsols/sollimit=-1")
solver.SetSolverSpecificParametersAsString("constraints/countsols/collect=TRUE")
solver.SetSolverSpecificParametersAsString("constraints/countsols/discardsols=FALSE")
...

请问操作是否有误？获取前N个最优解的需求是否可实现？

你的需求完全可实现，操作上存在两个核心问题：

1. 参数设置方式错误 #

SetSolverSpecificParametersAsString每次调用会覆盖之前的参数，无法累加。必须将所有参数合并为一个字符串一次性设置：

solver.SetSolverSpecificParametersAsString("""
limits/solutions=-1
limits/bestsol=-1
constraints/countsols/sollimit=-1
constraints/countsols/collect=TRUE
constraints/countsols/discardsols=FALSE
""")

2. 缺少最优解枚举的关键配置 #

默认情况下NextSolution()会返回任意可行解，而非仅最优解。要获取前N个最优解，需添加以下SCIP参数：

• focus/bestsol=TRUE：让SCIP优先搜索最优解
• limits/bestsol=N：限制仅收集N个最优解（替换N为目标数量）
• constraints/countsols/onlybest=TRUE：仅收集最优解，过滤非最优可行解

修改后的完整参数示例：

solver = pywraplp.Solver.CreateSolver("SCIP")
# 配置收集前3个最优解
solver.SetSolverSpecificParametersAsString("""
focus/bestsol=TRUE
limits/bestsol=3
constraints/countsols/collect=TRUE
constraints/countsols/discardsols=FALSE
constraints/countsols/onlybest=TRUE
""")

3. 测试问题的最优解数量验证 #

你的测试问题本身只有1个整数最优解：x=3、y=2，目标值23。其他可行解（如x=0、y=0）均为非最优解，这也是你只能获取一个最优解的原因。

若要测试多最优解场景，可调整问题为：

# 将x改为连续变量，扩大上限
x = solver.NumVar(0.0, 10.0, "x")
y = solver.IntVar(0.0, infinity, "y")
solver.Add(x + 7 * y <= 17.5)
solver.Maximize(x + 10 * y)

此时y=2时，x可取0到3.5之间的任意值，均为最优解（目标值20+x），能验证多最优解的收集逻辑。

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