0
$\begingroup$

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.

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

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]] =!= {} &]
]
$\endgroup$
1
$\begingroup$

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

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

A comment (with figure):

A large number of solutions:

enter image description here

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – two black lines in the middle Mar 13 '18 at 22:46
  • $\begingroup$ Now that you have changed your graphic, yes, there are a "large number of solutions," but not infinite. imgur.com/a/HAuMA $\endgroup$ – two black lines in the middle Mar 13 '18 at 22:48
  • $\begingroup$ @ 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 $\endgroup$ – Anxon Pués Mar 14 '18 at 16:00
  • $\begingroup$ Mathematica. (I deleted the code yesterday, but if you learn how to program in Mathematica such figures are quite simple.) $\endgroup$ – David G. Stork Mar 14 '18 at 16:02
1
$\begingroup$

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.

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

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

enter image description here

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}}
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.