Problems with FindInstance in v. 11

I have been trying to solve a system of linear equations and linear inequalities with 18 unknowns. I would think that for Mathematica giving an answer to such question will be a matter of milliseconds. Instead, the kernel runs for ages, uses up the entire CPU and RAM and then stops without providing any message. Just as if I did not let run the program at all.

Does anyone know what could be the problem? (and maybe how can I get ao some answer to my exercise?). Or is it a software bug? Thank you!!

Here is my code:

FindInstance[{1/5 t12 + 1/5 t22 + 3/5 t32 == 0,
1/5 t1 + 1/5 t2 + 3/5 t3 == 0,
Min[1/5 t12 + 1/5 t22 + 3/5 t32, 1/5 t1 + 1/5 t2 + 3/5 t3] +
Min[1/5 t1 + 1/5 t4 + 3/5 t7, 1/5 t12 + 1/5 t42 + 3/5 t72] >=
Min[1/5 t42 + 1/5 t52 + 3/5 t62, 1/5 t4 + 1/5 t5 + 3/5 t6] +
Min[ 1/5 t2 + 1/5 t5 + 3/5 t8, 1/5 t22 + 1/5 t52 + 3/5 t82],
Min[1/5 t12 + 1/5 t22 + 3/5 t32, 1/5 t1 + 1/5 t2 + 3/5 t3] +
Min[1/5 t1 + 1/5 t4 + 3/5 t7, 1/5 t12 + 1/5 t42 + 3/5 t72] >=
Min[1/5 t72 + 1/5 t82 + 3/5 t92, 1/5 t7 + 1/5 t8 + 3/5 t9] +
Min[ 1/5 t3 + 1/5 t6 + 3/5 t9, 1/5 t32 + 1/5 t62 + 3/5 t92],
Min[1/5 t42 + 1/5 t52 + 3/5 t62, 1/5 t4 + 1/5 t5 + 3/5 t6] < 0,
Min[1/5 t72 + 1/5 t82 + 3/5 t92, 1/5 t7 + 1/5 t8 + 3/5 t9] < 0,
Min[1/2 (1/5 + 1/9) t12 + 1/2 (1/5 + 1/9) t22 + 1/2 (3/5 + 7/9) t32,
1/2 (1/5 + 1/9) t1 + 1/2 (1/5 + 1/9) t2 + 1/2 (3/5 + 7/9) t3] < 0,
1/2 (1/5 + 1/9) t42 + 1/2 (1/5 + 1/9) t52 + 1/2 (3/5 + 7/9) t62 == 0,
1/2 (1/5 + 1/9) t4 + 1/2 (1/5 + 1/9) t5 + 1/2 (3/5 + 7/9) t6 == 0,
Min[1/2 (1/5 + 1/9) t7 + 1/2 (1/5 + 1/9) t8 + 1/2 (3/5 + 7/9) t9,
1/2 (1/5 + 1/9) t72 + 1/2 (1/5 + 1/9) t82 + 1/2 (3/5 + 7/9) t92] <0,
Min[1/9 t12 + 1/9 t22 + 7/9 t32, 1/9 t1 + 1/9 t2 + 7/9 t3] < 0,
Min[1/9 t42 + 1/9 t52 + 7/9 t62, 1/9 t4 + 1/9 t5 + 7/9 t6] < 0,
1/9 t72 + 1/9 t82 + 7/9 t92 == 0, 1/9 t7 + 1/9 t8 + 7/9 t9 == 0},
{t12, t22, t32, t42, t52, t62, t72, t82, t92, t1, t2, t3, t4, t5, t6,t7, t8, t9}, Reals]

• Why do you think Mathematica should be able to do this instantly? What is your reasoning? Not all problems can be easily computed. – user6014 Mar 6 '18 at 20:47
• Mathematica does well with a portion of the equations, but as soon as I include too many of them memory spikes. For example, assuming eqns is your list of equations, MemoryConstrained[FindInstance[eqns[[3 ;;]], {t1, t2, t3, t12, t22, t32, t42, t52, t62, t4, t5, t6, t7, t8, t9, t72, t82, t92}, Reals], 4000000000] // AbsoluteTiming quits after ~15 seconds on my machine. So it uses 4GB of RAM in 15 seconds, and from my tests would only keep climbing. This is with only 16 of your 18 equations. – user6014 Mar 6 '18 at 21:03
• I would do what you can to reduce the number of variables/equations. – user6014 Mar 6 '18 at 21:10
• Take a half of the system and find instance for it. Then verify all the system for these values. Then add to the half of the system the false equations/inequalities and find instance again and so on. – user64494 Mar 6 '18 at 21:19
• Thank you. @user6014 I found that 4th inequality (with Min) is the game stopper, without it the solution comes within milliseconds. I was thinking that it would be easy because just yesterday I was running a highly non-linear polynomial approximation with 24 unknowns and CPU and memory use was about 30% and at the end of 4 hours all was solved. So it kills all intuition for why a system of linear equations-inequalities takes that much of memory/time. – Kass Mar 6 '18 at 22:52

eqns = {1/5 t12 + 1/5 t22 + 3/5 t32 == 0, 1/5 t1 + 1/5 t2 + 3/5 t3 == 0,
Min[1/5 t12 + 1/5 t22 + 3/5 t32, 1/5 t1 + 1/5 t2 + 3/5 t3] +
Min[1/5 t1 + 1/5 t4 + 3/5 t7, 1/5 t12 + 1/5 t42 + 3/5 t72] >=
Min[1/5 t42 + 1/5 t52 + 3/5 t62, 1/5 t4 + 1/5 t5 + 3/5 t6] +
Min[1/5 t2 + 1/5 t5 + 3/5 t8, 1/5 t22 + 1/5 t52 + 3/5 t82],
Min[1/5 t12 + 1/5 t22 + 3/5 t32, 1/5 t1 + 1/5 t2 + 3/5 t3] +
Min[1/5 t1 + 1/5 t4 + 3/5 t7, 1/5 t12 + 1/5 t42 + 3/5 t72] >=
Min[1/5 t72 + 1/5 t82 + 3/5 t92, 1/5 t7 + 1/5 t8 + 3/5 t9] +
Min[1/5 t3 + 1/5 t6 + 3/5 t9, 1/5 t32 + 1/5 t62 + 3/5 t92],
Min[1/5 t42 + 1/5 t52 + 3/5 t62, 1/5 t4 + 1/5 t5 + 3/5 t6] < 0,
Min[1/5 t72 + 1/5 t82 + 3/5 t92, 1/5 t7 + 1/5 t8 + 3/5 t9] < 0,
Min[1/2 (1/5 + 1/9) t12 + 1/2 (1/5 + 1/9) t22 + 1/2 (3/5 + 7/9) t32,
1/2 (1/5 + 1/9) t1 + 1/2 (1/5 + 1/9) t2 + 1/2 (3/5 + 7/9) t3] < 0,
1/2 (1/5 + 1/9) t42 + 1/2 (1/5 + 1/9) t52 + 1/2 (3/5 + 7/9) t62 == 0,
1/2 (1/5 + 1/9) t4 + 1/2 (1/5 + 1/9) t5 + 1/2 (3/5 + 7/9) t6 == 0,
Min[1/2 (1/5 + 1/9) t7 + 1/2 (1/5 + 1/9) t8 + 1/2 (3/5 + 7/9) t9,
1/2 (1/5 + 1/9) t72 + 1/2 (1/5 + 1/9) t82 + 1/2 (3/5 + 7/9) t92] < 0,
Min[1/9 t12 + 1/9 t22 + 7/9 t32, 1/9 t1 + 1/9 t2 + 7/9 t3] < 0,
Min[1/9 t42 + 1/9 t52 + 7/9 t62, 1/9 t4 + 1/9 t5 + 7/9 t6] < 0,
1/9 t72 + 1/9 t82 + 7/9 t92 == 0, 1/9 t7 + 1/9 t8 + 7/9 t9 == 0} //
Simplify;


Extract equations, i.e., remove inequalities

eqns2 = Cases[eqns, Equal[_, 0]]

(* {t12 + t22 + 3 t32 == 0, t1 + t2 + 3 t3 == 0, 7 t42 + 7 t52 + 31 t62 == 0,
7 t4 + 7 t5 + 31 t6 == 0, t72 + t82 + 7 t92 == 0, t7 + t8 + 7 t9 == 0} *)

n = Length[eqns2];

vars = Variables[Level[eqns, {-1}]];


Find a subset of vars that solves eqns2

varsn = Subsets[vars, {n}];

lvn = Length[varsn];

ptr = 0;
finished = False;
While[! (finished), ptr++; sol1 = Solve[eqns2, varsn[[ptr]]];
finished = sol1 =!= {} || ptr == lvn] p;
sol1

(* {{t1 -> -t2 - 3 t3, t12 -> -t22 - 3 t32, t4 -> 1/7 (-7 t5 - 31 t6),
t42 -> 1/7 (-7 t52 - 31 t62), t7 -> -t8 - 7 t9, t72 -> -t82 - 7 t92}} *)

eqns2 = DeleteCases[eqns /. sol1[], True];

vars2 = Variables[Level[eqns2, {-1}]];

sol2 = FindInstance[eqns2, vars2][]

{t2 -> 0, t22 -> 0, t3 -> -1, t32 -> 0, t5 -> 0, t52 -> 0, t6 -> 1, t62 -> -1,
t8 -> -(50/7), t82 -> 0, t9 -> 1, t92 -> 38/147}

sol = Join[sol2, sol1[] /. sol2]

(* {t2 -> 0, t22 -> 0, t3 -> -1, t32 -> 0, t5 -> 0, t52 -> 0, t6 -> 1, t62 -> -1,
t8 -> -(50/7), t82 -> 0, t9 -> 1, t92 -> 38/147, t1 -> 3, t12 -> 0,
t4 -> -(31/7), t42 -> 31/7, t7 -> 1/7, t72 -> -(38/21)} *)


Verifying that sol satisfies all equations and inequalities

And @@ (eqns /. sol)

(* True *)


It can be handled by recasting the Min expressions as a convex combination of their constituents, with the added inequalities that the convex combination be less-equal to both constituents. The function below will assist in this transformation.

ineq[Min[a_, b_]] :=
With[{nv = Unique[m]}, {nv*a + nv*b, {nv >= 0, nv >= 0,
nv + nv == 1, nv*a + nv*b <= a,
nv*a + nv*b <= b}}]

system = {1/5 t12 + 1/5 t22 + 3/5 t32 == 0,
1/5 t1 + 1/5 t2 + 3/5 t3 == 0,
Min[1/5 t12 + 1/5 t22 + 3/5 t32, 1/5 t1 + 1/5 t2 + 3/5 t3] +
Min[1/5 t1 + 1/5 t4 + 3/5 t7, 1/5 t12 + 1/5 t42 + 3/5 t72] >=
Min[1/5 t42 + 1/5 t52 + 3/5 t62, 1/5 t4 + 1/5 t5 + 3/5 t6] +
Min[1/5 t2 + 1/5 t5 + 3/5 t8, 1/5 t22 + 1/5 t52 + 3/5 t82],
Min[1/5 t12 + 1/5 t22 + 3/5 t32, 1/5 t1 + 1/5 t2 + 3/5 t3] +
Min[1/5 t1 + 1/5 t4 + 3/5 t7, 1/5 t12 + 1/5 t42 + 3/5 t72] >=
Min[1/5 t72 + 1/5 t82 + 3/5 t92, 1/5 t7 + 1/5 t8 + 3/5 t9] +
Min[1/5 t3 + 1/5 t6 + 3/5 t9, 1/5 t32 + 1/5 t62 + 3/5 t92],
Min[1/5 t42 + 1/5 t52 + 3/5 t62, 1/5 t4 + 1/5 t5 + 3/5 t6] < 0,
Min[1/5 t72 + 1/5 t82 + 3/5 t92, 1/5 t7 + 1/5 t8 + 3/5 t9] < 0,
Min[1/2 (1/5 + 1/9) t12 + 1/2 (1/5 + 1/9) t22 +
1/2 (3/5 + 7/9) t32,
1/2 (1/5 + 1/9) t1 + 1/2 (1/5 + 1/9) t2 + 1/2 (3/5 + 7/9) t3] <
0, 1/2 (1/5 + 1/9) t42 + 1/2 (1/5 + 1/9) t52 +
1/2 (3/5 + 7/9) t62 == 0,
1/2 (1/5 + 1/9) t4 + 1/2 (1/5 + 1/9) t5 + 1/2 (3/5 + 7/9) t6 == 0,
Min[1/2 (1/5 + 1/9) t7 + 1/2 (1/5 + 1/9) t8 + 1/2 (3/5 + 7/9) t9,
1/2 (1/5 + 1/9) t72 + 1/2 (1/5 + 1/9) t82 +
1/2 (3/5 + 7/9) t92] < 0,
Min[1/9 t12 + 1/9 t22 + 7/9 t32, 1/9 t1 + 1/9 t2 + 7/9 t3] < 0,
Min[1/9 t42 + 1/9 t52 + 7/9 t62, 1/9 t4 + 1/9 t5 + 7/9 t6] < 0,
1/9 t72 + 1/9 t82 + 7/9 t92 == 0, 1/9 t7 + 1/9 t8 + 7/9 t9 == 0};


Now rewrite the system by extracting and replacing all Min terms and augmenting with the new inequalities. Also extract the full set of variables,

mins = Cases[system, Verbatim[Min][__], Infinity];
newEqsAndIneqsMin = Map[ineq, mins];
{newEqsMin, newIneqsMin} = Transpose[newEqsAndIneqsMin ];
newsys = system /. Thread[mins -> newEqsMin];
fullsys = Flatten[{newsys, newIneqsMin}];
allVars = Variables[Apply[Subtract, fullsys, {1}]];


FindInstance will handle this just fine.

AbsoluteTiming[vals = FindInstance[fullsys, allVars]]

(* Out= {0.493288, {{t1 -> 103/8, t12 -> 1, t2 -> -(55/8),
t22 -> -1, t3 -> -2, t32 -> 0, t4 -> 31/7, t42 -> -(31/7), t5 -> 0,
t52 -> 0, t6 -> -1, t62 -> 1, t7 -> -7, t72 -> 0, t8 -> 0,
t82 -> 0, t9 -> 1, t92 -> 0, m$96625 -> 1, m$96625 -> 0,
m$96626 -> 1, m$96626 -> 0, m$96627 -> 0, m$96627 -> 1,
m$96628 -> 1, m$96628 -> 0, m$96629 -> 1, m$96629 -> 0, m$96630 -> 1, m$96630 -> 0, m$96631 -> 1, m$96631 -> 0, m$96632 -> 1, m$96632 -> 0,
m$96633 -> 0, m$96633 -> 1, m$96634 -> 1, m$96634 -> 0,
m$96635 -> 1, m$96635 -> 0, m$96636 -> 1, m$96636 -> 0, m$96637 -> 1, m$96637 -> 0, m$96638 -> 1, m$96638 -> 0}}} *)


Check:

In:= system /. vals

(* Out= {{True, True, True, True, True, True, True, True, True,
True, True, True, True, True}} *)


You get a full solution set and a lot of instance solutions, if you substitute for all Min[a,b], Min[c,d],... by all possible combinations of a,b,c,d,...

(eqs = {1/5 t12 + 1/5 t22 + 3/5 t32 == 0,
1/5 t1 + 1/5 t2 + 3/5 t3 == 0,
Min[1/5 t12 + 1/5 t22 + 3/5 t32, 1/5 t1 + 1/5 t2 + 3/5 t3] +
Min[1/5 t1 + 1/5 t4 + 3/5 t7, 1/5 t12 + 1/5 t42 + 3/5 t72] >=
Min[1/5 t42 + 1/5 t52 + 3/5 t62, 1/5 t4 + 1/5 t5 + 3/5 t6] +
Min[1/5 t2 + 1/5 t5 + 3/5 t8, 1/5 t22 + 1/5 t52 + 3/5 t82],
Min[1/5 t12 + 1/5 t22 + 3/5 t32, 1/5 t1 + 1/5 t2 + 3/5 t3] +
Min[1/5 t1 + 1/5 t4 + 3/5 t7, 1/5 t12 + 1/5 t42 + 3/5 t72] >=
Min[1/5 t72 + 1/5 t82 + 3/5 t92, 1/5 t7 + 1/5 t8 + 3/5 t9] +
Min[1/5 t3 + 1/5 t6 + 3/5 t9, 1/5 t32 + 1/5 t62 + 3/5 t92],
Min[1/5 t42 + 1/5 t52 + 3/5 t62, 1/5 t4 + 1/5 t5 + 3/5 t6] < 0,
Min[1/5 t72 + 1/5 t82 + 3/5 t92, 1/5 t7 + 1/5 t8 + 3/5 t9] < 0,
Min[1/2 (1/5 + 1/9) t12 + 1/2 (1/5 + 1/9) t22 +
1/2 (3/5 + 7/9) t32,
1/2 (1/5 + 1/9) t1 + 1/2 (1/5 + 1/9) t2 + 1/2 (3/5 + 7/9) t3] <
0, 1/2 (1/5 + 1/9) t42 + 1/2 (1/5 + 1/9) t52 +
1/2 (3/5 + 7/9) t62 == 0,
1/2 (1/5 + 1/9) t4 + 1/2 (1/5 + 1/9) t5 + 1/2 (3/5 + 7/9) t6 == 0,
Min[1/2 (1/5 + 1/9) t7 + 1/2 (1/5 + 1/9) t8 + 1/2 (3/5 + 7/9) t9,
1/2 (1/5 + 1/9) t72 + 1/2 (1/5 + 1/9) t82 +
1/2 (3/5 + 7/9) t92] < 0,
Min[1/9 t12 + 1/9 t22 + 7/9 t32, 1/9 t1 + 1/9 t2 + 7/9 t3] < 0,
Min[1/9 t42 + 1/9 t52 + 7/9 t62, 1/9 t4 + 1/9 t5 + 7/9 t6] < 0,
1/9 t72 + 1/9 t82 + 7/9 t92 == 0,
1/9 t7 + 1/9 t8 + 7/9 t9 == 0}) // TableForm


First solve all equations an insert solutions

e1 = Cases[eqs, aa_ == 0]

sol1 = First@Solve[e1]

(*   {t1 -> -t2 - 3 t3, t12 -> -t22 - 3 t32, t4 -> -t5 - (31 t6)/7,
t42 -> -t52 - (31 t62)/7, t7 -> -t8 - 7 t9, t72 -> -t82 - 7 t92}   *)

param = {t12, t22, t32, t42, t52, t62, t72, t82, t92, t1, t2, t3, t4,
t5, t6, t7, t8, t9} // Sort

paramred = {t22, t32, t52, t62, t82, t92, t2, t3, t5, t6, t8, t9}


The remanining inequations

(eqs2 = DeleteCases[eqs /. sol1 // Simplify, True]) // TableForm


Prepare combinations for the first two inequations and get it

(perm = {{a < b, c < d, e < f, a >= c + e}, {b < a, c < d, e < f,
b >= c + e}, {a < b, d < c, e < f, a >= d + e}, {b < a, d < c,
e < f, b >= d + e}, {a < b, c < d, f < e, a >= c + f}, {b < a,
c < d, f < e, b >= c + f}, {a < b, d < c, f < e,
a >= d + f}, {b < a, d < c, f < e, b >= d + f}}) // TableForm

cas12 = Cases[eqs2[[1 ;; 2]],
Min[a_, b_] >= Min[c_, d_] + Min[e_, f_] -> (And @@ # & /@ perm),
3] // Simplify

cas12 // Dimensions

(*   {2, 8}   *)

ta = Table[
cas12[[1, i]] && cas12[[2, i]], {i, 1, Length[cas12[]]}] //
Simplify


Do the same for the remaning more simple structured six inequations

cas38 = Cases[eqs2[[3 ;; 8]],
Min[a_, b_] -> {{a < 0, a < b}, {b < 0, b < a}}, 3] // Simplify

(*   {{{t6 > 0, t62 < t6}, {t62 > 0, t6 < t62}}, {{t9 > 0,
t92 < t9}, {t92 > 0, t9 < t92}}, {{t3 < 0, t3 < t32}, {t32 < 0,
t32 < t3}}, {{t9 > 0, t92 < t9}, {t92 > 0, t9 < t92}}, {{t3 < 0,
t3 < t32}, {t32 < 0, t32 < t3}}, {{t6 < 0, t6 < t62}, {t62 < 0,
t62 < t6}}}   *)

seq = Sequence @@ Map[And @@ # &, cas38, {2}]


The 12 possible inequations reduce to 8

dc = DeleteCases[Flatten[Outer[And, seq], 5] // Simplify, False]


Now build all combinations all inequations, the invalid ones later evaluate to False. You get 16 combinations of inequations, that are all valid to give solutions.

out = Outer[And, ta, dc]

dout = DeleteCases[out // Flatten // Simplify, False]


Now FindInstance a lot of soutions. Use randomsample of paramed to not always get the same solution (here 80 different ones).

(ff = Flatten[Table[FindInstance[#,
RandomSample[paramred, Length[paramred]]] & /@ dout, {10}],
2]);

Dimensions /@ {ff, Union[ff]}

(*   {{80, 12}, {80, 12}}   *)

param /. sol1 /. ff // MatrixForm Proove all of them to satisfy all eqs.

And @@ (And @@ eqs /. sol1 /. ff)

(*   True   *)


If you have a few minutes time, you get the full solution of this system set by

redList =
DeleteCases[Reduce[dout[[#]]] & /@ Range[Length[dout]] // Simplify,
False]

(*   A very large output was generated...   *)


{t12 -> 0, t22 -> 26/15, t32 -> -(26/45), t42 -> 0, t52 -> 217/18, t62 -> -(49/18), t72 -> 229/135, t82 -> -(1403/270), t92 -> 1/2, t1 -> 0, t2 -> 369/20, t3 -> -(123/20), t4 -> 0, t5 -> -(93/10), t6 -> 21/10, t7 -> -(8/5), t8 -> -(73/20), t9 -> 3/4}

I solved

{Min[1/5 t12 + 1/5 t22 + 3/5 t32, 1/5 t1 + 1/5 t2 + 3/5 t3] +
Min[1/5 t1 + 1/5 t4 + 3/5 t7, 1/5 t12 + 1/5 t42 + 3/5 t72] >=
Min[1/5 t42 + 1/5 t52 + 3/5 t62, 1/5 t4 + 1/5 t5 + 3/5 t6] +
Min[ 1/5 t2 + 1/5 t5 + 3/5 t8, 1/5 t22 + 1/5 t52 + 3/5 t82],
Min[1/5 t12 + 1/5 t22 + 3/5 t32, 1/5 t1 + 1/5 t2 + 3/5 t3] +
Min[1/5 t1 + 1/5 t4 + 3/5 t7, 1/5 t12 + 1/5 t42 + 3/5 t72] >=
Min[1/5 t72 + 1/5 t82 + 3/5 t92, 1/5 t7 + 1/5 t8 + 3/5 t9] +
Min[ 1/5 t3 + 1/5 t6 + 3/5 t9, 1/5 t32 + 1/5 t62 + 3/5 t92]}


with Maple, obtaining, in particular,

{ t8 <= 2*t1*(1/3)+t3+t7-2*t5*(1/3)-t6, t9 <= (1/3)*t1+(1/6)*t2+(1/3)*t3+(1/6)*t4+(1/3)*t7-(1/6)*t8-(1/6)*t6, -(1/3)*t12+(1/3)*t1-(1/3)*t22+(1/3)*t2+t3 <= t32, -(1/3)*t22-(1/3)*t52+(1/3)*t2+(1/3)*t5+t8 <= t82, -(1/3)*t32-(1/3)*t62+(1/3)*t3+(1/3)*t6+t9 <= t92, -(1/3)*t42-(1/3)*t52+(1/3)*t4+(1/3)*t5+t6 <= t62, t6 < -(1/3)*t4-(1/3)*t5, (1/3)*t22+(1/3)*t52-(1/3)*t2-(1/3)*t5+t32+t62-t3-t6+t7 < t72}

The above expression was subsituted in the original system instead of the two complicated inequalities and FindInstance did the rest of the job.

• Seems that Mathematica will not manage to Reduce the inequalities? It does run forever... – gwr Mar 7 '18 at 11:38
• @gwr: I think Min commands cause problems. – user64494 Mar 7 '18 at 11:56
• I would argue that "use maple to do half of my solution" is not an answer in a Mathematica forum. – user6014 Mar 7 '18 at 14:21
• @user6014: I could not solve it in Mathematica because the kernel connection was lost. – user64494 Mar 7 '18 at 17:46
• @user64494 Interesting, thank you! It clarifies at least what Mathematica has to work out for their future versions. I will wait a bit if there is no other suggestion as how to deal with the issue for those who have no Maple (me) and then I will accept your solution. – Kass Mar 7 '18 at 20:26