Ask Your Question

Enumerating solutions to a system of linear relations

asked 2015-05-30 00:22:18 -0500

CptnChristo gravatar image

updated 2015-05-30 15:18:20 -0500

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.

edit retag flag offensive close merge delete

1 answer

Sort by ยป oldest newest most voted

answered 2015-05-30 06:44:16 -0500

Nathann gravatar image

Hello !

It seems that you are looking for that:

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:

Good luck,


edit flag offensive delete link more


Thank 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.

CptnChristo gravatar imageCptnChristo ( 2015-05-30 13:40:07 -0500 )edit

Your Answer

Please start posting anonymously - your entry will be published after you log in or create a new account.

Add Answer

Question Tools

1 follower


Asked: 2015-05-30 00:22:18 -0500

Seen: 71 times

Last updated: May 30 '15