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$
7
  • 1
    $\begingroup$ Reduce? I'm not sure there's enough information to give a definitive answer. $\endgroup$ Commented Dec 9, 2013 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$ Commented Dec 9, 2013 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$ Commented Dec 9, 2013 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$ Commented Dec 9, 2013 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$ Commented Dec 9, 2013 at 14:24

3 Answers 3

Reset to default
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$
8
  • $\begingroup$ In my cases, there will be no Or, so don't worry about that. $\endgroup$ Commented Dec 9, 2013 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$ Commented Dec 9, 2013 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$ Commented Dec 9, 2013 at 9:01
  • $\begingroup$ @Loi.Luu That's because the expressions returned by Reduce contain Or. $\endgroup$ Commented Dec 9, 2013 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$ Commented Dec 10, 2013 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$

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.