mersenneforum.org large equation system over integers
 Register FAQ Search Today's Posts Mark Forums Read

 2011-03-28, 17:46 #1 talork   Mar 2011 2·3 Posts 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!
2011-03-28, 19:03   #2
science_man_88

"Forget I exist"
Jul 2009
Dumbassville

100000110000002 Posts

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

Last fiddled with by science_man_88 on 2011-03-28 at 19:03

 2011-03-28, 19:49 #3 wblipp     "William" May 2003 New Haven 236010 Posts 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.
 2011-03-28, 20:14 #4 talork   Mar 2011 2·3 Posts 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!
2011-03-28, 20:19   #5
science_man_88

"Forget I exist"
Jul 2009
Dumbassville

838410 Posts

Quote:
 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).

2011-03-28, 20:26   #6
science_man_88

"Forget I exist"
Jul 2009
Dumbassville

26·131 Posts

Quote:
 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).

 2011-03-28, 20:29 #7 CRGreathouse     Aug 2006 135118 Posts sm: the OP said nonnegative rather than positive. Nonnegative includes 0.
2011-03-28, 20:33   #8
science_man_88

"Forget I exist"
Jul 2009
Dumbassville

26×131 Posts

Quote:
 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).

2011-03-28, 20:39   #9
science_man_88

"Forget I exist"
Jul 2009
Dumbassville

26×131 Posts

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

 2011-03-28, 20:43 #10 CRGreathouse     Aug 2006 596110 Posts 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
2011-03-28, 21:01   #11
science_man_88

"Forget I exist"
Jul 2009
Dumbassville

203008 Posts

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

 Similar Threads Thread Thread Starter Forum Replies Last Post carpetpool carpetpool 4 2017-02-03 12:48 flouran Math 7 2009-12-12 18:48 Vijay Math 6 2005-04-14 05:19 jasong Math 2 2005-03-11 03:30 Logic Programming 1 2004-09-19 21:26

All times are UTC. The time now is 17:49.

Mon Jan 18 17:49:03 UTC 2021 up 46 days, 14 hrs, 0 users, load averages: 1.19, 1.43, 1.53