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$
13
  • $\begingroup$ Won't there, in general, be an infinite number of solutions? $\endgroup$ Mar 13, 2018 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$ Mar 13, 2018 at 21:22
  • $\begingroup$ Very thin, infinitely long, trapezoid. $\endgroup$ Mar 13, 2018 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$ Mar 13, 2018 at 22:04
  • 2
    $\begingroup$ Have you seen both FrobeniusSolve[] and KnapsackSolve[]? $\endgroup$ Mar 14, 2018 at 1:27

5 Answers 5

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$
2
  • $\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$ Mar 13, 2018 at 22:08
  • $\begingroup$ @twoblacklinesinthemiddle You could sign up for a free trial of Mathematica Online. $\endgroup$
    – Carl Woll
    Mar 13, 2018 at 22:18
1
$\begingroup$

A comment (with figure):

A large number of solutions:

enter image description here

$\endgroup$
4
  • $\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$ Mar 13, 2018 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$ Mar 13, 2018 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$ Mar 14, 2018 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$ Mar 14, 2018 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$
2
  • $\begingroup$ This shows there is an infinite number of solutions. $\endgroup$ Mar 13, 2018 at 21:33
  • $\begingroup$ I'm looking for positive integer solutions. $\endgroup$ Mar 13, 2018 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.