0

enter image description here

I wanna get all integer solutions in a limited time, is it possible?

2
  • Are the p_i >= 0? Commented Jan 8, 2020 at 13:26
  • yes, p_i>0 Commented Jan 9, 2020 at 1:16

1 Answer 1

2

This is a linear, integer constraint satisfaction problem, which can be solved efficiently by OR Tools' CP-SAT. I've modified their example to solve your problem in 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()
Sign up to request clarification or add additional context in comments.

7 Comments

it works when size of p is small, what if size of p is a bit larger?(>2000) I want to figure out x which always be zero in all solutions
@Jerome That's a whole different question than the one you asked initially. It's pretty easy to see that any x associated with a p > 30 will have to be zero. Other than that I don't think there is an easy way to find out which x will allways be zero. The program runs on my machine with 2000 p values no problem.
PS: Are you sure you want all solutions with that many p values? Are you sure you don't want to solve this as a knapsack problem? In other words, with a certain value for each item and selecting the best solution rather than all solutions?
what is the range of you 2000 p? in my case, all 2000 p<30
Are the p values also integers?
|

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.