Можно ли найти все целочисленные решения? - PullRequest
Новая
       10

Можно ли найти все целочисленные решения?

0 голосов
/ 08 января 2020

enter image description here

Я хочу получить все целочисленные решения за ограниченное время, возможно ли это?

1 Ответ

2 голосов
/ 08 января 2020

Это линейная целочисленная удовлетворение ограничения задача, которая может быть эффективно решена с помощью ИЛИ Tools 'CP-SAT. Я изменил их пример , чтобы решить вашу проблему в Python: 

from ortools.sat.python import cp_model

class VarArraySolutionPrinter(cp_model.CpSolverSolutionCallback):
    """Print intermediate solutions."""

    def __init__(self, variables):
        cp_model.CpSolverSolutionCallback.__init__(self)
        self.__variables = variables
        self.__solution_count = 0

    def on_solution_callback(self):
        self.__solution_count += 1
        for v in self.__variables:
            print('%s=%i' % (v, self.Value(v)), end=' ')
        print()

    def solution_count(self):
        return self.__solution_count

def SearchForAllSolutionsSampleSat():
    """Showcases calling the solver to search for all solutions."""
    # Creates the model.
    model = cp_model.CpModel()

    p = [1, 2, 3, 4]
    ceq = 30
    cgeq = 2

    N = len(p)

    # Creates the variables
    x = [model.NewIntVar(0, 100, f'x{i}') for i in range(N)]

    # Create the constraints.
    model.Add(sum([xi*pi for xi, pi in zip(x, p)]) == ceq)
    model.Add(sum(x) >= cgeq)

    # Create a solver and solve.
    solver = cp_model.CpSolver()
    solution_printer = VarArraySolutionPrinter(x)
    status = solver.SearchForAllSolutions(model, solution_printer)

    print('Status = %s' % solver.StatusName(status))
    print('Number of solutions found: %i' % solution_printer.solution_count())


SearchForAllSolutionsSampleSat()
...