0
$\begingroup$

I have this Solve:

Solve[6x1 + 30x2 + 8x3 + 15x4 - 3x5 + 2x7 == 1325 && -5x1 + 6x4 - x5 + 7x6 + 9x7 == 800 && 10 <= x1 <= 80 && 12 <= x2 <= 146 && 15 <= x3 <= 299 && 9 <= x4 <= 30 && 16 <= x5 <= 172 && 19 <= x6 <= 672 && 8 <= x7 <= 9, {x1, x2, x3, x4,x5, x6, x7}, Integers]

It returns 164254 results, which is very long. Is there a way to limit the number of returns to 100? What I am looking for is a way to avoid situations where Solve wants to return a large amount of data and limit that to some small number, to avoid unnecessary cpu usage. FindInstance is not an options, as it keeps running until I abort:

FindInstance[6x1 + 30x2 + 8x3 + 15x4 - 3x5 + 2x7 == 1325 && -5x1 + 6x4 - x5 + 7x6 + 9x7 == 800 && 10 <= x1 <= 80 && 12 <= x2 <= 146 && 15 <= x3 <= 299 && 9 <= x4 <= 30 && 16 <= x5 <= 172 && 19 <= x6 <= 672 && 8 <= x7 <= 9, {x1, x2, x3, x4,x5, x6, x7}, Integers, 100]
$\endgroup$
6
  • $\begingroup$ Welcome to the Mathematica Stack Exchange. An alternative command to try in this case would be: FindInstance[x1 + x2 == 1000000, {x1, x2}, PositiveReals, 10] which gives you 10 results. $\endgroup$
    – Syed
    Nov 3, 2023 at 3:42
  • $\begingroup$ it returns only two results in V 13.3.1, which version are you using? !Mathematica graphics $\endgroup$
    – Nasser
    Nov 3, 2023 at 3:42
  • $\begingroup$ I edited my question to reflect on your comments. The first version was a simplified one. I inserted a new system of equations to be solved by Solve[] $\endgroup$
    – Dani
    Nov 3, 2023 at 4:18
  • $\begingroup$ There is no option for Solve to limit the number of solutions. So if FindInstance does not work you, then I think you are out of luck. Why not just get all the solutions from Solve and then trim them to the number you want? any way. I do not see an option for what you want with Solve. $\endgroup$
    – Nasser
    Nov 3, 2023 at 5:02
  • $\begingroup$ What about MaxExtraConditions option? Do you think it can be of any help? $\endgroup$
    – Dani
    Nov 3, 2023 at 5:07

2 Answers 2

0
$\begingroup$

One of the ways is as follows.

Solve[6 x1 + 30 x2 + 8 x3 + 15 x4 - 3 x5 + 2 x7 == 
1325 && -5 x1 + 6 x4 - x5 + 7 x6 + 9 x7 == 800 && 10 <= x1 <= 80 &&
12 <= x2 <= 146 && 15 <= x3 <= 299 && 9 <= x4 <= 30 && 
16 <= x5 <= 172 && 19 <= x6 <= 672 && 8 <= x7 <= 9, {x1, x2, x3, 
x4, x5, x6, x7}, Integers][[1 ;; 10]]

{{x1 -> 10, x2 -> 12, x3 -> 67, x4 -> 29, x5 -> 28, x6 -> 89, x7 -> 9}, {x1 -> 10, x2 -> 12, x3 -> 70, x4 -> 30, x5 -> 41, x6 -> 90, x7 -> 9}, {x1 -> 10, x2 -> 12, x3 -> 71, x4 -> 27, x5 -> 28, x6 -> 92, x7 -> 8}, {x1 -> 10, x2 -> 12, x3 -> 73, x4 -> 24, x5 -> 19, x6 -> 92, x7 -> 9}, {x1 -> 10, x2 -> 12, x3 -> 74, x4 -> 28, x5 -> 41, x6 -> 93, x7 -> 8}, {x1 -> 10, x2 -> 12, x3 -> 76, x4 -> 25, x5 -> 32, x6 -> 93, x7 -> 9}, {x1 -> 10, x2 -> 12, x3 -> 77, x4 -> 22, x5 -> 19, x6 -> 95, x7 -> 8}, {x1 -> 10, x2 -> 12, x3 -> 77, x4 -> 29, x5 -> 54, x6 -> 94, x7 -> 8}, {x1 -> 10, x2 -> 12, x3 -> 79, x4 -> 26, x5 -> 45, x6 -> 94, x7 -> 9}, {x1 -> 10, x2 -> 12, x3 -> 80, x4 -> 23, x5 -> 32, x6 -> 96, x7 -> 8}}

$\endgroup$
3
  • $\begingroup$ This is interesting. It actually solves for all the solutions, but only returns the first 10 ones. right? BTW, do you think Method-> can be of any help here? Solve and FindInstance, probably, are using different methods to solve this system of equations. If one knows what Method is Solve using and add that to FindInstance, it is likely to work. Although I know that the Methods used by Mathematica are not public. $\endgroup$
    – Dani
    Nov 5, 2023 at 16:50
  • $\begingroup$ The only described method of Solve is Method->Reduce. Its application here does no effect. $\endgroup$
    – user64494
    Nov 5, 2023 at 19:18
  • $\begingroup$ Here What Method options does FindInstance accept? it was discussed, but there are too many options available. I don't think it helps. $\endgroup$
    – Dani
    Nov 5, 2023 at 21:00
0
$\begingroup$

A really simple way to get less solutions is to make your constraints tighter. Here I change the first constraint to be 10<=x[1]<=10 instead of 10<x[1]<80, and I do the same with the constraint on x[2]

A = {{6, 30, 8, 15, -3, 0, 2},
   {-5, 0, 0, 6, -1, 7, 9}};
b = {1325, 800};
xArr = Array[x, 7];
cons = 10 <= x[1] <= 80 && 12 <= x[2] <= 146 && 15 <= x[3] <= 299 && 
   9 <= x[4] <= 30 && 16 <= x[5] <= 172 && 19 <= x[6] <= 672 && 
   8 <= x[7] <= 9;
cons[[1, -1]] = 10;
cons[[2, -1]] = 12;
sol = Solve[A . xArr == b && cons, Integers];
Length@sol
(*122*)

This is not great really, because this is a very specific region of the solutions. A random sample from the constrained solution space is probably more what you want, but I am not sure how to accomplish that.

Notice however that since this is just a linear system, we can find one solution to the problem, and any other solution will be that solution plus the matrix's null space (dotted with a vector):

(*find one solution on the integers*)
f0 = FindInstance[A . xArr == b, xArr, Integers] // Values // Flatten;
(*any other solution will be f0 plus a vector dotted with the null \
space*)
ns = NullSpace[A];
kArr = Array[k, Length@ns];
solnForm = kArr . ns + Threaded[f0];
(*since the null space has 5 vectors we reduce to a 5 variable \
constrained solution*)
constrained = 
 Table[cons[[i]] /. xArr[[i]] -> solnForm[[i]], {i, Length@solnForm}]

(*{10 <= 135 k[1] + 35 k[2] - 10 k[3] + 60 k[4] <= 80, 
 12 <= -32 k[1] - 7 k[2] + 7 k[3] - 37 k[4] - 4 k[5] <= 146, 
 15 <= 15 k[5] <= 299, 9 <= 50 k[4] <= 30, 16 <= 7 + 50 k[3] <= 172, 
 19 <= -750 + 25 k[2] <= 672, 8 <= 673 + 75 k[1] <= 9}*)

Maybe there is some way to use this to find more randomly-spaced solutions in your constrained solution space?

$\endgroup$
6
  • $\begingroup$ One of the results of sol = Solve[A . xArr == b && cons, Integers] is {x[1] -> 10, x[2] -> 12, x[3] -> 154, x[4] -> 9, x[5] -> 160, x[6] -> 125, x[7] -> 9}. Now (6 x1 + 30 x2 + 8 x3 + 15 x4 - 3 x5 + 2 x7 == 1325 && -5 x1 + 6 x4 - x5 + 7 x6 + 9 x7 == 800 && 10 <= x1 <= 80 && 12 <= x2 <= 146 && 15 <= x3 <= 299 && 9 <= x4 <= 30 && 16 <= x5 <= 172 && 19 <= x6 <= 672 && 8 <= x7 <= 9) /. {x[1] -> 10, x[2] -> 12, x[3] -> 154, x[4] -> 9, x[5] -> 160, x[6] -> 125, x[7] -> 9} results in $\endgroup$
    – user64494
    Nov 3, 2023 at 16:23
  • $\begingroup$ 6 x1 + 30 x2 + 8 x3 + 15 x4 - 3 x5 + 2 x7 == 1325 && -5 x1 + 6 x4 - x5 + 7 x6 + 9 x7 == 800 && 10 <= x1 <= 80 && 12 <= x2 <= 146 && 15 <= x3 <= 299 && 9 <= x4 <= 30 && 16 <= x5 <= 172 && 19 <= x6 <= 672 && 8 <= x7 <= 9, not True. $\endgroup$
    – user64494
    Nov 3, 2023 at 16:23
  • $\begingroup$ I am using x[1], x[2],...,x[7] for variable names instead of x1,x2,...,x7 for variable names (I did this because it felt easier to just write xArr = Array[x, 7];). If you change my variables back to their original names (x1,x2,...,x7) it works: $$ $$ (6 x1 + 30 x2 + 8 x3 + 15 x4 - 3 x5 + 2 x7 == 1325 && -5 x1 + 6 x4 - x5 + 7 x6 + 9 x7 == 800 && 10 <= x1 <= 80 && 12 <= x2 <= 146 && 15 <= x3 <= 299 && 9 <= x4 <= 30 && 16 <= x5 <= 172 && 19 <= x6 <= 672 && 8 <= x7 <= 9) /. {x1 -> 10, x2 -> 12, x3 -> 154, x4 -> 9, x5 -> 160, x6 -> 125, x7 -> 9} (*True*) $\endgroup$
    – ydd
    Nov 3, 2023 at 16:31
  • $\begingroup$ Sorry for the confusion I should've specified I changed the names of the variables. $\endgroup$
    – ydd
    Nov 3, 2023 at 16:32
  • $\begingroup$ Thank you for your explanation. It is not so simple. How "to make your constraints tighter" if one wants 15 solutions? 360 items? My code takes 11.2831 s, not so much. $\endgroup$
    – user64494
    Nov 3, 2023 at 17:05

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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