Solving for a missing column

i have 8 numbers [25451;1901512;265214;356108;707500;24544;462430;24410] each of them could be multiplied by 0.5 or -0.5 or 0. the sum of the multiplications is 720061.5 is it possible to know each number is multiplied by what in order to get 720061.5 ? in other words how to compute the missing column (where each row could be one of the 3 values 0.5,0,or -0.5) that gives me 720061.5? is there any matlab algorthim that could iterate these values till i get the desired sum?

Answer 1

[Guillaume]

With only 8 values and 3 exponents, it's only 3^8 = 6561combinations to try, you could simply brute tests all at once:

a = [25451; 1901512; 265214; 356108; 707500; 24544; 462430; 24410]; 
multipliers = [0.5 0 -0.5];
multcombs = cell(1, numel(a));    %to receive all combinations of multipliers
[multcombs{:}] = ndgrid(multipliers);  %generate all combinations
multcombs = reshape(cat(numel(a) + 1, multcombs{:}), [], numel(a)).';  %reshape along rows of a
sumcombs = sum(a .* multcombs);  %prior to 2016b use: sumcomb = sum(bsxfun(@times, a, multcombs));

sumcombs is the sum of the multiplication for each combination of the multipliers. Now find the closest one to 720061.5

>>[difference, location] = min(abs(sumcombs - 720061.5))
difference = 
    0
 location = 
    6193

which you get with the combination

>>multcombs(:, location)
ans =
        0.5
        0.5
          0
          0
          0
          0
       -0.5
       -0.5

and to get all possible combinations where the sum is exactly 720061.5:

>>multcombs(:, find(sumcombs == 720061.5))  %may return more than one column
ans = 
        0.5
        0.5
          0
          0
          0
          0
       -0.5
       -0.5

There's only one, same as above.

edit: shouldn't have Torsten's a which is missing one value!

Answer 2

[Torsten]

Let a=[25451;1901512;265214;356108;707500;24544;462430;24410].

Then your problem is equivalent to the following formulation which can be solved using "intlinprog":

min: eps
a^t*x-2*720061.5 - eps <= 0
-(a^t*x-2*720061.5) - eps <= 0
-1 <= x <= 1

Unknowns are the vector x (which must be set as integer) and eps (real number, should be 0 for optimum x vector).

Note that the solution to your problem doesn't need to be unique.

Best wishes

Torsten.

[Danielle Leblance]

thanks. before i invest in it. i am unclear about two issues. what is t? and where can i impose -0.5,0.5,and 0 values in x?

[Torsten]

1. ^t means: the transposed vector (in MATLAB: transpose(a)).

2. You don't impose any values in the vector x.

"intlinprog" will determine a vector x=[x1,x2,...,x8] the components of which are all taken from the set {-1,0,1} such that

|25451*x1+1901512*x2+...+24410*x8-2*720061.5|

is minimized (in the best case, the expression is zero) (. stands for absolute value).

Once you have x, the vector y=0.5*x will minimize

|25451*y1+1901512*y2+...+24410*y8-720061.5|

Thus y is the solution to your problem.

Best wishes

Torsten.