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

Question

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.

Answer 1

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}],
      #[[2]] =!= {} &]
]

{{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}],
      #[[2]] =!= {} &]
]

Answer 2

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}

or Maximize:

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

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

Answer 3

A comment (with figure):

A large number of solutions:

Answer 4

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.

Answer 5

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[5], Range[3]}]

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}}