Title: How to programmatically solve y = (a1 * x1) + (a2 * x2) + .... + (a28 * x28) where y and a1, a2 ....a28 are known?
Tags: algorithm;math
Question: I am trying to solve this equation with 28 variables:

y = (a1 * x1) + (a2 * x2) + .... + (a28 * x28) 

1) y is known, so are a1, a2 all the way through a28. 

2) x1, x2 ..... x28 are unknown variables and they are in the range of [-4, 4] with 0.1 increment. 

Could somebody shed some lights on my baffled brain as to what algorithm would be the most efficient to use here?

Comment: What do you mean by `the range of [-4, 4] with 0.1 increment`?

Comment: Is the discretisation intrinsic to the problem, or just an assumed approach? For the continuous problem, can you not simply allow _any_value of say `x2` through to `x28`, and then solve for `x1` in terms of that?

Comment: I wonder what Wolfram Alpha does with this =p

Comment: Are `a` and `y` reals, rationals or integers?

Comment: unfortunately yes, they are all different values

Comment: @irrelephant Karthik is right, that means it could be one of the 80 numbers from -4.0 to 4.0

Comment: @KarthikT there will most definitely be multiple answers

Comment: @DanielFischer all answers are wanted and preferably within reasonable amount of time

Comment: it's intrinsic, allowing x2 through x28 to deviate from the range would change the problem in question

Comment: @Jason just curious, how will you present the solution?

Comment: in at least one scenario, there will be 439804651110400000000000000  solutions.

Comment: Do you want all answers or would any answer suffice?

Comment: @irrelephant im guessing they are -4 or -3.9 or.... 3.9 or 4

Comment: Wont there be multiple answers?

Comment: Are x1... x28 all different values? Because in that case, there will be a very, very large number of valid solutions, if I'm not mistaken.


Here is another answer: This is equivalent to integer linear programming, though since there is only one equation with 28 simple constraints (the bounds, rather than a system of equations), you might be able to do better. In general this is going to be NP-hard (see https://en.wikipedia.org/wiki/Linear_programming#Integer_unknowns), but there are several implementations you might be able to use (see for example How to choose an integer linear programming solver?)

Comment for this answer: This is not a linear programming problem, it is an equation not a relation or maximization.  The answer must be exactly y.
Comment for this answer: You can think of it as maximizing the right hand side sum, subject to the limitation that the sum must not exceed y. That, combined with multiplying by 10 to get rid of the fractions, may turn it into a problem with existing practical solvers.

Here is another answer: First of all multiply everything by 10 so you can stay in integer math.  Also add sum(40*a_u) to both sides will change the range of x_i to [0,80]

Secondly there may be an exponential number of answers so your algorithm must take exponential time.

Given that there are 80^28 (approximately 2^177) possible answers - this is not possible in general.

Now if the range of x_i were [0,1] (and not [0,80]) and we add an extra term that is equal to y (and change y to 0), than the problem becomes find a subset of a set of integers that add up to zero.  This is a well known NP complete problem, and it seems even easier than yours (although I don't have a clear reduction).

There may be a dynamic programming solution, but it may be too slow:

```set<float&gt; X;

X.insert(0)

for i = 1 to 28
    for f = -4.0 to 4.0 step 0.1
        for x in X
            X.insert(x + a_i * f)

for x in X
    if (x == y)
        return true;

return false;
```

You can do better than this by passing back the feasible range (of [y + a_i*(-4.0), y + a_i*4.0]) and prune infeasible partial solutions outside those bounds.

Comment for this answer: You can't really knapsack a problem like this.  What you're doing above is adding -4.0*x1,-3.9*x1 etc which violates the constraints (not to mention you'll run out of memory :))
Comment for this answer: @dfb: I agree depending on the a_i it is exponential in space, but how does it violate the constraints?

Here is another answer: You can program it in prolog (SICStus prolog engine and for example SPIDER IDE on Eclipse). This problem is state space searching problem. And use clpfd library (Constraint Logic Programming over Finite Domains). Then you just do one constraint, X1 to X28 will be domain variable and given constraint y #= a1*X1 + ... + a28*X28. There is also few ways to optimalize searching of state space.

/edit:
Or you can try do it in any imperative language. Also use some heuristics - for example, choose some points of execution, where you can check current result (for example, you have some tmp. sum and you had already count with 15 from 28 values. If y minus temp sum is lesser than MIN_VARIABLE_VALUE * i, where i is index and x_i belongs to remaining variables, you can safely decide, that you won´t continue, bcs. you can´t get equality). This heuristic get on my mind first. Use can also use some substitution in this. But there should be done "research" on some test data how much efficient it is.


{'source': 'StackExchangeDataset', 'subset': 'stackoverflow.com', 'metadata': {'AnswerCount': 3, 'CommentCount': 15, 'ContentLicense': 'CC BY-SA 3.0', 'CreationDate': '2012:00:12/14/12', 'FavoriteCount': 1.0, 'PostTypeId': 1, 'Tags': '<algorithm><math>', 'Title': 'How to programmatically solve y = (a1 * x1) + (a2 * x2) + .... + (a28 * x28) where y and a1, a2 ....a28 are known?', 'ViewCount': 457, 'id': 13872264, 'user_AboutMe': None, 'user_AccountId': 1247519.0, 'user_DisplayName': 'Jason Ye', 'user_Reputation': 79.0, 'user_Views': 18.0, 'user_id': 1208663.0}}