large equation system over integers

[talork]

Hi all,

I have a huge set of linear equations I have to solve.
There are 651 equations, 1395 variables, and all the equations are of this form:
x_i1 + ... + x_i15 = 4
While x_i is a natural number (not negative and not fractional).

Does anyone know an efficient way to solve this?
Also, if Matlab offers a way to solve this (which I couldn't find) that would also help a lot.

Thanks in advance!

[science_man_88]

Originally Posted by talork

Hi all,

I have a huge set of linear equations I have to solve.
There are 651 equations, 1395 variables, and all the equations are of this form:
x_i1 + ... + x_i15 = 4
While x_i is a natural number (not negative and not fractional).

Does anyone know an efficient way to solve this?
Also, if Matlab offers a way to solve this (which I couldn't find) that would also help a lot.

Thanks in advance!

I've read some of the links in http://www.mersenneforum.org/showthread.php?t=14309 it might help depending on the equations. and what you want to know.

[wblipp]

With the number of variables being so much larger than the number of equations, we expect there to be a very large number of solutions (although it is possible that there are none). Do you want ANY solution? A particular solution that is better than all the others by some comparison method? A characterization of ALL of the solutions? Are there other constraints you haven't yet mentioned, such as the variables are all non-negative?

Is the right side always "4", or is that is example intended to mean it is a constant, but different equations have different constants?

The big picture is that your matrix has a null space, and from any particular solution, you can generate other solutions by adding any member of the null space. One possible approach is to use linear algebra methods to find the solutions in real numbers, and then find the ones that are all integers. Another possible approach is to guess there are solutions with all of the variables in a small set (perhaps 0 and 1, or perhaps -2 to +2), and treat the solution as a combinatorial optimization problem, perhaps using simulated annealing to find a "best fit," and hoping that best fit is actually a solution. There is a whole field known as "integer programming" which is devoted to this kind of problem and has tools that might be effective for this particular problem. I'm sure there are dozens of other approaches - knowing more about the problem details and origins might suggest particularly effective methods for your specific problem.

[talork]

Thanks a lot for your answers.
wblipp, any solution would do (or the knowledge that there isn't any), the variables should all be non negative and the right side of the equation is always 4.
here are a few equations for example:
x1+x2+x3+x4+x5+x6+x7+x8+x9+x10+x11+x12+x13+x14+x15=4
x12+x166+x180+x192+x204+x216+x228+x232+x241+x250+x259+x268+x277+x286+x295=4
x85+x225+x352+x479+x579+x679+x779+x1335+x1343+x1351+x1359+x1367+x1375+x1383+x1391=4

Since I'm not familiar with this field at all, could you maybe recommend some specific methods I can read about?
Thanks!

[science_man_88]

Originally Posted by wblipp

With the number of variables being so much larger than the number of equations, we expect there to be a very large number of solutions (although it is possible that there are none). Do you want ANY solution? A particular solution that is better than all the others by some comparison method? A characterization of ALL of the solutions? Are there other constraints you haven't yet mentioned, such as the variables are all non-negative?

Is the right side always "4", or is that is example intended to mean it is a constant, but different equations have different constants?

The big picture is that your matrix has a null space, and from any particular solution, you can generate other solutions by adding any member of the null space. One possible approach is to use linear algebra methods to find the solutions in real numbers, and then find the ones that are all integers. Another possible approach is to guess there are solutions with all of the variables in a small set (perhaps 0 and 1, or perhaps -2 to +2), and treat the solution as a combinatorial optimization problem, perhaps using simulated annealing to find a "best fit," and hoping that best fit is actually a solution. There is a whole field known as "integer programming" which is devoted to this kind of problem and has tools that might be effective for this particular problem. I'm sure there are dozens of other approaches - knowing more about the problem details and origins might suggest particularly effective methods for your specific problem.

He mentions in post 1 that they are all positive( non-negative) integers.

lets say 4 is the answer if the i15 means 15 variables there are a number of possibilities:

using notation I saw on : http://www.math.rutgers.edu/~erowlan...rithmetic.html

we can see that:
1+1=0
0+0=0
0+1=1

using this we can say with any equation( with a even right side) the amount of odd numbers has to be even (including the possibility 0 odds). calculating from this we can create a scenarios list (in particular I'll say 15 variables):

14 odds,1 even
12 odds,3 evens
10 odds,5 evens
8 odds, 7 evens
6 odds, 9 evens
4 odds, 11 evens
2 odds, 13 evens
0 odds,15 evens

for the odd right side ones reverse the name ( ie. switch odds for even,and vice versa).

[science_man_88]

Originally Posted by science_man_88

He mentions in post 1 that they are all positive( non-negative) integers.

lets say 4 is the answer if the i15 means 15 variables there are a number of possibilities:

using notation I saw on : http://www.math.rutgers.edu/~erowlan...rithmetic.html

we can see that:
1+1=0
0+0=0
0+1=1

using this we can say with any equation( with a even right side) the amount of odd numbers has to be even (including the possibility 0 odds). calculating from this we can create a scenarios list (in particular I'll say 15 variables):

14 odds,1 even
12 odds,3 evens
10 odds,5 evens
8 odds, 7 evens
6 odds, 9 evens
4 odds, 11 evens
2 odds, 13 evens
0 odds,15 evens

for the odd right side ones reverse the name ( ie. switch odds for even,and vice versa).

the problem with my explanation is I talk of many possibilities of the 15 variables (there are none fitting the positive integers unless you include 0 as positive, based on the fact 4<15 so 15*1>4 which means with 15 there's no solution that doesn't involve 0 with those parameters).

[CRGreathouse]

sm: the OP said nonnegative rather than positive. Nonnegative includes 0.

[science_man_88]

Originally Posted by CRGreathouse

sm: the OP said nonnegative rather than positive. Nonnegative includes 0.

okay then the solutions that can happen are the ones that only use 4 values of 1 and the rest 0 then the problem becomes how many are there (which is just asking how many ways can they be arranged, as the order can show which variable).

[science_man_88]

Originally Posted by science_man_88

okay then the solutions that can happen are the ones that only use 4 values of 1 and the rest 0 then the problem becomes how many are there (which is just asking how many ways can they be arranged, as the order can show which variable).

as there are only 4 ones possible the situation is not as simple as 2 ( being even or odd) values for each, which would give the large 2^15. There is still a possibility of more though.

[CRGreathouse]

Heuristic pruning could probably be used very effectively on this problem.

First find all variables that are used only once and remove them, changing their equations from ... + x = 4 to ... <= 4. If any variables are alone on one side of an equation, remove them from the problem substituting their value. If any equation has a 0 on the right, choose one of the variables and remove it from all equations with the appropriate substitution. Remove any equations/inequalities that are already satisfied. Then find the variable that is used most often and guess that it's 0. Start the process over; if anything becomes unsatisfiable, increase the value of the number you're attempting. Once you get to an appropriate depth, solve the matrix and plug in values until they cause something to violate the constraints.

Even better, every so often look to see if two equations are similar to each other and subtract them. The utility of this technique will depend on the amount of overlap, of course.


Of course many software packages for integer programming exist. You might even try solving it as a 0-1 programming problem first.

[science_man_88]

Originally Posted by CRGreathouse

Heuristic pruning could probably be used very effectively on this problem.

First find all variables that are used only once and remove them, changing their equations from ... + x = 4 to ... <= 4. If any variables are alone on one side of an equation, remove them from the problem substituting their value. If any equation has a 0 on the right, choose one of the variables and remove it from all equations with the appropriate substitution. Remove any equations/inequalities that are already satisfied. Then find the variable that is used most often and guess that it's 0. Start the process over; if anything becomes unsatisfiable, increase the value of the number you're attempting. Once you get to an appropriate depth, solve the matrix and plug in values until they cause something to violate the constraints.

Even better, every so often look to see if two equations are similar to each other and subtract them. The utility of this technique will depend on the amount of overlap, of course.


Of course many software packages for integer programming exist. You might even try solving it as a 0-1 programming problem first.

couldn't it also be reduce to actually using

(17:57)>3+1
%67 = 4
(17:57)>2+1+1
%68 = 4
(17:57)>1+1+1+1
%69 = 4
(17:57)>2+2
%70 = 4
(17:57)>4+0
%71 = 4

for the pure 4 one there are 15 possible combo's I see with 15 variables. the second has around 15*14 I believe. and yes I know I used the same logic ( or no logic, depends who reads it) in the chess positions thread.