# Find all the closest positive integer solutions within a bound for a simple linear equation

Suppose I have a linear equation/inequality like

$$xA+yB \leq C,$$

with $x,y \in \mathbb{Z}^{+}_{\neq 0}$ and $A,B,C \in \{x | x = 0.01\mu, \forall \mu \in \mathbb{Z}^+_{\neq0}\}$. I want to find all the closest (positive integer) pairs $(x,y)$ such that:

$$\delta \leq xA+yB \leq C, \delta\in\mathbb{R}.$$

How can this be done in Mathematica? I want to find the closest positive integer solution to the line. I can do this visually, and just circle pairs, but it would be nice to have an automatic method to generate such pairs.

As $x,y$ are clearly "quantities" of things, and $A,B,C$ are "monetary values" an example of a linear equation (with a $\delta = 76.92$) might be something like this:

$$76.92 \leq 4.54x + 7.31y \leq 81.92$$

It would be nice if this could be generalized for more variables too, that is, like this:

$$\delta \leq x_0A_0+x_1A_1+\dots +x_nA_n \leq C, \delta \in \mathbb{R}$$

With $x_i\in \mathbb{Z}^+_{\neq 0}$ and $A_i\in \{x | x = 0.01\mu, \forall \mu \in \mathbb{Z}^+_{\neq0}\}$ as before.

• Won't there, in general, be an infinite number of solutions? – David G. Stork Mar 13 '18 at 21:18
• Positive integer solutions bounded by the line and the chosen $\delta$. It's basically all the positive integer solutions within a very thin trapezoid. – two black lines in the middle Mar 13 '18 at 21:22
• Very thin, infinitely long, trapezoid. – David G. Stork Mar 13 '18 at 21:54
• @DavidG.Stork, no, why do you think it's infinitely long? I don't understand. Maybe I'm not being clear enough. – two black lines in the middle Mar 13 '18 at 22:04
• Have you seen both FrobeniusSolve[] and KnapsackSolve[]? – J. M. will be back soon Mar 14 '18 at 1:27

Your question is a generalisation of a previous question.

Non-negative solutions to this linear Diophantine equation for positive coefficients {a,b} are given by NonnegLinearDiophantineTwo[{a,b},c].

NonnegLinearDiophantineTwo[{a_Integer, b_Integer}, c_Integer] :=
Block[{g, r, s, k},
{g, {r, s}} = ExtendedGCD[a, b];
Transpose[{r*c + b*k, s*c - a*k}/g /. k->Range[Ceiling[-r*c/b],Floor[s*c/a]]]
]


Make a table of solutions for the range of allowed c, then pick those with positive solutions.

Pick[#, Map[FreeQ[#, 0] &, #]] &[
Select[
Table[{c, NonnegLinearDiophantineTwo[{454, 731}, c]}, {c, 7692, 8192}],
#[] =!= {} &]
]


{{7741, {{9, 5}}}, {7764, {{1, 10}}}, {7818, {{14, 2}}}, {7841, {{6, 7}}}, {7918, {{11, 4}}}, {7941, {{3, 9}}}, {7995, {{16, 1}}}, {8018, {{8, 6}}}, {8095, {{13, 3}}}, {8118, {{5, 8}}}}

As @J.M. points out, the built-in function FrobeniusSolve[{a,b},c] is designed to solve these types of equations. FrobeniusSolve generalises to any number of coefficients. However, FrobeniusSolve is much slower than NonnegLinearDiophantineTwo in the case of two coefficients.

Pick[#, Map[FreeQ[#, 0] &, #]] &[
Select[
Table[{c, FrobeniusSolve[{454, 731}, c]}, {c, 7692, 8192}],
#[] =!= {} &]
]


You can use Solve or Reduce to enumerate all of the possibilities:

(* example *)
a = 11;
b = 4;
c = 30;
δ = 20;

Solve[x>0 && y>0 && δ < x a + b y < c, {x, y}, Integers]


{{x -> 1, y -> 3}, {x -> 1, y -> 4}, {x -> 2, y -> 1}}

If you just want to find the closest point, you can use LinearProgramming:

LinearProgramming[
-{a, b},
{{a, b}},
{{c-1/2, -1}},
1,
Integers
]


LinearProgramming::lpip: Warning: integer linear programming will use a machine-precision approximation of the inputs.

{1, 4}

Maximize[{x a + b y, δ < x a + b y < c && x>0 && y>0}, {x, y}, Integers]


{27, {x -> 1, y -> 4}}

• Can't find my key to my student Mathematica disk. Is there a way to run these functions remotely on a Mathematica server? – two black lines in the middle Mar 13 '18 at 22:08
• @twoblacklinesinthemiddle You could sign up for a free trial of Mathematica Online. – Carl Woll Mar 13 '18 at 22:18

A comment (with figure):

A large number of solutions: • You are forgetting that the constraint is $x,y,a,b,C>0$. If $x,y,a,b,C>0$, then you cannot have a "negative slope" as your graphic depicts. – two black lines in the middle Mar 13 '18 at 22:46
• Now that you have changed your graphic, yes, there are a "large number of solutions," but not infinite. imgur.com/a/HAuMA – two black lines in the middle Mar 13 '18 at 22:48
• @ David G. Stork, I would like to know how you made this grpah, and also how you made graphs in answer. Same about to put the equations over the lines – Anxon Pués Mar 14 '18 at 16:00
• Mathematica. (I deleted the code yesterday, but if you learn how to program in Mathematica such figures are quite simple.) – David G. Stork Mar 14 '18 at 16:02

if you have actual values of a,b,c,d this works

FindInstance[1 < 5 x + 2 y  < 8, {x, y}, Integers, 5]


{{x -> 110, y -> -272}, {x -> 186, y -> -462}, {x -> 980, y -> -2449}, {x -> 536, y -> -1339}, {x -> 650, y -> -1623

to have a graph intuition about possible solutions I tried this, it's easy to choose between three cases, no solutions, a few solutions or infinite.

Manipulate[
Plot[{y = c/b - c/a x, y = d/b - c/a x}, {x, -30, 30}], {a, -8,
8}, {b, -8, 8}, {c, -8, 8}, {d, -24, 24}]


It will be good if someone, can open ligth about this discusion options face to the values of a, b, c, d.

• This shows there is an infinite number of solutions. – David G. Stork Mar 13 '18 at 21:33
• I'm looking for positive integer solutions. – two black lines in the middle Mar 13 '18 at 21:59

Using the Region concept it is more explicit to arrive to solutions, if any.

RegionPlot[
ImplicitRegion[{-11 > -5  x - 7 y > -31 && x > 0 && y > 0  }, {x,
y}], AspectRatio -> {1, 1}, GridLines -> {Range, Range}] Solve[{x, y} \[Element]
ImplicitRegion[{-11 > -5  x - 7 y > -31 && x > 0 && y > 0  }, {x,
y}], {x, y}, Integers]

{{x -> 1, y -> 1}, {x -> 1, y -> 2}, {x -> 1, y -> 3}, {x -> 2,
y -> 1}, {x -> 2, y -> 2}, {x -> 3, y -> 1}, {x -> 3,
y -> 2}, {x -> 4, y -> 1}}