ASKSAGE: Sage Q&A Forum - RSS feedhttps://ask.sagemath.org/questions/Q&A Forum for SageenCopyright Sage, 2010. Some rights reserved under creative commons license.Sat, 30 May 2015 20:40:07 +0200Enumerating solutions to a system of linear relationshttps://ask.sagemath.org/question/26979/enumerating-solutions-to-a-system-of-linear-relations/Hi, I'm new to sagemath, and I've been away from math courses for a while now. Please be patient with me! :)
I want to feed sagemath a system of linear relations. I'd like sagemath to give back all positive integer solutions to the system. I'll use a classic math exercise to illustrate.
You have pennies, nickels, and dimes. Find all combinations of coins that sum to at least 10 cents, but no more than 15 cents. Select between 5 and 7 coins (inclusive). Only nickels and dimes contribute to the wanted sum. Assume you have more than 7 of each type of coin.
In the relations below, 'pennies', 'nickels', and 'dimes' represent the number of coins from the respective denomination. So, the relations are:
pennies + nickels + dimes >= 5
pennies + nickels + dimes <= 7
5*nickels + 10*dimes >= 10
5*nickels + 10*dimes <= 15
I'd like sagemath to process the above system into a list of solutions similar to:
[
{ pennies: 4, nickels: 0, dimes: 1 },
{ pennies: 5, nickels: 0, dimes: 1 },
{ pennies: 6, nickels: 0, dimes: 1 },
{ pennies: 3, nickels: 1, dimes: 1 },
...
{ pennies: 4, nickels: 3, dimes: 0 }
]
This is what I've tried:
sage: pennies,nickels,dimes = var('pennies,nickels,dimes')
sage: coins_max = (pennies+nickels+dimes<=7)
sage: coins_min = (pennies+nickels+dimes>=5)
sage: value_max = (5*nickels+10*dimes<=15)
sage: value_min = (5*nickels+10*dimes>=10)
sage: assume( pennies>=0, pennies<=7, nickels>=0, nickels<=7, dimes>=0, dimes<=7 )
sage: coin_solve = solve( [coins_max, coins_min, value_max, value_min], pennies, nickels, dimes, solution_dict=True )
sage: print coin_solve
[
{-2*pennies + 8: nickels, dimes: -1/2*nickels + 1, nickels: -2*pennies + 12},
{-2*pennies + 7: nickels, dimes: -1/2*nickels + 3/2, nickels: -2*pennies + 11},
{-2*pennies + 7: nickels, dimes: -nickels - pennies + 5, nickels: -2*pennies + 8},
{-2*pennies + 11: nickels, dimes: -nickels - pennies + 7, nickels: -2*pennies + 12},
{-2*pennies + 7: nickels, max(-1/2*nickels + 1, -nickels - pennies + 5): dimes, dimes: min(-1/2*nickels + 3/2, -nickels - pennies + 7), nickels: -2*pennies + 12},
{pennies: dimes + 3, nickels: -2*dimes + 2},
{pennies: dimes + 5, nickels: -2*dimes + 2},
{pennies: dimes + 2, nickels: -2*dimes + 3},
{pennies: dimes + 4, nickels: -2*dimes + 3}
]
I don't know if solve() is the right approach. Do I need another function to further process solve()'s results? Do I need to write my own?
I'm hoping someone can point me in the right direction. Thank you for your time.Sat, 30 May 2015 07:22:18 +0200https://ask.sagemath.org/question/26979/enumerating-solutions-to-a-system-of-linear-relations/Answer by Nathann for <p>Hi, I'm new to sagemath, and I've been away from math courses for a while now. Please be patient with me! :)</p>
<p>I want to feed sagemath a system of linear relations. I'd like sagemath to give back all positive integer solutions to the system. I'll use a classic math exercise to illustrate.</p>
<p>You have pennies, nickels, and dimes. Find all combinations of coins that sum to at least 10 cents, but no more than 15 cents. Select between 5 and 7 coins (inclusive). Only nickels and dimes contribute to the wanted sum. Assume you have more than 7 of each type of coin.</p>
<p>In the relations below, 'pennies', 'nickels', and 'dimes' represent the number of coins from the respective denomination. So, the relations are:</p>
<pre><code>pennies + nickels + dimes >= 5
pennies + nickels + dimes <= 7
5*nickels + 10*dimes >= 10
5*nickels + 10*dimes <= 15
</code></pre>
<p>I'd like sagemath to process the above system into a list of solutions similar to:</p>
<pre><code>[
{ pennies: 4, nickels: 0, dimes: 1 },
{ pennies: 5, nickels: 0, dimes: 1 },
{ pennies: 6, nickels: 0, dimes: 1 },
{ pennies: 3, nickels: 1, dimes: 1 },
...
{ pennies: 4, nickels: 3, dimes: 0 }
]
</code></pre>
<p>This is what I've tried:</p>
<pre><code>sage: pennies,nickels,dimes = var('pennies,nickels,dimes')
sage: coins_max = (pennies+nickels+dimes<=7)
sage: coins_min = (pennies+nickels+dimes>=5)
sage: value_max = (5*nickels+10*dimes<=15)
sage: value_min = (5*nickels+10*dimes>=10)
sage: assume( pennies>=0, pennies<=7, nickels>=0, nickels<=7, dimes>=0, dimes<=7 )
sage: coin_solve = solve( [coins_max, coins_min, value_max, value_min], pennies, nickels, dimes, solution_dict=True )
sage: print coin_solve
[
{-2*pennies + 8: nickels, dimes: -1/2*nickels + 1, nickels: -2*pennies + 12},
{-2*pennies + 7: nickels, dimes: -1/2*nickels + 3/2, nickels: -2*pennies + 11},
{-2*pennies + 7: nickels, dimes: -nickels - pennies + 5, nickels: -2*pennies + 8},
{-2*pennies + 11: nickels, dimes: -nickels - pennies + 7, nickels: -2*pennies + 12},
{-2*pennies + 7: nickels, max(-1/2*nickels + 1, -nickels - pennies + 5): dimes, dimes: min(-1/2*nickels + 3/2, -nickels - pennies + 7), nickels: -2*pennies + 12},
{pennies: dimes + 3, nickels: -2*dimes + 2},
{pennies: dimes + 5, nickels: -2*dimes + 2},
{pennies: dimes + 2, nickels: -2*dimes + 3},
{pennies: dimes + 4, nickels: -2*dimes + 3}
]
</code></pre>
<p>I don't know if solve() is the right approach. Do I need another function to further process solve()'s results? Do I need to write my own?</p>
<p>I'm hoping someone can point me in the right direction. Thank you for your time.</p>
https://ask.sagemath.org/question/26979/enumerating-solutions-to-a-system-of-linear-relations/?answer=26981#post-id-26981Hello !
It seems that you are looking for that:
http://doc.sagemath.org/html/en/reference/geometry/sage/geometry/polyhedron/base.html#sage.geometry.polyhedron.base.Polyhedron_base.integral_points
Note that it is a bit slow currently, but it should be improved in a couple of months if I get to do what I plan to.
Also, in case you want to solve such a system of equations and would be looking for *one* solution (not all of them), know that you can use Mixed Integer Linear Programming in Sage quite easily:
http://doc.sagemath.org/html/en/thematic_tutorials/linear_programming.html#linear-programming
Good luck,
Nathann Sat, 30 May 2015 13:44:16 +0200https://ask.sagemath.org/question/26979/enumerating-solutions-to-a-system-of-linear-relations/?answer=26981#post-id-26981Comment by CptnChristo for <p>Hello !</p>
<p>It seems that you are looking for that:</p>
<p><a href="http://doc.sagemath.org/html/en/reference/geometry/sage/geometry/polyhedron/base.html#sage.geometry.polyhedron.base.Polyhedron_base.integral_points">http://doc.sagemath.org/html/en/refer...</a></p>
<p>Note that it is a bit slow currently, but it should be improved in a couple of months if I get to do what I plan to.</p>
<p>Also, in case you want to solve such a system of equations and would be looking for <em>one</em> solution (not all of them), know that you can use Mixed Integer Linear Programming in Sage quite easily:</p>
<p><a href="http://doc.sagemath.org/html/en/thematic_tutorials/linear_programming.html#linear-programming">http://doc.sagemath.org/html/en/thema...</a></p>
<p>Good luck,</p>
<p>Nathann </p>
https://ask.sagemath.org/question/26979/enumerating-solutions-to-a-system-of-linear-relations/?comment=26988#post-id-26988Thank you for the response! The algorithm being "slow" is to be expected. It's the nature of the problem. Though, I'm wrestling with how to convert the example into a set of polyhedron vertices. I assume each vertex coordinate represents one of the desired quantities (e.g. pennies, nickels, dimes). But the relations involve different quantities (i.e. "number of coins" versus "monetary value"). So I'm not sure how to map those quantities into a single n-dimensional polyhedron. I don't mean to impose, but could you offer a small example?
And, I wish one solution was enough. Unfortunately for me, this represents a sub-calculation within a larger probability question. I need all solutions to guarantee probability accuracy.
Again, thank you for your help.Sat, 30 May 2015 20:40:07 +0200https://ask.sagemath.org/question/26979/enumerating-solutions-to-a-system-of-linear-relations/?comment=26988#post-id-26988