Number of combinations less than 100

Question

I have 13 lists belonging to different groups:

• Group A (List 1)

• Group B (List 2), (List 3), (List 4), (List 5), (List 6)

• Group C (List 7), (List 8), (List 9), (List 10), (List 11)

• Group D (List 12), (List 13)

All of the groups together must sum up to 1

• Group A can take values from 0-0.7

• Group B can take values from 0-0.6

• Group C can take values from 0-0.9

• Group D can take values from 0-0.1

I want to find all different combinations that these lists can make without exceeding limits of their group.

For example:

if for one combination List2 element = 0.6, List3, List4, List5 and List6 must be 0

Is there an easy way to do that? (I can use R or Python)

(The lists take values from 0 to their Group's limit with an increment of .1)

# i.e. 
List1=[0.0,0.1,0.2,...,0.7]
List2 = [0.0,0.1,0.2,...,0.6]
# etc.

Answer 1

As suggested in my comment we can use Google OR-Tools which are meant for optimization problems such as this. I will try to break down each step to make it as clear as possible and show how this can extend to fit your needs.

from ortools.sat.python import cp_model
model = cp_model.CpModel()

class Data:
    def __init__(self, name, ub, model):
        self.name = name
        self.ub = ub
        self.model = model

    def make_var(self, repeat):
        vars = [self.model.NewIntVar(0, self.ub, f"{self.name}{i}") for i in range(repeat)]
        return vars

We define a class, Data which will hold information about each of your arrays. It will contain the name, the upper bound, and the reference to the model where this variable will be used on. We also define a function, make_var which will create an integer variable for the model to solve for.

If you think about it from the highest level your model really comes down to the following constraint:

a + b1 + b2 + b3 + b4 + b5 + c1 + c2 + c3 + c4 + c5 + d1 + d2 == 100

Each group of array's has its own condition to fulfill but from the highest level this is what we are trying to solve for. make_var will create each of these variables and attach it to the model. This is shown below.

# Variables
a = Data("a", 70, model)
var_a = a.make_var(1)

b = Data("b", 60, model)
var_b = b.make_var(5)

c = Data("c", 90, model)
var_c = c.make_var(5)

d = Data("d", 10, model)
var_d = d.make_var(2)

Next we will add our constraints which each group of arrays is subject to.

# Constraints
model.Add(sum(var_a) <= 70)
model.Add(sum(var_b) <= 60)
model.Add(sum(var_c) <= 90)
model.Add(sum(var_d) <= 10)
model.Add(sum(var_a) + sum(var_b) + sum(var_c) + sum(var_d) == 100)

After that we will define a class which will print our solutions as well as cap the limit on the number of solutions we want to return. That is configureable and you can change that however it makes sense to you. This class is a modified version of the class which can be found here.

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

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

    def on_solution_callback(self):
        self.__solution_count += 1
        for v in self.__variables:
            for val in v:
                print('%s = %i' % (val, self.Value(val)), end=' ')
        print()
        if self.__solution_count >= self.__solution_limit:
            print('Stop search after %i solutions' % self.__solution_limit)
            self.StopSearch()

    def solution_count(self):
        return self.__solution_count

Lastly we solve for the solutions to your problem.

solver = cp_model.CpSolver()
solution_printer = VarArraySolutionPrinterWithLimit([var_a, var_b, var_c, var_d], 10)
status = solver.SearchForAllSolutions(model, solution_printer)

a0 = 0 b0 = 10 b1 = 0 b2 = 0 b3 = 0 b4 = 0 c0 = 0 c1 = 0 c2 = 90 c3 = 0 c4 = 0 d0 = 0 d1 = 0 
a0 = 0 b0 = 9 b1 = 0 b2 = 0 b3 = 0 b4 = 0 c0 = 0 c1 = 0 c2 = 90 c3 = 0 c4 = 0 d0 = 1 d1 = 0 
a0 = 0 b0 = 60 b1 = 0 b2 = 0 b3 = 0 b4 = 0 c0 = 0 c1 = 0 c2 = 30 c3 = 0 c4 = 0 d0 = 10 d1 = 0 
a0 = 0 b0 = 60 b1 = 0 b2 = 0 b3 = 0 b4 = 0 c0 = 0 c1 = 0 c2 = 30 c3 = 0 c4 = 0 d0 = 9 d1 = 1 
a0 = 0 b0 = 0 b1 = 0 b2 = 0 b3 = 0 b4 = 0 c0 = 0 c1 = 0 c2 = 90 c3 = 0 c4 = 0 d0 = 0 d1 = 10 
a0 = 0 b0 = 0 b1 = 1 b2 = 0 b3 = 0 b4 = 0 c0 = 0 c1 = 0 c2 = 90 c3 = 0 c4 = 0 d0 = 0 d1 = 9 
a0 = 0 b0 = 0 b1 = 0 b2 = 1 b3 = 0 b4 = 0 c0 = 0 c1 = 0 c2 = 90 c3 = 0 c4 = 0 d0 = 0 d1 = 9 
a0 = 0 b0 = 0 b1 = 0 b2 = 0 b3 = 1 b4 = 0 c0 = 0 c1 = 0 c2 = 90 c3 = 0 c4 = 0 d0 = 0 d1 = 9 
a0 = 0 b0 = 0 b1 = 0 b2 = 0 b3 = 0 b4 = 1 c0 = 0 c1 = 0 c2 = 90 c3 = 0 c4 = 0 d0 = 0 d1 = 9 
a0 = 0 b0 = 1 b1 = 0 b2 = 0 b3 = 0 b4 = 0 c0 = 0 c1 = 0 c2 = 90 c3 = 0 c4 = 0 d0 = 0 d1 = 9 
Stop search after 10 solutions

I set the limit to 10 solutions but as mentioned previously you can change this as needed. It took ~9ms to obtain the solutions so this should work efficiently and quickly for your use-case.