Optimization problem with array input

Question

Mehmet 2023-12-25

1
链接

此问题的直接链接

https://ww2.mathworks.cn/matlabcentral/answers/2063957-optimization-problem-with-array-input

编辑： Torsten 2023-12-26

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!

6 个评论
显示 4更早的评论隐藏 4更早的评论

MEHMET SAHIN 2023-12-25

编辑：MEHMET SAHIN 2023-12-25

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 2023-12-25

编辑：Torsten 2023-12-25

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

请先登录，再进行评论。

请先登录，再回答此问题。

Answer 1

Torsten 2023-12-25

1
链接

此回答的直接链接

https://ww2.mathworks.cn/matlabcentral/answers/2063957-optimization-problem-with-array-input#answer_1377332

编辑：Torsten 2023-12-25

在 MATLAB Online 中打开

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
...

5 个评论
显示 3更早的评论隐藏 3更早的评论

Torsten 2023-12-25

编辑：Torsten 2023-12-26

在 MATLAB Online 中打开

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