Optimization problem with array input

Guys i need to figure out the algorithm to model a question. Question is here: I have to pickup 30 balls that are in 10 different colors. Number of the balls are in the first column of the input matrice. Only requirement here is i have to pick at least one for each color.Every balls have different numbers of holes and spike on them. These are column 2 and 3 input. The sum of the holes must be 100. I want to solve for min and max spike conditions. What is the algorithm here? I tried to assign coefficients but that doesn't seem like it works. I could solve with 10 for loops but the sizes of arrays differ from 5 to 150. It takes about 3 days to execute. I kinda search for fmincon for discrete array inputs. Thanks!

[Torsten]

Which column contains the color of the ball ? The first one ? Or do you have more than one input matrix - one for each color ?

[MEHMET SAHIN]

I have 10 separate matrices in .xlsx format for each color.Like c1(5,3) & c2(150,3) & c3(58,3) etc.

[John D'Errico]

You CANNOT use fmincon. fmincon does not apply to discrete problems, Period. You might decide to try GA, but your question is still to vague to understand it. No matter what, this problem is never going to be solvable using brute force loops.

An example matrix with your data in it might help. For example, do all red balls have the same number of holes and spikes?

[MEHMET SAHIN]

% for yellow balls
% Number of balls as package, number of holes on each,number of spikes on
% each

a = [3 5 36;1 5 25;2 8 2;4 7 23;8 22 8;8 2 7;5 12 98;6 15 5];

% for black balls
% Number of balls as package, number of holes on each,number of spikes on
% each
b = [3 3 3;1 6 6;2 8 2;3 5 2;3 11 5;8 5 31;7 6 7;9 3 8;8 4 9;2 20 3;3 4 51];...

%constraints 

for aa=1:height(a)
    for bb=1:height(b)...

        tot_num_balls=a(aa,1)+b(bb+1);... % must be equal to 30
        tot_holes=a(aa,1).*a(aa,2)+b(bb,1).*b(bb,2);... % must be equal to 100
        tot_spikes=a(aa,1).*a(aa,3)+b(bb,1).*b(bb,3);...   % search for min and max values 

    end
end

[MEHMET SAHIN]

i pick balls as packages like trio,duo, single etc. For example, as indicated in the first row of a, I have 3 balls that have 5 holes and 36 spikes on each and i cannot divide them. So i have 2 choices here:

(0) Do not pick -- 0 balls 0 hole 0 spike

(1) Pick -- 3 balls 15 holes 108 spikes

[Torsten]

Try my suggestion below - I guess that for bigger problems, your attempt will lead nowhere.

Answer 1

[Torsten]

You might want to try "intlinprog" with x being a binary vector with x(i) = 1 meaning: ball i is picked and x(i)= 0 meaning: ball i is not picked.

Then set up the problem as

minimize/maximize sum_i x(i)*spike(i)

under the constraints

sum_i x(i)*holes(i) = 100
sum_i x(i) = 30
sum_{i=1}^{i=5} x(i) >= 1
sum_{i=5+1}^{i=5+150} x(i) > = 1
sum_{i=5+150+1}^{i=5+150+58} x(i) >= 1
...

[Torsten]

a = [3 5 36;1 5 25;2 8 2;4 7 23;8 22 8;8 2 7;5 12 98;6 15 5];
b = [3 3 3;1 6 6;2 8 2;3 5 2;3 11 5;8 5 31;7 6 7;9 3 8;8 4 9;2 20 3;3 4 51];
number_of_yellow_balls = sum(a(:,1));
number_of_black_balls = sum(b(:,1));
total_number_of_balls = number_of_yellow_balls + number_of_black_balls;
ab = [a;b];
hole_vector = [];
spike_vector = [];
for i = 1:size(ab,1)
    hole_vector = [hole_vector;ab(i,2)*ones(ab(i,1),1)];
    spike_vector = [spike_vector;ab(i,3)*ones(ab(i,1),1)];
end
ballchoice = optimproblem;
balls = optimvar('balls',total_number_of_balls,'Type','integer','LowerBound',0,'UpperBound',1);
ballchoice.Objective = sum(balls.*spike_vector);
ballchoice.Constraints.c0 = sum(balls) == 30;
ballchoice.Constraints.c1 = sum(balls.*hole_vector) == 100;
ballchoice.Constraints.c2 = sum(balls(1:number_of_yellow_balls)) >= 1;
ballchoice.Constraints.c3 = sum(balls(number_of_yellow_balls+1:total_number_of_balls)) >= 1;
x = solve(ballchoice)

Solving problem using intlinprog.
LP:                Optimal objective value is 197.250000.                                           

Cut Generation:    Applied 2 strong CG cuts.                                                        
                   Lower bound is 200.000000.                                                       
                   Relative gap is 0.00%.                                                          


Optimal solution found.

Intlinprog stopped at the root node because the objective value is within a gap tolerance of the optimal value, options.AbsoluteGapTolerance = 0. The intcon variables are integer within tolerance,
options.IntegerTolerance = 1e-05.

x = struct with fields:
    balls: [86×1 double]

sum(x.balls)

ans = 30

sum(x.balls.*spike_vector)

ans = 200

sum(x.balls.*hole_vector)

ans = 100

[Torsten]

So you only pick full packages ? Then the code from above will become even easier.

[MEHMET SAHIN]

Yes, i understood this logic. This could help. Let me check by myself. Thanks a lot !!

[MEHMET SAHIN]

Thanks!! I tried this way in Excel solver and it tooks 1 day to get the solution. But intlinprog is more powerful and gave me the answer in 3 secs.

[Torsten]

Didn't know that Excel has such a solver. But glad to hear you succeeded in MATLAB.