Message Boards Message Boards

0
|
8497 Views
|
13 Replies
|
0 Total Likes
View groups...
Share
Share this post:

Solve a large system of equations with 19 variables?

Posted 5 years ago

I need a little help in formulating the correct logic for a set of equations. There are 19 variables with relationships as follows. {p1, p2, ....p19} where {p1, {p2, p4, p5}}. In relation to this the logic is as follows:- p1 has 3 dependents and p1 can be any integer from 1 to 4, the 3 dependents have to take values from 1 to p1-1, any unset variables can be any integer from 1 to 7. . p2 has 4 dependents and as such p2 can be any value from 1 to 5 and it's 4 dependent variables have to include the integers 1 to p2-1 and any unset variable can be any value from 1 to 7. and finally p5 has 6 dependent variables so p5 can be any value from 1 to 7 and it's 6 dependents must contain values from 1 to p5-1 and any unset variable can be any value from 1 to 7. there is a total sum of all 19 variables.

I am not sure if my logic is correct, here is a small part of my system of equations the full set is many lines long.

Solve[{p1 >= p2 || p1 >= p4 || p1 >= p5, 
  p2 >= p3 || p2 >= p1 || p2 >= p5 || p2 >= p6, 
  p3 >= p2 || p3 >= p6 || p3 >= p7,....p1 > 0, p2 > 0, p3 > 0,.....p1 + p2 + p3 + p4 + p5 +....==58,p1 <= 4, p3 <= 4,....,p10 <= 7, p11 <= 7},{p1, p2, p3, p4, p5, p6,...},Integers]

UPDATE:

Solve[{p1 >= p2, p1 >= p4, p1 >= p5, p2 >= p3, p2 >= p1, p2 >= p5, 
  p2 >= p6, p3 >= p2, p3 >= p6, p3 >= p7, p4 >= p5, p4 >= p1, 
  p4 >= p8, p4 >= p9, p5 >= p6, p5 >= p4, p5 >= p1, p5 >= p2, 
  p5 >= p9, p5 >= p10, p6 >= p7, p6 >= p5, p6 >= p2, p6 >= p3, 
  p6 >= p10, p6 >= p11, p7 >= p6, p7 >= p3, p7 >= p11, p7 >= p12, 
  p8 >= p9, p8 >= p4, p8 >= p13, p9 >= p10, p9 >= p8, p9 >= p5, 
  p9 >= p4, p9 >= p14, p9 >= p13, p10 >= p11, p10 >= p9, p10 >= p6, 
  p10 >= p5, p10 >= p15, p10 >= p14, p11 >= p12, p11 >= p10, 
  p11 >= p7, p11 >= p6, p11 >= p16, p11 >= p15, p12 >= p11, 
  p12 >= p7, p12 >= p16, p13 >= p14, p13 >= p8, p13 >= p9, 
  p13 >= p17, p14 >= p15, p14 >= p13, p14 >= p9, p14 >= p10, 
  p14 >= p18, p14 >= p17, p15 >= p16, p15 >= p14, p15 >= p10, 
  p15 >= p11, p15 >= p19, p15 >= p18, p16 >= p15, p16 >= p11, 
  p16 >= p12, p16 >= p19, p17 >= p18, p17 >= p13, p17 >= p14, 
  p18 >= p19, p18 >= p17, p18 >= p14, p18 >= p15, p19 >= p18, 
  p19 >= p15, p19 >= p16, p1 > 0, p2 > 0, p3 > 0, p4 > 0, p5 > 0, 
  p6 > 0, p7 > 0, p8 > 0, p9 > 0, p10 > 0, p11 > 0, p12 > 0, p13 > 0, 
  p14 > 0, p15 > 0, p16 > 0, p17 > 0, p18 > 0, p19 > 0, 
  p1 + p2 + p3 + p4 + p5 + p6 + p7 + p8 + p9 + p10 + p11 + p12 + p13 +
     p14 + p15 + p16 + p17 + p18 + p19 == 58, p1 <= 4, p3 <= 4, 
  p8 <= 4, p12 <= 4, p17 <= 4, p19 <= 4, p2 <= 5, p4 <= 5, p7 <= 5, 
  p13 <= 5, p16 <= 5, p18 <= 5, p10 <= 7, p11 <= 7, p14 <= 7, 
  p15 <= 7, p5 <= 7, p6 <= 7, p9 <= 7}, {p1, p2, p3, p4, p5, p6, p7, 
  p8, p9, p10, p11, p12, p13, p14, p15, p16, p17, p18, p19}, Integers]

Within a minute or so all 32 gb of memory has been used and a few minutes later the kernel shuts down.

POSTED BY: Paul Cleary
13 Replies
Posted 5 years ago

Neil,

The values I supplied as solutions to the first few variables we found manually, I had found a full set of solutions that worked for all variables and as such I came to the conclusion that the problem is not solvable by the means available in Mma. For instance if we take p1, it can take 1 of 4 values, from 1 to 4, if it were 1 then the dependants could be any value from 1 to 7, if p1 were equal to 2 then one of the dependents has to be a 1 and the remaining ones any value up to 7 and so on, therefore how can you logically define a variable that has got moving dependants and on top of that we don't know what any of the variables are to start with only an upper value.

There could be a way by supplying a variable and working it through as far as it can but we would then come up against another block where we would have to supply another variable and so on, this would then be defeating the idea of trying to fully solve it.

So I am back to writing algorithms that try many values but it is a slow process, more so as the number of variables increases. As far as writing the equations and them getting large, I had automated this process programmatically, it was just a matter of supplying the correct syntax for the logic as strings and converting back with Toexpression, the logic was the stumbling block.

So, thank you very much for your time, much appreciated.

regards

paul.

POSTED BY: Paul Cleary

Paul,

It appears that your problem is "non-endogenous". Which means that your constraints depend on the values of the variables, pn. These are particularly hard problems to solve because the constraints change with the variables.

Can you solve the "stages" sequentially? Solve for p1, then use the value of p1 to solve for p2,p4,p5 and then from those values construct the constraints for the p2 dependencies -- or do the later solutions alter the earlier choices? For example, in your earlier example up to p7, how did you set p1=4? was that iterative until a complete solution was found?

If the later is the case you can try creating constraints that combine And and Or and enumerate all the possible constraint sets for each stage but that might get large and difficult to solve.

Regards,

Neil

POSTED BY: Neil Singer
Posted 5 years ago

Yes I see where the conflict occurs which is why I tended towards using the "or" operator as some are bigger but not necessarily all of them. These are specific values that work up to p7.

{p1 = 4, p2 = 3, p3 = 4, p4 = 2, p5 = 1, p6 = 2, p7 = 1}

and we can see that the first 3 statements are true and the values of p2, p4 and p5 are 1, 2 and 3 in some order, they are the values from 1 to p1 - 1. Now p2 dependents are {p1, p3, p5, p6} and because p2 = 3 that means of those 4 variables, 2 of them have to be 1 and 2, the other 2 variables can be any value from 1 up to 7. p3 has 3 dependents {p2, p6, p7} and because p3 = 4 they have to be a 1, 2 and 3 in some order.

To be concise here is the full set of relationships.

p1 , {p2,p4,p5}
p2 , {p3,p1,p5,p6}
p3 , {p2,p6,p7}
p4 , {p5,p1,p8,p9}
p5 , {p6,p4,p1,p2,p9,p10}
p6 , {p7,p5,p2,p3,p10,p11}
p7 , {p6,p3,p11,p12}
p8 , {p9,p4,p13}
p9 , {p10,p8,p5,p4,p14,p13}
p10 , {p11,p9,p6,p5,p15,p14}
p11 , {p12,p10,p7,p6,p16,p15}
p12 , {p11,p7,p16}
p13 , {p14,p8,p9,p17}
p14 , {p15,p13,p9,p10,p18,p17}
p15 , {p16,p14,p10,p11,p19,p18}
p16 , {p15,p11,p12,p19}
p17 , {p18,p13,p14}
p18 , {p19,p17,p14,p15}
p19 , {p18,p15,p16}

the format is from the top, p1's dependents are {p2, p4, p5} etc and what ever value the first variable is, the dependents have to contain all values from 1 to p(i) - 1, this implies that if a p value is 1 then all its dependents can be any value, but due to the constraints no where can any value be greater than 7. My task is to formulate the logic for this set of equations. The total sum of the 19 variables is 58 and it is the maximum this set of equations can take. If I can get the logic down then hopefully I can extend it up to a maximum of 2107 variables.

POSTED BY: Paul Cleary

I looked more closely, and it is true - all of the inequalities can be reduced to {p1==p2, p2==p3, ..., p18==p19}, which means that a solution must assign the same value to all of the p's. The sum p1+p2+...+p19=58 is unsatisfiable if all of the variables must be equal and integers, since 58/19 is 3.05263, which isn't an integer. It looks like you aren't encoding your problem correctly as a set of constraints if you think it is possible to solve - as stated, the equations are not satisfiable.

POSTED BY: Matthew Sottile

I think I see part of the problem. Looking closely at your list of constraints there, you see instances like “p1 >= p2” and later “p2 >= p1”. That implies that “p1 == p2”, so a solution will only be found if that is true. There are a number of instances in your constraint set where equality is implied, even though you specified the constraints as >= inequalities. I am guessing that a result of this is that your constraint that all of the variables add to 58 is unsatisfiable, so the solver returns nothing. If I have time after I grab lunch, I might see if it becomes clearer if the system of equations is simplified by hand (e.g., manually replace pairs of constraints like p1 >= p2, p2 >= p1 with one constraint that p1 == p2.)

POSTED BY: Matthew Sottile
Posted 5 years ago

Alexander, this is what I have at the moment and it doesn't equate to anything, i.e. no solution. So I can only assume the logic is wrong and doesn't accurately describe the desired problem.

Solve[{p1 >= p2, p1 >= p4, p1 >= p5, p2 >= p3, p2 >= p1, p2 >= p5, 
  p2 >= p6, p3 >= p2, p3 >= p6, p3 >= p7, p4 >= p5, p4 >= p1, 
  p4 >= p8, p4 >= p9, p5 >= p6, p5 >= p4, p5 >= p1, p5 >= p2, 
  p5 >= p9, p5 >= p10, p6 >= p7, p6 >= p5, p6 >= p2, p6 >= p3, 
  p6 >= p10, p6 >= p11, p7 >= p6, p7 >= p3, p7 >= p11, p7 >= p12, 
  p8 >= p9, p8 >= p4, p8 >= p13, p9 >= p10, p9 >= p8, p9 >= p5, 
  p9 >= p4, p9 >= p14, p9 >= p13, p10 >= p11, p10 >= p9, p10 >= p6, 
  p10 >= p5, p10 >= p15, p10 >= p14, p11 >= p12, p11 >= p10, 
  p11 >= p7, p11 >= p6, p11 >= p16, p11 >= p15, p12 >= p11, 
  p12 >= p7, p12 >= p16, p13 >= p14, p13 >= p8, p13 >= p9, 
  p13 >= p17, p14 >= p15, p14 >= p13, p14 >= p9, p14 >= p10, 
  p14 >= p18, p14 >= p17, p15 >= p16, p15 >= p14, p15 >= p10, 
  p15 >= p11, p15 >= p19, p15 >= p18, p16 >= p15, p16 >= p11, 
  p16 >= p12, p16 >= p19, p17 >= p18, p17 >= p13, p17 >= p14, 
  p18 >= p19, p18 >= p17, p18 >= p14, p18 >= p15, p19 >= p18, 
  p19 >= p15, p19 >= p16, p1 > 0, p2 > 0, p3 > 0, p4 > 0, p5 > 0, 
  p6 > 0, p7 > 0, p8 > 0, p9 > 0, p10 > 0, p11 > 0, p12 > 0, p13 > 0, 
  p14 > 0, p15 > 0, p16 > 0, p17 > 0, p18 > 0, p19 > 0, 
  p1 + p2 + p3 + p4 + p5 + p6 + p7 + p8 + p9 + p10 + p11 + p12 + p13 +
     p14 + p15 + p16 + p17 + p18 + p19 == 58, p1 <= 4, p3 <= 4, 
  p8 <= 4, p12 <= 4, p17 <= 4, p19 <= 4, p2 <= 5, p4 <= 5, p7 <= 5, 
  p13 <= 5, p16 <= 5, p18 <= 5, p10 <= 7, p11 <= 7, p14 <= 7, 
  p15 <= 7, p5 <= 7, p6 <= 7, p9 <= 7}, {p1, p2, p3, p4, p5, p6, p7, 
  p8, p9, p10, p11, p12, p13, p14, p15, p16, p17, p18, p19}, Integers]

Regards

Paul.

POSTED BY: Paul Cleary

Paul, attach file with code, perhaps we will find a solution.

Posted 5 years ago

Alexander

I did mention that what I had posted was only a small part, the full set of equations runs to many lines and I didn't want to post it all. the "..." is as far as I know the default way to indicate that there are more items without showing them.

POSTED BY: Paul Cleary

If there are 19 variables, then why are there only 11 in your code and what does "..." mean?

Posted 5 years ago

Neil,

Thank you, I shall definitely use your method from now on, I shall re-write my code and see what happens, though I still think it is going to crash and burn.

Regards

Paul.

POSTED BY: Paul Cleary

Paul,

Yes, the &&'s are not needed.

As a side note, if you use && or || I like to use parenthesis -- && and || have a high precedence so you can get some strange results if the input can be interpreted two ways. So my practice is to always type (p1>p2)&&(p1>p4) In this case it is not needed but I've been burned by the case when the && operates on the two expression halves first.

Regards,

Neil

POSTED BY: Neil Singer
Posted 5 years ago

Neil,

You are right, they should be &&'s . and in that case I have a small question, would say p1>=p2&&p1>=p4 etc be equivalent to {p1>=p2, p1>=p4, …} without the && operator?

Regards

Paul.

POSTED BY: Paul Cleary

Paul,

Shouldn’t your “or” operator be “and” (&&)? Don’t you want p2, p4, and p5 to all be less than p1? Or am I misreading your description?

Regards,

Neil

POSTED BY: Neil Singer
Reply to this discussion
Community posts can be styled and formatted using the Markdown syntax.
Reply Preview
Attachments
Remove
or Discard

Group Abstract Group Abstract