help with an optimization problem

I am new in optimization and will appriciate if someone can assist in writing a code for this specific problem:

There are 20 vectors at length of 4

for example a=[2 6 3 7] ; b=[4 6 1 5] ; c=[3 5 7 6] etc...

I need to find a combination of minimun number of vectors that summing them will result in a vector that each number in it will be larger than 60.

For example. sum=a+c+d+e+f+g+r+z

sum(1)>60 , sum(2)>60 , sum(3)>60 and sum(4)>60

what if I need only 3 numbers (out of the 4) in the resulted vector to be lerger than 60?

Thanks

Answer 1

[Walter Roberson]

Put all your vectors together, each as a column, but multiply by -1.

A = -1[a(:), b(:), c(:), ...];

and a goal vector the same length and negative

b = -60 * ones(length(a),1);

Now use a binary optimizer on 20 variables, in which the objective function is the sum of the decision variables (which gets you the smallest number of items selected), and using A and b as the linear inequality constraints, which are constraints of the form A*x <= b

With only 20 variables you can evaluate

X = (dec2bin(0:2^20-1, 20) - '0').';

min_test = A*X <= b;
meets_min = all(min_test, 1);
candidates = X(:,meets_min);
numvecs_for_candidates = sum(candidates,1);
best_candidates_idx = find(numvecs_for_candidates == min(numvecs_for_candidates));
best_candidates = candidates(:,best_candidates_idx);

best_candidates will then be an array that includes all of the cases where, with the minimum number of vectors, the sums were all at least 60.

To modify this so that only 3 sums need to be above 60,

meets_min = sum(min_test, 1) >= 3;

And no optimization routine needs to be run, every combination is tested.

This should be pretty feasible for 20 variables. Probably it would be feasible for 24 as well. By 30 or so you would be pushing things and might run out of memory.

I constructed this particular way with the negatives because this A and b matrix constructed are exactly what you would need to pass as A and b matrices to the various minimizers such as fmincon() or ga() or one of the integer programming routines. (You would not actually use fmincon() for this because fmincon() is not suitable for binary decision variables.)

[Oren Levy]

Thanks so much