Несколько решений MILP в ORTOOLS [python]

Question

Я пытаюсь использовать or-tools в Python для решения линейной программы со смешанными целыми числами, которая имеет несколько оптимальных решений. Однако NextSolution() всегда возвращает False, поэтому я не могу получить более одного решения. Я понимаю, что эта функция работает с использованием решателя ограничений, но я хотел бы использовать решатель MILP.

В соответствующей документации or-tools указано:

По состоянию на 10 февраля 2020 года только 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

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()

Answer 1

Извините за вводящую в заблуждение документацию. В настоящее время только Gurobi поддерживает NextSolution. Я не экспортировал соответствующий код SCIP.

Если ваша проблема требует только логической или целочисленной переменной, вы можете использовать решатель CP-SAT (ortools / sat), который поддерживает перечисление по нескольким решениям.

см. эту документацию .