How to programmatically solve y = (a1 * x1) + (a2 * x2) + .... + (a28 * x28) where y and a1, a2 ....a28 are known?

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?

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. — username tbd, Dec 14 '12 at 03:35
What do you mean by `the range of [-4, 4] with 0.1 increment`? — irrelephant, Dec 14 '12 at 03:36
@irrelephant im guessing they are -4 or -3.9 or.... 3.9 or 4 — Karthik T, Dec 14 '12 at 03:37
@irrelephant Karthik is right, that means it could be one of the 80 numbers from -4.0 to 4.0 — Jason Ye, Dec 14 '12 at 03:39
@DanielFischer all answers are wanted and preferably within reasonable amount of time — Jason Ye, Dec 14 '12 at 03:43
in at least one scenario, there will be 439804651110400000000000000 solutions. — Keith Nicholas, Dec 14 '12 at 03:48
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? — Keith, Dec 14 '12 at 04:34
it's intrinsic, allowing x2 through x28 to deviate from the range would change the problem in question — Jason Ye, Dec 14 '12 at 06:06

score 2 · Answer 1 · edited May 23 '17 at 12:12

2

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?)

edited May 23 '17 at 12:12

Community

1
1

answered Dec 14 '12 at 03:44

dfb

13,133
2
31
52

This is not a linear programming problem, it is an equation not a relation or maximization. The answer must be exactly y. – Andrew Tomazos Dec 14 '12 at 05:31
1

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. – Patricia Shanahan Dec 14 '12 at 09:10

Andrew Tomazos · Answer 2 · 2012-12-14T05:29:34.523

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

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 :)) — dfb, Dec 14 '12 at 04:13
@dfb: I agree depending on the a_i it is exponential in space, but how does it violate the constraints? — Andrew Tomazos, Dec 14 '12 at 05:23

Equo · Answer 3 · 2012-12-14T09:45:11.973

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.

How to programmatically solve y = (a1 * x1) + (a2 * x2) + .... + (a28 * x28) where y and a1, a2 ....a28 are known?

3 Answers3