mersenneforum.org  

Go Back   mersenneforum.org > Math Stuff > Other Mathematical Topics

Reply
 
Thread Tools
Old 2011-03-28, 17:46   #1
talork
 
Mar 2011

616 Posts
Default large equation system over integers

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!
talork is offline   Reply With Quote
Old 2011-03-28, 19:03   #2
science_man_88
 
science_man_88's Avatar
 
"Forget I exist"
Jul 2009
Dumbassville

836910 Posts
Default

Quote:
Originally Posted by talork View Post
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.

Last fiddled with by science_man_88 on 2011-03-28 at 19:03
science_man_88 is offline   Reply With Quote
Old 2011-03-28, 19:49   #3
wblipp
 
wblipp's Avatar
 
"William"
May 2003
New Haven

22·32·5·13 Posts
Default

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.
wblipp is offline   Reply With Quote
Old 2011-03-28, 20:14   #4
talork
 
Mar 2011

1102 Posts
Default

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!
talork is offline   Reply With Quote
Old 2011-03-28, 20:19   #5
science_man_88
 
science_man_88's Avatar
 
"Forget I exist"
Jul 2009
Dumbassville

8,369 Posts
Default

Quote:
Originally Posted by wblipp View Post
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 is offline   Reply With Quote
Old 2011-03-28, 20:26   #6
science_man_88
 
science_man_88's Avatar
 
"Forget I exist"
Jul 2009
Dumbassville

8,369 Posts
Default

Quote:
Originally Posted by science_man_88 View Post
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).
science_man_88 is offline   Reply With Quote
Old 2011-03-28, 20:29   #7
CRGreathouse
 
CRGreathouse's Avatar
 
Aug 2006

2·2,963 Posts
Default

sm: the OP said nonnegative rather than positive. Nonnegative includes 0.
CRGreathouse is offline   Reply With Quote
Old 2011-03-28, 20:33   #8
science_man_88
 
science_man_88's Avatar
 
"Forget I exist"
Jul 2009
Dumbassville

8,369 Posts
Default

Quote:
Originally Posted by CRGreathouse View Post
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 is offline   Reply With Quote
Old 2011-03-28, 20:39   #9
science_man_88
 
science_man_88's Avatar
 
"Forget I exist"
Jul 2009
Dumbassville

8,369 Posts
Default

Quote:
Originally Posted by science_man_88 View Post
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.
science_man_88 is offline   Reply With Quote
Old 2011-03-28, 20:43   #10
CRGreathouse
 
CRGreathouse's Avatar
 
Aug 2006

172616 Posts
Default

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.

Last fiddled with by CRGreathouse on 2011-03-28 at 20:48
CRGreathouse is offline   Reply With Quote
Old 2011-03-28, 21:01   #11
science_man_88
 
science_man_88's Avatar
 
"Forget I exist"
Jul 2009
Dumbassville

8,369 Posts
Default

Quote:
Originally Posted by CRGreathouse View Post
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
Code:
(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.
science_man_88 is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Large Polynomial Equation Problem carpetpool carpetpool 4 2017-02-03 12:48
Diophantine Equation flouran Math 7 2009-12-12 18:48
Possible solutions to an equation: Vijay Math 6 2005-04-14 05:19
Time to prp equation jasong Math 2 2005-03-11 03:30
Request for an equation. Logic Programming 1 2004-09-19 21:26

All times are UTC. The time now is 01:44.

Wed Oct 21 01:44:10 UTC 2020 up 40 days, 22:55, 0 users, load averages: 1.80, 1.62, 1.63

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2020, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.