Sum minimum n matrix elements > certain value

Hello,

My problem is about matrices, for example a 20x20 size.

I would like to know how to: - determine which combinations of values are > than a given sum.

Some constrains must be taken in consideration:

- from each column only 1 value can be used

- a combination (sum) of values should have at least 3 values

Example of 6x6

4 5 7 3 8 4

1 8 4 2 1 3

9 1 8 3 5 7

5 5 7 3 3 4

1 8 4 2 1 3

8 1 6 3 0 15

Question: How to find all unique combinations of values that are > 15.

If the matrix is 20x20 brute force is not really an option. There are simple to many combinations.

Thank you very much for your help.

[José-Luis]

What have you tried so far?

[Paul Reinders]

I'm not a mathematician and I don't have matlab experience. I searched the internet for a similar case, try to find an algorithm but could not find anything helpful.

Until now I have tried to find all the possible unique descending combinations with a least 3 elements and the sum > than the given value.

Answer 1

[John D'Errico]

Not all problems have a simple solution. In fact, it is trivial to pose simple looking problems that have such a huge search space that either you will never stop looking for a solution, or you will generate so many possible solutions that you will run out of memory to store them all.

Sadly, this problem is a case where both of those issues are involved. The search space is huge, and there will probably be so many solutions that you will run out of memory to hold them all.

Often the correct solution is to ask yourself if you REALLY DO need all such solutions. Or if you really need to solve this problem at all.

Note that you CAN view this problem as one where you take each column, and put a tick mark on a corresponding axis of your search space. Add a tick for 0 on each axis too. So with 20 columns, you have 20 dimensions. For the 6x6 case you show...

4 5 7 3 8 4
1 8 4 2 1 3
9 1 8 3 5 7
5 5 7 3 3 4
1 8 4 2 1 3
8 1 6 3 0 15

The first axis will have ticks at [0 1 4 5 8 9], the second axis at [0 1 5 8], the third axis has ticks at [0 4 6 7 8], etc.

Now, visualize a lattice in all 6 (oe 20) dimensions, passing through all combinations of those ticks, thus something that ndgrid would generate.

So something like this:

[X1,X2,X3,X4,X5,X6] = ndgrid([0 1 4 5 8 9],[0 1 5 8],[0 4 6 7 8],[0 2 3],[0 1 3 5 8],[0 3 4 7 15]);

Finally, visualize a plane that lives in that space, defined by the condition

x1 + x2 + x3 + x4 + x5 + x6 >= 15

Any vertices of the lattice that live on the correct side of your plane correspond to solutions. A solution with zero in it does not use the corresponding column. If you add in the final constraint that there must be at least three columns selected, this just means you will only accept solutions with at least 3 non-zeros in it.

Finally, you would need to deal with the case where as is here, the 5th column actually has a zero in it.

Again though, in 20 dimensions, no matter how you phrase it, the search space is simply too huge in 20 dimensions.

[X1,X2,X3,X4,X5,X6] = ndgrid([0 1 4 5 8 9],[0 1 5 8],[0 4 6 7 8],[0 2 3],[0 1 3 5 8],[0 3 4 7 15]);
X = [X1(:),X2(:),X3(:),X4(:),X5(:),X6(:)];
size(X)
ans =
        9000           6

So there are 9000 nodes in the 6 dimensional lattice.

ind = find((sum(X,2) >= 15) & ((sum(X > 0,2) >= 3) | ((sum(X > 0,2) == 2) & (X(:,5) == 0))));
ans =
        7907

And there are 7907 solutions, just for the 6 column case.

[Paul Reinders]

Thank you very much for your suggestions/help.