2
$\begingroup$

I have a system of expressions, in which each expression is an equality or inequality expression of the following form:

  • Var = Var1 + Var2
  • Var $\odot$ number
  • Var $\odot$ Var1
  • $\odot$ = $\leq | \geq | == | > | <$

I want to find the range of values for each variable, is this possible to do that by Mathematica?

Update example

I tried with Reduce but it didn't work as I expected. For example, I tried Reduce[a == b + c && a >= 2 && b <= 10 && c == 5, {a, b, c}], it returned 2 <= a <= 15 && b == -5 + a && c == a - b.

What I expect to get is 2 <= a <= 15 && -3 <= b <= 10 && c == 5

Thanks,

||improve this question
$\endgroup$
  • 1
    $\begingroup$ Reduce? I'm not sure there's enough information to give a definitive answer. $\endgroup$ – Michael E2 Dec 9 '13 at 4:16
  • $\begingroup$ Reduce does not return what I want. For example, I tried Reduce[a == b + c && a >= 2 && b <= 10 && c == 5, {a, b, c}], it returns 2 <= a <= 15 && b == -5 + a && c == a - b. What I expect to get is 2 <= a <= 15 && -3 <= b <= 10 && c == 5 $\endgroup$ – Loi.Luu Dec 9 '13 at 4:21
  • 1
    $\begingroup$ Try Reduce[.., {a, b, c}], Reduce[.., {b, c, a}], and Reduce[.., {c, a, b}] -- the first inequality in each is what you're after. Perhaps there's a more efficient way. If this example is typical, you should consider adding it to your question. As it is, it's a bit vague. You could even include a few examples to show the range of problems you wish to deal with. $\endgroup$ – Michael E2 Dec 9 '13 at 4:26
  • $\begingroup$ Its not the optimal way to solve the problem, I think. Uhm, just updated the example to my question as you suggested. $\endgroup$ – Loi.Luu Dec 9 '13 at 4:31
  • 1
    $\begingroup$ It seems that you want the minimal bounding rectangle that is aligned with the axes. For this you can use Minimize and Maximize` on the separate variables. $\endgroup$ – Daniel Lichtblau Dec 9 '13 at 14:24
4
$\begingroup$

Perhaps there's a better way than using Reduce three times, but it seems to me that the computations to figure out the range of each variable will have to be done somehow. Reduce does that. This will work on such simple inequalities as in the OP's example:

And @@ (First@Reduce[a == b + c && a >= 2 && b <= 10 && c == 5, #] & /@
    NestList[RotateLeft, {a, b, c}, 2])

 (* 2 <= a <= 15 && -3 <= b <= 10 && c == 5 *)

For more complicated cases, one would have to check the Head of the result to see if there are cases, indicated by a head of Or. In that case, one would have to take the union of the ranges of each case.

With 100 variables the CylindricalDecomposition returned by Reduce will no doubt contain cases.

Here's a more generalized approach.

boundingBox[ineq_, vars_] := And @@ Simplify[
   Reduce[ineq, #] & /@ NestList[RotateLeft, vars, 2] //. And[first_, rest_] :> first
   ]

boundingBox[a == b + c && a >= 12 && b <= 10 && c <= 10 && b >= 1 && c >= 1, {a, b, c}]
(* 12 <= a <= 20 && 2 <= b <= 10 && 2 <= c <= 10 *)

In some fashion, the maximum and minimum values of each variable have to be computed. Reduce does more than that in computing the cylindrical decomposition, so perhaps some time may be saved. If we can assume that the inequalities are closed, we can try finding the extrema directly.

boundingBox2[ineq_, vars_] := 
 And @@ (MinValue[{#, ineq}, vars] <= # <= MaxValue[{#, ineq}, vars] & /@ vars)

boundingBox2[a == b + c && a >= 12 && b <= 10 && c <= 10 && b >= 1 && c >= 1, {a, b, c}]
(* 12 <= a <= 20 && 2 <= b <= 10 && 2 <= c <= 10 *)

It's actually faster on this example.

SetAttributes[timeAvg, HoldFirst]
timeAvg[func_] := 
  Do[If[# > 0.3, Return[#/5^i]] & @@  AbsoluteTiming@Do[func, {5^i}], {i, 0, 15}]

boundingBox[
  a == b + c && a >= 12 && b <= 10 && c <= 10 && b >= 1 && c >= 1, {a, b, c}] // timeAvg
boundingBox2[
  a == b + c && a >= 12 && b <= 10 && c <= 10 && b >= 1 && c >= 1, {a, b, c}] // timeAvg
(* 0.01004385 *)
(* 0.00204969 *)
||improve this answer
$\endgroup$
  • $\begingroup$ In my cases, there will be no Or, so don't worry about that. $\endgroup$ – Loi.Luu Dec 9 '13 at 5:04
  • $\begingroup$ So in your solution, we still have to call Reduce 3 times, right? Since my system of expressions may include up to 100 variables, it will definitely cost the efficiency if we call Reduce 100 times... $\endgroup$ – Loi.Luu Dec 9 '13 at 5:09
  • 1
    $\begingroup$ I tried your solution with a == b + c && a >= 12 && b <= 10 && c <= 10 && b >= 1 && c >= 1, the result is not clean. I expect something like 20 >= a >= 12, 10 >= b >= 2, 10 >= c >= 2. $\endgroup$ – Loi.Luu Dec 9 '13 at 9:01
  • $\begingroup$ @Loi.Luu That's because the expressions returned by Reduce contain Or. $\endgroup$ – Michael E2 Dec 9 '13 at 11:12
  • 2
    $\begingroup$ @Loi.Luu According to the documentation, you can specify the domain to be Integers for MinValue and MaxValue. You could also use Ceiling and Floor on them. Finally one can add && Element[a, Integers] to the inequalities. $\endgroup$ – Michael E2 Dec 10 '13 at 2:29
2
$\begingroup$

You can try the existance statement:

Reduce[
       Exists[{#2, #3},
              a == b + c && a >= 2 && b <= 10 && c == 5
             ],
      #1] & @@
  RotateLeft[{a, b, c}, #] & /@ Range[0, 2]

{2 <= a <= 15, -3 <= b <= 10, c == 5}
||improve this answer
$\endgroup$
0
$\begingroup$

Backsubstitution is an option often ignored when people use Reduce. In the op's case it gives:

  Reduce[a == b + c && a >= 2 && b <= 10 && c == 5, {a, b, c}, Backsubstitution -> True]
  2 <= a <= 15 && b == -5 + a && c == 5

The op's writes: " What I expect to get is 2 <= a <= 15 && -3 <= b <= 10 && c == 5 "

Notice : Mathematica should not produce this outcome because it is not a description of the solution set of the equations inputed. For example, a==2, b==10, c==5 falls in the range 2 <= a <= 15 && -3 <= b <= 10 && c == 5 but it is not a solution of the system

||improve this answer
$\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.