20110328, 17:46  #1 
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! 
20110328, 19:03  #2  
"Forget I exist"
Jul 2009
Dumbassville
2^{6}×131 Posts 
Quote:
Last fiddled with by science_man_88 on 20110328 at 19:03 

20110328, 19:49  #3 
"William"
May 2003
New Haven
23·103 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 nonnegative?
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. 
20110328, 20:14  #4 
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! 
20110328, 20:19  #5  
"Forget I exist"
Jul 2009
Dumbassville
2^{6}·131 Posts 
Quote:
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). 

20110328, 20:26  #6  
"Forget I exist"
Jul 2009
Dumbassville
10000011000000_{2} Posts 
Quote:


20110328, 20:29  #7 
Aug 2006
3·1,993 Posts 
sm: the OP said nonnegative rather than positive. Nonnegative includes 0.

20110328, 20:33  #8 
"Forget I exist"
Jul 2009
Dumbassville
2^{6}×131 Posts 
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).

20110328, 20:39  #9 
"Forget I exist"
Jul 2009
Dumbassville
10000011000000_{2} Posts 
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.

20110328, 20:43  #10 
Aug 2006
3·1,993 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 01 programming problem first. Last fiddled with by CRGreathouse on 20110328 at 20:48 
20110328, 21:01  #11  
"Forget I exist"
Jul 2009
Dumbassville
20C0_{16} Posts 
Quote:
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 

Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Large Polynomial Equation Problem  carpetpool  carpetpool  4  20170203 12:48 
Diophantine Equation  flouran  Math  7  20091212 18:48 
Possible solutions to an equation:  Vijay  Math  6  20050414 05:19 
Time to prp equation  jasong  Math  2  20050311 03:30 
Request for an equation.  Logic  Programming  1  20040919 21:26 