Average Optimization using GA or intlinprog algorithms

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 respectively. I want to solve the problem for min and max average spike count. What is the algorithm here? Intlingprog does not seem to help, used ga solver but it takes about 5 mins. I want to drop the runtime to 10 secs at worst. Thanks!

[Mehmet]

Let me explain the problem clearly. I asked it as an anology for my real case. If i remember extra constraints that must be met i will edit the code but this is it for now.

a = excel_mat1;    % rocks in diff shapes and materials and contain [0,0] row (size 30x3)
b = excel_mat2;    % rocks in diff shapes and materials and contain [0,0] row (size 30x3)
c = excel_mat3;    % rocks in diff shapes and materials and contain [0,0] row (size 30x3)
d = excel_mat4;    % rocks in diff shapes and materials and contain [0,0] row (size 30x3)
e = excel_mat5;    % rocks in diff shapes and materials and contain [0,0] row (size 30x3)
f = excel_mat6;    % rocks in diff shapes and materials and contain [0,0] row (size 30x3)
g = excel_mat7;    % rocks in diff shapes and materials and contain [0,0] row (size 30x3)
h = excel_mat8;    % rocks in diff shapes and materials and contain [0,0] row (size 30x3)
i = excel_mat9,    % rocks in diff shapes and materials and contain [0,0] row (size 30x3)
j = excel_mat10;   % fluid types  (size 10x3)

%%  [Volume;density;ID] for all

aa = size(a,1);
bb = size(b,1);
cc = size(c,1);
dd = size(d,1);
ee = size(e,1);
ff = size(f,1);
gg = size(g,1);
hh = size(h,1);
ii = size(i,1);

max_bucket_vol = user_defined_value; 

%% this bucket has various things whose values are known inside 
volume_initial = vol1;  %constant volume of materials inside bucket at first
density_initial= den1;  %constant density of materials inside bucket at first

number_of_rocks = size([a;b;c;d;e;f;g;h;i],1);

available_fluids = size(j,1);
max_volume_of_available_fluids = j(:,1);
max_weight_of_available_fluids = j(:,1).*j(:,2); %density in second column

ings = [a;b;c;d;e;f;g;h;i];

volume_vector = ings(:,1);
density_vector= ings(:,2);

optchoice  = optimproblem;
optrocksol = optimvar('optrocksol',number_of_rocks,'Type','integer','LowerBound',0,'UpperBound',1);
optfluidsol= optimvar('optfluidsol',available_fluids,'LowerBound',0,'UpperBound',1);

optchoice.Objective = (sum(optrocksol.*volume_vector.*density_vector)+sum(optfluidsol.*max_weight_of_available_fluids)+vol1*den1)...
/(sum(optrocksol.*volume_vector)+sum(optfluidsol.*j(:,1)+vol1);

optchoice.Constraints.s0 = sum(optrocksol.*volume_vector)+sum(optfluidsol.*j(:,1)+vol1 <= max_bucket_vol;
optchoice.Constraints.s1 = sum(optrocksol(1:aa)) == 1;
optchoice.Constraints.s2 = sum(optrocksol(aa+1:aa+bb)) == 1;
optchoice.Constraints.s3 = sum(optrocksol(aa+bb+1:aa+bb+cc)) == 1;
optchoice.Constraints.s4 = sum(optrocksol(aa+bb+cc+1:aa+bb+cc+dd)) == 1;
optchoice.Constraints.s5 = sum(optrocksol(aa+bb+cc+dd+1:aa+bb+cc+dd+ee)) == 1;
optchoice.Constraints.s6 = sum(optrocksol(aa+bb+cc+dd+ee+1:aa+bb+cc+dd+ee+ff)) == 1;
optchoice.Constraints.s7 = sum(optrocksol(aa+bb+cc+dd+ee+ff+1:aa+bb+cc+dd+ee+ff+gg)) == 1;
optchoice.Constraints.s8 = sum(optrocksol(aa+bb+cc+dd+ee+ff+gg+1:aa+bb+cc+dd+ee+ff+gg+hh)) == 1;
optchoice.Constraints.s9 = sum(optrocksol(aa+bb+cc+dd+ee+ff+gg+hh+1:aa+bb+cc+dd+ee+ff+gg+hh+ii)) == 1;

s = solve(optchoice); % solving for most dense or least dense bucket for defined max volume

Answer 1

[Torsten]

https://uk.mathworks.com/matlabcentral/answers/2063957-optimization-problem-with-array-input?s_tid=srchtitle

[Mehmet]

Yeah, my requirements are kinda changed. I was studying MatLab algorithms lately but could not manage to find and apply any useful method to my problem. Genetic algorithm might be the one.

[Torsten]

Why is the intlinprog code I linked to not applicable ? When reading your question, it seems nothing has changed.

[Mehmet]

It was applicable in that case. But now i need to maximize or minimize average of holes or spikes. So when i set the objective function as sum(selection_array.*ball_number.*spike_on_each_ball)/sum(selection_array.*ball_number), intlinprog runtime becomes insufficient since it does not behave linear anymore.

[Mehmet]

selection_array is binary array here

[Torsten]

Please include the code you used for the other objective.

Note that your problem description from above does not mention any condition on the number of holes. If they don't matter, just take the packages of each color with maximum/minimum number of spikes on the respective balls.

[Mehmet]

Last time my obj function was sum(selection_array.*ball_number.*spike_on_each_ball) hence intlinprog was working admirably. Now it takes ages when the objective func becomes average value of spikes as sum(selection_array.*ball_number.*spike_on_each_ball)/sum(selection_array.*ball_number). Current case is different from the previous one since the objective is maximizing spike count while minimizing the ball number now.

[Torsten]

But I gave you the solution above since you don't mention a condition on the number of holes. So just take the packages of each color with maximum/minimum number of spikes on the respective balls.

If you mean the problem from below, I don't think you can refomulate it as a linear integer problem. So "ga" will be the only way to go.

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_packages = size(a,1);
number_of_black_balls_packages = size(b,1);
total_number_of_balls_packages = number_of_yellow_balls_packages + number_of_black_balls_packages;
ab = [a;b];
balls_vector = ab(:,1);
hole_vector = ab(:,2);
spike_vector = ab(:,3);
ballchoice = optimproblem;
selection_array = optimvar('selection_array',total_number_of_balls_packages,'Type','integer','LowerBound',0,'UpperBound',1);
ballchoice.Objective = sum(selection_array.*balls_vector.*spike_vector)/sum(selection_array.*balls_vector);
ballchoice.Constraints.c0 = sum(selection_array.*balls_vector) == 30;
ballchoice.Constraints.c1 = sum(selection_array.*balls_vector.*hole_vector) == 100;
ballchoice.Constraints.c2 = sum(selection_array(1:number_of_yellow_balls_packages).*balls_vector(1:number_of_yellow_balls_packages)) >= 1;
ballchoice.Constraints.c3 = sum(selection_array(number_of_yellow_balls_packages+1:total_number_of_balls_packages).*balls_vector(number_of_yellow_balls_packages+1:total_number_of_balls_packages)) >= 1;
x = solve(ballchoice);
sum(x.selection_array)
sum(x.selection_array.*balls_vector.*spike_vector)/sum(x.selection_array.*balls_vector)
sum(x.selection_array.*balls_vector.*hole_vector)

Maybe minimizing or maximizing

sum(selection_array.*spike_vector./balls_vector)

could be a compromise. But it's not the same, of course.

Or you try to restart from the solution of the linear integer problem:

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_packages = size(a,1);
number_of_black_balls_packages = size(b,1);
total_number_of_balls_packages = number_of_yellow_balls_packages + number_of_black_balls_packages;
ab = [a;b];
balls_vector = ab(:,1);
hole_vector = ab(:,2);
spike_vector = ab(:,3);
ballchoice = optimproblem;
selection_array = optimvar('selection_array',total_number_of_balls_packages,'Type','integer','LowerBound',0,'UpperBound',1);
ballchoice.Objective = sum(selection_array.*balls_vector.*spike_vector);
ballchoice.Constraints.c0 = sum(selection_array.*balls_vector) == 30;
ballchoice.Constraints.c1 = sum(selection_array.*balls_vector.*hole_vector) == 100;
ballchoice.Constraints.c2 = sum(selection_array(1:number_of_yellow_balls_packages).*balls_vector(1:number_of_yellow_balls_packages)) >= 1;
ballchoice.Constraints.c3 = sum(selection_array(number_of_yellow_balls_packages+1:total_number_of_balls_packages).*balls_vector(number_of_yellow_balls_packages+1:total_number_of_balls_packages)) >= 1;
x = solve(ballchoice);
ballchoice.Objective = sum(selection_array.*balls_vector.*spike_vector)/sum(selection_array.*balls_vector);
x0.selection_array = x.selection_array;
x = solve(ballchoice,x0)
sum(x.selection_array)
sum(x.selection_array.*balls_vector.*spike_vector)/sum(x.selection_array.*balls_vector)
sum(x.selection_array.*balls_vector.*hole_vector)

[Mehmet]

I added the real problem. Yeah that formula was compromising but not sufficient to simulate the case.

[Torsten]

Then you will either use "ga" right from the beginning or start "ga" from a solution obtained by "intlinprog" that will be at least feasible and where the objective is a linear approximation of the nonlinear "average function".

Just out of interest: How large is aa*bb*cc*...*ii ?

Answer 2

[John D'Errico]

This is not an optimization problem. You only look at it in that way. It is purely a problem of a Monte Carlo simulation, to compute the distribution of average spike count. It sounds like you want min and max.

You need to choose 30 balls, from 10 different colors. The only requirement as you state is that you need to choose at least ONE of each color. The solution seems simple. Choose ONE of each color ball FIRST. Remove them from the set of unchosen balls.

Having done that, now you need to choose 20 more balls, but there is no constraint on them. So choose randomly from those that remain.

Now just compute the desired information on that chosen set. Repeat as many times as you wish. The above scheme can be done in a tiny fraction of a second, not minutes, or even seconds.

If this does not solve your problem, then you need to explain what in your question was incomplete.

[Mehmet]

I added the real problem.

[John D'Errico]

Sorry. I cannot/will not chase a moving target, especially one that is highly likely to continue its rapid motion. I've left my answer because it does answer the question you initially posed.