如何在 Python 中使用 Google 的 OR-Tools 获得二元 LP 问题的多个解？

Question

我是整数优化新手。我正在尝试解决以下大型（虽然不是那么大）二元线性优化问题：

max_{x} x_1+x_2+...+x_n

服从：A*x <= b ; x_i is binary for all i=1,...,n

如你所见，

。控制变量是长度为 x 的向量，例如 n=150； x_i 是所有 i=1,...,n

的二进制

。我想最大化 x_i 的总和

。在约束中，A 是一个 nxn 矩阵，b 是一个 nx1 向量。所以我有 n=150 线性不等式约束。

我想获得一定数量的解，NS。比如说，NS=100。（我知道有不止一种解决方案，而且可能有数百万个。）

我正在使用 Google 的 Python OR-Tools。我能够写出问题并获得一种解决方案。之后我尝试了很多不同的方法来获得更多解决方案，但我就是做不到。例如：

1. 我尝试使用 SCIP 求解器，然后我使用最佳目标函数的值，将其称为 V，以在原始值的基础上添加另一个约束，x_1+x_2+...+x_n >= V “Ax<=b," and then used the CP-SAT solver to find NS feasible 向量（我按照本指南中的说明进行操作）。第二步中没有优化，只是寻求可行性。这不起作用：求解器生成了同一向量的 N 个副本。仍然，当询问找到的解决方案数量时，它会误导性地回答solution_printer.solution_count()等于NS。这是我使用的代码片段：

# Define the constraints (A and b are lists)
for j in range(n):
    constraint_expr = [int(A[j][l])*x[l] for l in range(n)]
    model.Add(sum(constraint_expr) <= int(b[j][0]))

V = 112
constraint_obj_val = [-x[l] for l in range(n)]
model.Add(sum(constraint_obj_val) <= -V)


# Call the solver:
solver = cp_model.CpSolver()
solution_printer = VarArraySolutionPrinterWithLimit(x, NS)
solver.parameters.enumerate_all_solutions = True
status = solver.Solve(model, solution_printer)

2. 我尝试使用 SCIP 求解器，然后使用solver.NextSolution()，但每次使用此命令时，该算法都会产生一个每次都越来越不理想的向量：第一个对应的值是，比方说，V=112（最优的！）；第二个向量对应于值 111；第三个，到108；第四至第六，至103；等等

不幸的是，我的问题有点模糊，但问题是：获得多个解决方案来解决我的优化问题的最佳方法是什么？

如果我不够清楚或者您需要更多/其他代码块等，请告诉我。这是我第一次在这里发布问题:)

提前致谢。

Answer 1

你的矩阵 A 是积分吗？如果没有，您就无法使用 scip 和 CP-SAT 解决同样的问题。

此外，为什么要使用scip？您应该使用相同的求解器来求解这两部分。

此外，我相信 scip 中的默认解决方案池实现将以相反的顺序返回找到的所有解决方案，从而按质量顺序递减。

Answer 2

在 Gurobi 中，你可以这样做来获得多个最佳解决方案：

solver->SetSolverSpecificParametersAsString("PoolSearchMode=2"); // or-tools [Gurobi]

来自 Gurobi 参考资料 [第 20.1 节]：

默认情况下，Gurobi MIP 求解器将尝试为您的模型找到一个经过验证的最佳解决方案。

您可以使用 PoolSearchMode 参数来控制用于查找解决方案的方法。 在默认设置 (0) 下，MIP 搜索只是旨在找到一个 最优解。将参数设置为 1 会导致 MIP 搜索 花费额外的努力来寻找更多的解决方案，但在 非系统的方式。你会得到更多的解决方案，但不一定 最佳解决方案。将参数设置为 2 会导致 MIP 执行 系统地搜索n个最佳解决方案。对于非默认 设置中，PoolSolutions 参数设置数字的目标 需要找到的解决方案。

寻找多个最优解的另一种方法是首先将原始问题求解至最优，然后添加目标函数作为约束，下限和上限作为最优目标值。