ORTOOLS [python] 中的多个 MILP 解决方案 [英] Multiple MILP solutions in ORTOOLS [python]

问题描述

我正在尝试使用 Python 中的 or-tools 来解决具有多个最优解的混合整数线性程序.但是，NextSolution() 总是返回 False，所以我不能检索多个解决方案.我知道此函数使用约束求解器工作，但我想使用 MILP 求解器.

相关的or-tools 文档指出:/p><块引用>

截至 2020 年 2 月 10 日，只有 Gurobi 和 SCIP 支持 NextSolution()，有关如何为多个解决方案配置这些求解器的示例，请参见 linear_solver_interfaces_test.其他求解器无条件返回 false.

但是，我在源代码库、文档或通过网络搜索找不到任何此类 linear_solver_interfaces_test.我使用的是 ortools 版本 7.8.7959 和包含的 SCIP 7.0.1 和 Python 3.6.9.

下面是我的示例代码，它说明了我想要解决的类型的一个简单示例.它应该产生三个唯一的解决方案，但目前产生零个解决方案.

from ortools.linear_solver import pywraplp定义主():求解器 = pywraplp.Solver(multiple_solution_test"，pywraplp.Solver.SCIP_MIXED_INTEGER_PROGRAMMING)x = solver.IntVar(0, 2, x")y = solver.IntVar(0, 2, y")z = solver.IntVar(0, 2, z")solver.Add(x + y <= 2)solver.Maximize(x + y + z) # 应该是4，可以通过(2,0,2), (1,1,2), or (0,2,2)得到求解器.Solve()打印解决方案(求解器，x，y，z)def print_solutions(solver, x, y, z):计数 = 0while solver.NextSolution(): # <-- NextSolution() 总是返回 False！计数 += 1打印(x ="，x.solution_value()，y ="，y.solution_value()，z ="，z.solution_value())打印(\n找到的解决方案数:"，计数)如果 __name__ == __main__":主要的()

解决方案

对于误导性的文档，我们深表歉意.目前，只有 Gurobi 支持 NextSolution.我没有导出 SCIP 相关代码.

如果您的问题只需要布尔或整数变量，您可以使用支持枚举多个解决方案的 CP-SAT (ortools/sat) 求解器.

请参阅此文档.

I am trying to use or-tools in Python to solve a mixed-integer linear program that has multiple optimal solutions. However, NextSolution() always returns False, so I cannot retrieve more than one solution. I understand that this function works using a constraint solver, but I would like to use the MILP solver.

The related or-tools documentation states:

As of 2020-02-10, only Gurobi and SCIP support NextSolution(), see linear_solver_interfaces_test for an example of how to configure these solvers for multiple solutions. Other solvers return false unconditionally.

However, I cannot find any such linear_solver_interfaces_test in the source repo, documentation, or via a web search. I am using ortools version 7.8.7959 and the included SCIP 7.0.1 with Python 3.6.9.

Below is my example code which illustrates a simple example of the type I would like to solve. It should produce three unique solutions, but currently produces zero solutions.

from ortools.linear_solver import pywraplp

def main():
    solver = pywraplp.Solver("multiple_solution_test", pywraplp.Solver.SCIP_MIXED_INTEGER_PROGRAMMING)
    x = solver.IntVar(0, 2, "x")
    y = solver.IntVar(0, 2, "y")
    z = solver.IntVar(0, 2, "z")
    solver.Add(x + y <= 2)
    solver.Maximize(x + y + z)  # should be 4, which can be obtained by (2,0,2), (1,1,2), or (0,2,2)
    solver.Solve()
    print_solutions(solver, x, y, z)


def print_solutions(solver, x, y, z):
    count = 0
    
    while solver.NextSolution():  # <-- NextSolution() always returns False!
        count += 1
        print("x =", x.solution_value(), "y =", y.solution_value(), "z =", z.solution_value())
    print("\nNumber of solutions found:", count)
    
    
if __name__ == "__main__":
    main()

解决方案

Sorry for the misleading documentation. Currently, only Gurobi supports NextSolution. I have not exported the SCIP relevant code.

If your problem only needs Boolean or integer variable, you can use the CP-SAT (ortools/sat) solver that supports enumerating over multiple solutions.

see this documentation.

这篇关于ORTOOLS [python] 中的多个 MILP 解决方案的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！