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

Hello!

This will be a 2 part question.

1. 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).
2. 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.

Answer 1

[Bruno Luong]

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.

[Bruno Luong]

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]

This is almost exactly what I need! I suppose I could put it in a while loop where the values in the maxnrep array are reduced for each iteration?

[Bruno Luong]

My code only give the best one.

I don't know what mean "reduce values of maxnrep" since there are n-values, the next best solution might have at least one that is reduced but might be other values increases.

The best w is [5, 1, 10]

If you want to loop, I guess you need to reduce only one element at the time for the next iteration, try to find smallest x for three maxnrep:

maxnrep = [4,64,32] 
maxnrep = [128,0,32] 
maxnrep = [128,64,9] 

Pick the best x of these three and the corresponding w; then iterate again until you reach

maxnrep = [0,0,0] 

It must converge in at most 128+64+32 iterations as sum(maxnrep) is strictly reduced from iteration too iteration.

[Vladislavs Grigorjevs]

Yeah I get that, but what I mean is for example:

We take the answer that your code returns, which is

31.415927 = 5*2.000000 + 1*3.500000 + 10*1.790000 + 0.015927

So in this case, A(1) is used 5 times, A(2) is used once and A(3) is used 10 times. These numbers should now be subtracted from the available number of coins for each value, as in 128-5=123, 64-1=63 and 32-10=22. So, for the next iteration of the loop maxnrep would look like this:

maxnrep=[123 63 22]

And I would like this loop to run until all of these are equal to 0, finding the optimal solution each time. Can this be done?

[Bruno Luong]

If that is the goal you want to achieve, then do it. I'm not quite sure if I fully understand your description. I only give you a tool.

[Torsten]

But what if another solution exists and gives the same minimal x value ?

Maybe you could get better results in the following steps of your process if you had chosen this solution (that you don't know of).

Maybe you should not optimize each individual step, but the complete process.

[Vladislavs Grigorjevs]

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]

options = optimoptions(@intlinprog,'Display','off');

[Bruno Luong]

Exactly as Torsen's suggestion call intlinprog with the option to switch off the verbose

options = optimoptions(@intlinprog,'Display','off');
wx = intlinprog(f, intcon, [], [], Aeq, beq, lb, hb, [], options);

[Vladislavs Grigorjevs]

That doesn't seem to work

[Torsten]

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

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

[Bruno Luong]

"That doesn't seem to work"

Check what to do by reading

doc Intlinprog 

Answer 2

[Davide Masiello]

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.

[Vladislavs Grigorjevs]

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]

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.