0
$\begingroup$

Ok, so I have a problem where I have a function that depends on 9 parameters and a bound condition

$$f(x,y,z,w,t,u,v,r,s)<K$$

Now all these variables take discrete values such as:

$$x \in \{x_1, x_2,x_3,..., x_X \}$$ $$y \in \{y_1, y_2,y_3,..., y_Y \}$$

etc. Now I am using backtrack serach to find all combinations for these values that verify the condition.

I manage to do this in an acceptable way when the variables each take 4 discrete values, so the problem has a complexity of $4^9=262144$, taking little over 3 minutes to do the task. The problem is that when the lists increase it no longer takes an acceptable time. Every variable with 5 discrete values, Mathematica simply can't solve it (maybe if I've waited days but that is not the goal).

Now the fact is that it is unnecessary to test all combinations. Each value $x_1$, $x_2$, etc. represent prices from the most expensive to the cheapest solution. My idea is too find the set of most expensive solutions that means that if I find the solution

$$[3, 3, 2, 2, 3, 2, 2, 3, 3]$$

I don't care about the solution

$$[2, 3, 2, 2, 3, 2, 2, 3, 3] $$

where I just replaced the first value with a smaller one but I do care about the solution

$$[2, 3, 3, 2, 3, 2, 2, 3, 3]$$

where I have switched $x$ and $z$.

How would you do this in an easy way? I need some ideas...

A small workable example of what I did so far,

InitTime = AbsoluteTime[];
values={3,2,1,0.5}
{x,y,z,w,t,u,v,r,s} = {values, values, values, values, values, values, values, values, values};
f[x, y_, z_, w_, t_, u_, v_, r_, s_] := Sqrt[30.7912 y^2 + 30.7912 w^2 + 92.3941 u^2 + 0.641399 z^2 + 0.641399 t^2 + 74.5364 v^2 + 74.5364 s^2 + 5.60933 x^2 + 0.277617 y^2]
k = 8.83;
ResourceFunction["BacktrackSearch"][{x, y, z, w, 
  t, u, v, r, s}, 
 Length[#] <= 9 &, (f @@ #) < k &, All]
AbsoluteTime[] - InitTime
Improve this question
$\endgroup$
5
  • $\begingroup$ Please provide Mathematica code you have used so far. $\endgroup$
    – Domen
    Commented Dec 29, 2022 at 23:31
  • $\begingroup$ Is your $f$ linear or non-linear? An example of $f$ would be useful to determine which approach is best. $\endgroup$
    – flinty
    Commented Dec 29, 2022 at 23:52
  • $\begingroup$ Just provided a small example! $\endgroup$
    – Granger Obliviate
    Commented Dec 30, 2022 at 0:20
  • $\begingroup$ Caveat, I only just now read the documentation for the BacktrackSearch resource function. It's not clear to me that your Length <= 9 test is actually doing anything. I would have thought that you need to somehow encode the logic of "whether to keep going in this direction". So, shouldn't it somehow encode your comments about knowing that certain expensive solutions tell you which other candidates you can ignore? $\endgroup$
    – lericr
    Commented Dec 30, 2022 at 0:45
  • $\begingroup$ Your example is completely monotonic, so just choosing the largest element of values for each variable would give you the unique maximum (ignoring duplicates). If you had some minuses in there or other functions that aren't just increasing, then it would be harder. Is this just a fake problem; is your real problem quadratic / convex / linear / or have you some harder non-linear $f$ ? You might want to look at ResourceFunction["AntColonyOptimization"]. $\endgroup$
    – flinty
    Commented Dec 30, 2022 at 3:17

0

Reset to default

Your Answer

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