-1

I am looking for a way to produce a given total ($n$) using fixed parts $(a, b, c)$ in multiples $(x, y, z)$: $ax+by+cz=n$, in such a way that $x+y+z$ is as small as possible, using integers only.

An example: where $n=50$, $a=9$, $b=7$, and $c=4$, $a(4)+b(2)+c(0)=n$ is a better solution than $a(2)+b(4)+c(1)=n$, because $4+2+0<2+4+1$.

EDIT: All integers are to be non-negative. An easy real-world example would be making change - it's ideal to use the least possible number of coins to deliver the required sum. These are the types of problems I am trying to figure out how to solve; I have several, with different values for all given variables.

Is there some way to calculate this, or do I just need to attempt to noodle out all of my solutions? TIA!

RS Piper
  • 1
  • You might want to try the "optimization" tag, that's what this type of problem is typically called. – Exnur Oct 07 '20 at 01:57
  • Additionally, my suspicion is that this doesn't have an optimal solution - x+y+z=T is (I think) a 3D hyperplane in 4D space, and ax+by+yz=n is a 2D plane - the two may have infinitely many solutions (in which case there is always a smaller combination, no minimum). You may be able to make something happen by restricting x,y,z to be non-negative, though. – Exnur Oct 07 '20 at 02:14
  • Good catch - yes, I do intend to use only non-negative integers. I'll edit my question – RS Piper Oct 07 '20 at 19:39

1 Answers1

1

This is an integer linear programming problem. You want to minimize $x+y+z$ subject to: \begin{align} ax + by + cz &= n\\ x &\ge 0 \text{ and integer} \\ y &\ge 0 \text{ and integer} \\ z &\ge 0 \text{ and integer} \end{align} The linear programming relaxation yields lower bound $$\lceil \min(n/a,n/b,n/c)\rceil = \lceil n\min(1/a,1/b,1/c)\rceil =\lceil n/\max(a,b,c)\rceil.$$ For your example data, this lower bound is $6$, certifying optimality of $(x,y,z)=(4,2,0)$.

RobPratt
  • 45,619
  • Not sure I understand entirely - If I'm reading your comment right, you are telling me that I need to know the "lower bound" before determining x, y, and z? E.g., using my example data, [n/ max(a,b,c)]=6? – RS Piper Oct 07 '20 at 19:45
  • The LP relaxation has optimal solution $(x,y,z)=(n/a,0,0)$, $(x,y,z)=(0,n/b,0)$, or $(x,y,z)=(0,0,n/c)$, depending on which is smallest out of $n/a$, $n/b$, or $n/c$ Because the objective function $x+y+z$ is required to be integer-valued, the ceiling of the smallest value is a valid lower bound on the optimal integer linear programming objective value. – RobPratt Oct 07 '20 at 20:01
  • Would x+y+z, then, be the objective function, and my first constraint, using the example data, be 9x+7y+4z=50? – RS Piper Oct 07 '20 at 22:26
  • Yes, you have correctly identified the objective function and the linear constraint. – RobPratt Oct 07 '20 at 22:35
  • I seem to be still missing something. I have read into the terms you've used that I didn't understand - the hardest concept to grasp is relaxation - but after clarifying the objective function and first constraint I attempted to recreate the example data using Wofram Alpha's Linear Programming Calculator to no avail - I get the error "Not a valid input; please try again" – RS Piper Oct 07 '20 at 22:52
  • https://www.wolframalpha.com/input/?i=Minimize+x%2By%2Bz+subject+to+9x%2B7y%2B4z%3D50+and+x+%3E%3D0+and+y%3E%3D0+and+z%3E%3D0 – RobPratt Oct 08 '20 at 00:30
  • Sorry for being AWOL for a couple days; had a lot going on. That was a completely different calculator than I was using; but it does seem to do the job with the exception of the integer restraint (example data yields (50/9, 0, 0) instead of (4,2,0)). I've again done further research based off the pointers you've given, this time pursuing the calculator you linked with a goal of restricting it to integer output, but again fruitlessly – RS Piper Oct 12 '20 at 19:16