Find minimal possible term x by trying out various combinations of other terms for a known sum

Question

Vladislavs Grigorjevs 2022-4-4

0
链接

此问题的直接链接

https://ww2.mathworks.cn/matlabcentral/answers/1688034-find-minimal-possible-term-x-by-trying-out-various-combinations-of-other-terms-for-a-known-sum

评论： Bruno Luong 2022-4-4

采纳的回答： Bruno Luong

Hello!

This will be a 2 part question.

So let's say I have a known sum, s=12 for example. I also have a number of terms that can all be part of this sum - a, b, c, d and so on, each of them having a constant numeric value assigned to them (for example, a=2; b=3.5; c=1.79 etc.). There is a term x that is a part of this sum as well, but it is unknown and I need it to be as low as possible. So, essentially, I need a code that would try out different combinations of a, b, c etc. in order to find one where x would be the smallest possible value, assuming that the sum stays constant. It should be noted that a single term should also be able to be used multiple times in the sum if it makes sense to do so (for example s = a + a + a + ... + x).
Now, each term will have a defined quantity of times it can be used (for example a can be used 128 times, b can be used 64 times and so on). When the most optimal combination has been used the maximum amount of times for one of the terms, the second most optimal combination of the terms needs to be found, with the term that has run out bypassed. I need this to be repeated until all of the terms have run out. Also, if a situation arises where the most optimal combination is s = a + a + a + ... + x, but a only has 2 times left to be used, then the combination must be adapted so that there aren't any leftovers (as in each term should always be used all of the available amount of times).

I need each combination and the amount of times it is used displayed to me in chronological order as a return. How would I go about making a script like this? I am not familiar with coding that well and it is a bit hard for me to wrap my head around it, so any help would be greatly appreciated.

0 个评论
显示 -2更早的评论隐藏 -2更早的评论

请先登录，再进行评论。

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

Answer 1

Bruno Luong 2022-4-4

0
链接

此回答的直接链接

https://ww2.mathworks.cn/matlabcentral/answers/1688034-find-minimal-possible-term-x-by-trying-out-various-combinations-of-other-terms-for-a-known-sum#answer_934009

You need first to formulate your problem in consist unambiguous math problem.

So I unstand you have an array

A with n-numbers (in your case = [a, a, ..., a, b, b...] with a repeated 128 times, b 64 times).

What you want is to find a subset S of A and x such that

sum(S) + x = s, and you want x (>=0?) is as small as possible.

This problem can be formulated as interger linear programming. Find

array w of same size as A, w having elements of value 0 or 1, such that

x(w) := abs(s - w.*A) is smallest as possible.

You can use intlinprog to solve it if you have optimization tollbox.

12 个评论
显示 10更早的评论隐藏 10更早的评论

Bruno Luong 2022-4-4

在 MATLAB Online 中打开

An example of using intlinprog

A=[2 3.5 1.79]; % coin values
s = 10*pi; % target sum
maxnrep = [128 64 32]; % nb of coins available for each type
n = length(A);
f = [zeros(1,n) 1];
intcon = 1:n;
% A*w + x == s
Aeq = [A 1];
beq = s;
lb = [zeros(1,n) 0];
hb = [maxnrep, Inf];
wx = intlinprog(f, intcon, [], [], Aeq, beq, lb, hb);
LP:                Optimal objective value is 0.000000.                                             

Heuristics:        Found 1 solution using ZI round.                                                 
                   Upper bound is 1.415927.                                                         
                   Relative gap is 58.61%.                                                         

Cut Generation:    Applied 2 mir cuts.                                                              
                   Lower bound is 0.000000.                                                         
                   Relative gap is 58.61%.                                                         

Heuristics:        Found 2 solutions using diving.                                                  
                   Upper bound is 0.125927.                                                         
                   Relative gap is 11.18%.                                                         

Cut Generation:    Applied 1 Gomory cut.                                                            
                   Lower bound is 0.000000.                                                         
                   Relative gap is 11.18%.                                                         

Branch and Bound:

   nodes     total   num int        integer       relative                                          
explored  time (s)  solution           fval        gap (%)                                         
       3      0.07         4   4.592654e-02   4.390991e+00                                          
       5      0.07         5   4.592654e-02   4.390991e+00                                          
      19      0.07         6   1.592654e-02   1.567686e+00                                          
      23      0.07         6   1.592654e-02   0.000000e+00                                          

Optimal solution found.

Intlinprog stopped because the objective value is within a gap tolerance of the optimal value, options.AbsoluteGapTolerance = 0 (the default value). The intcon variables are integer within tolerance,
options.IntegerTolerance = 1e-05 (the default value).
% number of coins to approximate s
w=round(wx(1:n))';
% the residual x
x = s - sum(w.*A); % == wx(n+1)
fprintf(['%f = ' repmat('%d*%f + ', 1, n) '%f\n'], s, [w; A], x)
31.415927 = 5*2.000000 + 1*3.500000 + 10*1.790000 + 0.015927

Vladislavs Grigorjevs 2022-4-4

在 MATLAB Online 中打开

Bruno, thank you for your help once again, I am really close to getting this code to work the way I need it to and I couldn't have done it without you. One last question before I leave you alone, can this output be suppressed somehow?

LP:                Optimal objective value is 0.000000.                                             
Heuristics:        Found 1 solution using ZI round.                                                 
                   Upper bound is 1.415927.                                                         
                   Relative gap is 58.61%.                                                         
Cut Generation:    Applied 2 mir cuts.                                                              
                   Lower bound is 0.000000.                                                         
                   Relative gap is 58.61%.                                                         
Heuristics:        Found 2 solutions using diving.                                                  
                   Upper bound is 0.125927.                                                         
                   Relative gap is 11.18%.                                                         
Cut Generation:    Applied 1 Gomory cut.                                                            
                   Lower bound is 0.000000.                                                         
                   Relative gap is 11.18%.                                                         
Branch and Bound:
   nodes     total   num int        integer       relative                                          
explored  time (s)  solution           fval        gap (%)                                         
       3      0.07         4   4.592654e-02   4.390991e+00                                          
       5      0.07         5   4.592654e-02   4.390991e+00                                          
      19      0.07         6   1.592654e-02   1.567686e+00                                          
      23      0.07         6   1.592654e-02   0.000000e+00                                          
Optimal solution found.
Intlinprog stopped because the objective value is within a gap tolerance of the optimal value, options.AbsoluteGapTolerance = 0 (the default value). The intcon variables are integer within tolerance,
options.IntegerTolerance = 1e-05 (the default value).

Thank you in advance.

Torsten 2022-4-4

编辑：Torsten 2022-4-4

在 MATLAB Online 中打开

Maybe you have an older MATLAB version that works with optimset ?

options = optimset('Display','off')

Bruno Luong 2022-4-4

在 MATLAB Online 中打开

"That doesn't seem to work"

Check what to do by reading

doc Intlinprog

请先登录，再进行评论。

Answer 2

Davide Masiello 2022-4-4

0
链接

此回答的直接链接

https://ww2.mathworks.cn/matlabcentral/answers/1688034-find-minimal-possible-term-x-by-trying-out-various-combinations-of-other-terms-for-a-known-sum#answer_934034

编辑：Davide Masiello 2022-4-4

在 MATLAB Online 中打开

This may be an approach

a = 2;                                      % Can be repeated 128 times max 
b = 3.5;                                    % Can be repeated 64 times max
c = 1.79;                                   % Can be repeated 32 times max
S = 50;                                     % The sum
A = combntns(1:128,3);                      % All possible combintations of 3 numbers between 1 and 128
Warning: The COMBNTNS function will be removed in a future release.
A(A(:,2)>64 & A(:,3)>32,:) = [];            % Rules out if # of repetitions of b and c is over max number allowed
x = S-A*[a;b;c];                            % Finds x
x(x<0) = +inf;                              % Rules out all x<0
[xmin,idx] = min(x);                           % Finds the samllest x
fprintf('The best combination is %i x a + %i x b + %i x c. The value of x if %f.\n',[A(idx,:),xmin])
The best combination is 2 x a + 7 x b + 12 x c. The value of x if 0.020000.

2 个评论
显示无隐藏无

Vladislavs Grigorjevs 2022-4-4

在 MATLAB Online 中打开

I see, this seems plausible, however, there a couple things I'm not really sure about in this case.

So if instead of 3 numbers I have 7, the number of repetitions for which varies from 33 to 1829, how would I change the code then? More specifically, this line exactly

A = combntns(1:128,3);                      % All possible combintations of 3 numbers between 1 and 128

I've changed the 3 to 7 and 128 to 1829, but I'm now getting an error saying "Requested array exceeds the maximum possible variable size." Am I misunderstanding this line or?

Now the second thing that doesn't really work here as far as I can tell is that the code cannot bypass numbers if needed. I would need it to be able to ignore b or c if that would lead to a smaller x value or if the sum of all 3 is bigger than the defined sum value, however, from playing around with it a little bit, I think it just fails to execute properly if that happens.

Davide Masiello 2022-4-4

Yes, in such a large case my example wouldn't be suitable because the matrix of all possible combinations becomes too large and matlab runs out of memory.

In this case I would rather opt for the suggestions given by @Bruno Luong in his answer, which has a more rigorous mathematical approach.

请先登录，再进行评论。

Find minimal possible term x by trying out various combinations of other terms for a known sum

0 个评论
显示 -2更早的评论隐藏 -2更早的评论

采纳的回答

12 个评论
显示 10更早的评论隐藏 10更早的评论

更多回答（1 个）

2 个评论
显示无隐藏无

另请参阅

类别

标签

产品

版本

Community Treasure Hunt

Find minimal possible term x by trying out various combinations of other terms for a known sum

0 个评论 显示 -2更早的评论隐藏 -2更早的评论

采纳的回答

12 个评论 显示 10更早的评论隐藏 10更早的评论

更多回答（1 个）

2 个评论 显示 无隐藏 无

另请参阅

类别

标签

产品

版本

Community Treasure Hunt

0 个评论
显示 -2更早的评论隐藏 -2更早的评论

12 个评论
显示 10更早的评论隐藏 10更早的评论

2 个评论
显示无隐藏无