Generating combinations under certain constraints

I have 5 variables x1,x2,x3,x4 and x5. each is a 4x1 column vector and I want to generate a matrix that holds the different possible combinations of these 5 variables such that the sum of their product(x1'*x1 +x2'*x2+ x3'*x3 +x4'*x4+ x5'*x5) is less than 10. the elements of the 5 variables x are non-negative integers.

[Matt J]

It's impossible as currently stated. The minimum value of the sum is 20, attained when all x1(i)...x5(i)=1.

[Amira Akra]

Why is that? the values can be 0, so if i have one 1 in each variable, I can get a minimum of 4...right?

[Guillaume]

positive normally means greater than zero. non negative would be a more appropriate term if your integers can be 0.

[John D'Errico]

Um, you state in one place that the values can be as small as zero, in another place that they be positive integers. Which is it?

[Amira Akra]

each element is >=0

[John D'Errico]

Matt's question is a valid one though. If x1 is a POSITIVE integer vector of length 4, as is x2, x3, etc., then

x1'*x1 = sum(x1.^2)

has a minimum value of 4.

The sum of 5 such terms has a minimum value of 20.

To quote your own explanation...

"the elements of the 5 variables x are positive integers."

So you need either to explain the problem more clearly, or accept that it cannot be solved as such.

[Amira Akra]

ok. what if x1=[0 1 0 0]', x2=[0 0 0 0]',x3=[0 0 0 0]',x4=[1 0 0 0]' and x5=[0 0 0 0]'? this will give 8..are there any possibilities than these?

[Image Analyst]

OK, so zero is allowed. But for a given set of x, (x1'*x1 +x2'*x2+ x3'*x3 +x4'*x4+ x5'*x5) is a single number. So what do you mean by "combinations" ? Do you mean like x1 might be multiplied by x3 sometimes and x2 other times? Also, what is the use case for this? In other words, why do you need it?

[Amira Akra]

@Image Analyst : I am trying to write an optimization problem with constraints and i need to test all possibilities. one of these constraints is related to my question.

regarding what I mean with combination: x1=[0 1 0 0]', x2=[0 0 0 0]',x3=[0 0 0 0]',x4=[1 0 0 0]' and x5=[0 0 0 0]' is a possible combination between the 5 variables. changinf the values of the variables will provide another combination and so on.... hope this clarifies it??

[John D'Errico]

Not yet. You need to clarify if order matters. Thus, suppose we find a solution

{x1,x2,x3,x4,x5}

then is the set

{x2,x1,x3,x4,x5}

a different solution?

[Amira Akra]

@John D'Errico no, they should remain in the same order

1) x1=[0 1 0 0]', x2=[0 0 0 0]',x3=[0 0 0 0]',x4=[0 0 0 0]' and x5=[0 0 0 0]' since (x1'*x1 +x2'*x2+ x3'*x3 +x4'*x4+ x5'*x5) =1 <10

2) x1=[1 0 0 0]', x2=[1 0 0 0]',x3=[0 0 0 0]',x4=[0 0 0 0]' and x5=[0 0 0 0]' since (x1'*x1 +x2'*x2+ x3'*x3 +x4'*x4+ x5'*x5) =1<10

3) x1=[1 1 1 1]', x2=[1 1 1 1]',x3=[0 0 0 0]',x4=[0 0 0 0]' and x5=[0 0 0 0]' since (x1'*x1 +x2'*x2+ x3'*x3 +x4'*x4+ x5'*x5) =8<10

4)x1=[1 1 1 1]', x2=[1 1 1 1]',x3=[0 1 0 0]',x4=[0 0 0 0]' and x5=[0 0 0 0]' since (x1'*x1 +x2'*x2+ x3'*x3 +x4'*x4+ x5'*x5) =9<10

and so on....I want to generate all the possible values of x1 till x5 that will satisfy this mechanism.

Answer 1

[Matt J]

It might be helpful to recognize that the problem is equivalent simply to selecting a sequence of 20 square integers. Because of your constraints, the set of square integers you can choose from are {0,1,4,9}. There are only about 7 ways the non-zero square integers can be distributed disregarding order,

• 9
• 9 1
• 4 4
• 4 4 1
• 4 4 1 1
• One 4 and up to 6 ones
• Up to 10 ones

It should be a simple matter to use nchoosek() to identify all the possible selections for each case.

[Amira Akra]

why is 2 not included in the set? If i have one of the variables, let us say x1=[1 1 0 0], then x1'*x1 = 2?

[Matt J]

Your constraint is a sum of squares

    sum_k X(k).^2 <=10

where X=[x1;x2;x3;x4;x5] is the vector you get from concatenating all your x_j vectors. We have therefore rewritten the problem in terms of new variables s(k) = X(k).^2, k=1...20. The new variables s(k) can only have values that are squared integers {0,1,4,9}.

Once you have solved in terms of s, you can always convert back to X later.

[Amira Akra]

ok that was very helpful..Thank you! one last question please, if i changed the threshold, i can still follow the same method,right?

Answer 2

[Guillaume]

Here is one way to try the brute force approach:

allx = {x1, x2, x3, x4, x5);
sumprodofset = @(cx) sum(cellfun(@(x) x' * x, cx));
combinations = num2cell(logical(dec2bin(1:2^numel(allx)-1, numel(allx)) - '0'), 2);
combsum = cellfun(@(c) sumprodofset(allx(c)), combinations);
validcombtf = combinations(combsum < 10)

Not sure what you want as an output, maybe this:

validcombx = cellfun(@(v) cell2mat(allx(v)), validcombtf, 'UniformOutput', false)

Or this:

valicombtf = cell2mat(validcombtf);

[Amira Akra]

can you walk me through this please? :S

Answer 3

[John D'Errico]

There are a fair number of possible solutions, depending on the answers to my questions. We can view the solution in a simple way, regardless. Your clarification of my questions will impact the possible set of solutions.

View this problem as the sum of squares of 20 non-negative integers, such that the sum is no greater than 10. There are only a very restricted set of possibilities we can have for that solution. We can worry about how those integers will be distributed among the vectors afterwards.

So essentially, this problem reduces initially to the set of partitions of the integers 0:10, as a sum of the integers {0,1,4,9}. I'll write that sum in terms of the multiplicity of each square in the sum, where the total multiplicity is exactly 20. So we can have many solutions. Here are a few:

20*0, 19*0+1, 18*0+2*1, ... , 18*0+1*1+1*9.

It looks like there are 23 such fundamental ways we can write the integers 0:10 as such a sum of squares of exactly 20 integers.

Now, for each of those 23 fundamental partitions, now you need only see how the non-zero elements can be distributed among the 5 distinct vectors, and you are done.