9
$\begingroup$

I'm asking myself for some time if the results of optimization are random. As search for stochastic and optimization gives results about stochastic optimization but does not help with the stochasticity of optimization.

Let's say we have a simple knapsack problem:

$\begin{align} &\max\; x_1 + x_2 + 2x_3\\ &\text{s.t. } x_1 + x_2 + 2x_3 \le 2\\ &x_1, x_2, x_3 \in \{0,1\}\end{align}$

There are two possible results: $x_1 = 1, x_2 = 1$, or $x_3 = 1$.

Is it true to say that, in this case, each optimal result has a probability of 50%, as we would deduce from enumeration? As I understand, this would be called random.

However, a solver could apply a deterministic heuristic, which resolves knapsack problems by setting the largest values true, which would always result in $x_3 = 1$, or vice versa. In this case, when we know about this, we should call the result deterministic.

For general optimization problems, it's nearly impossible to predict the interplay of all solution methods. Also, for larger problems it might not be feasible to enumerate all solutions.

I would assume that, if we pick a variable of a complex optimization problem, we probably couldn't tell the probability of a solution value in an optimal solution.

But we should keep in mind that there are processes in the solver which are deterministic and thus reduce randomness.

Could we say that results of sufficiently complex optimization problems are stochastic?

Update

My question aims more in the direction of if the possibility to say that the results are stochastic, and less in the direction of how it is possible to create deterministic results.

Also, what might not have been clear in the question is that it aims at the assessment of the stochasticity of the solution before the solution is known. I could ask more clearly: Can we regard the solution to a complex optimization problem, with solvers which contain random elements, as stochastic, before we solve the problem?

$\endgroup$
4
  • 1
    $\begingroup$ I expect from algorithm-suppliers that they do their utmost best to make runs reproducible. Debugging models is very difficult if results are not deterministic. $\endgroup$ Aug 15, 2022 at 15:48
  • $\begingroup$ The answers seem to be stem from a frame of looking for deterministicity. However, my question aims in the direction of if the possibility to say that the results are stochastic, as this can be a desirable property for resource allocation. $\endgroup$
    – JaBe
    Aug 15, 2022 at 16:04
  • $\begingroup$ In my opinion, this randomness is never a good thing. Horror scenario: a client runs a model, reports a problem, and you cannot reproduce. One would lose all credibility. If you want different solutions, look into using the solution pool. $\endgroup$ Aug 15, 2022 at 16:19
  • 1
    $\begingroup$ Even if the world were deterministic in the sense that, knowing the state of all particles at a given time point, we could predict exactly the next state of each particle, then using probabilities would still make sense. Probabilities would measure what we don't know or can't compute about the current state. So we would still say that there is 1/6 probability of each outcome when throwing a die, even if the actual outcome is already determined. It's the same for optimization solvers $\endgroup$
    – fontanf
    Aug 16, 2022 at 9:32

6 Answers 6

11
$\begingroup$

Usually no. All solvers worth their salt can be deterministic, and most are by default. That is, given a fixed configuration and seed for their random number generator, they always give the same solution. So for a given solver configuration finding a solution can not be seen as a random process.

You can make it stochastic

If you add random elements, you could make it stochastic. This could be any randomization in the parameters, the random seed, the order of the formulation, enabling non-deterministic multithreading, changing machine, etc.

But it's likely not very random

Even then, it's not easy to understand how it samples the solution space: preprocessing and branching strategies create a lot of bias. It's hard to sample solutions uniformly and efficiently, and there is ongoing research on the subject (see here for SAT solvers for example).

$\endgroup$
10
  • 1
    $\begingroup$ I agree, with one caveat. To make a solver's behavior deterministic, in addition to specifying a seed value you may need to throttle the solver to a single thread. When you run parallel threads, timing issues outside the control of the solver can crop up. Also, it may be worth noting that the way the problem is fed to the solver (the order of the variables, the order of the constraints) can affect the results. $\endgroup$
    – prubin
    Aug 15, 2022 at 15:28
  • $\begingroup$ Is it common behaviour with multithreading? At least the solvers I know best - Gurobi, CPlex and LocalSolver - are deterministic by default even with multithreading. Otherwise the seed and any change in values or problem order may change the results. $\endgroup$
    – Ggouvine
    Aug 15, 2022 at 17:18
  • $\begingroup$ I've observed changes in runtime behavior with CPLEX, using a specified seed and called through the Java API, when running with multiple threads. I can't recall if I've encountered that in the latest couple of versions. The Java code creating the model is single-threaded, so the model input should be the same each time. Also, as a note, the default value for the CPLEX parallel switch is "auto", which lets CPLEX choose whether or not to be deterministic. $\endgroup$
    – prubin
    Aug 15, 2022 at 17:44
  • $\begingroup$ Thank you, that's good to know! $\endgroup$
    – Ggouvine
    Aug 15, 2022 at 17:51
  • $\begingroup$ The solver may not have to be single threaded if It is very careful. It must divide the complete job into smaller tasks, create a deterministic number of threads, and assigned tasks to threads in some deterministic order. And use the one random seed which is held constant to be repeatable to initialise one random number generator per thread. During development you may need to be deterministic only on one development machine (so you can use more threads on a more powerful machine, as long as the same machine is deterministic). $\endgroup$
    – gnasher729
    Aug 16, 2022 at 16:20
8
$\begingroup$

I suspect that the answer to your question hinges more on how you understand the word stochastic than any particular insight about optimization.

Multiplicity of optima

In the example you gave, we have an optimization problem that has multiple optima. This is a fairly common situation in discrete optimization problems such as integer programs; it can also occur in nonlinear programming.

In designing optimization algorithms, we typically do not concern ourselves with multiple optima. There are cases, such as LP, where you can inspect the final tableau and state whether there are multiple optima and provide them upon request, but this is more of a "cool feature" than an "essential requirement" of a solution algorithm.

So, why aren't multiple optima a big deal?

Well, if you made your objective function correctly—that is, if it truly orders the feasible solutions according to your preferences—then if a problem has multiple optima, you are by definition indifferent between them. Therefore, it shouldn't matter to you whether the solver produces any one of the multiple optima, or selects randomly from among them, or picks the highest one according to a lexicographical tiebreaking rule like you proposed, or something else.

Viewing multiple optima stochastically

In general, the "solution" to an optimization problem is the set of solutions that provide the optimal objective function value. This set can be empty, or have multiple elements, or be a singularity. Only if it is a singularity do we say that the problem has a unique optimal solution.

You argue that when the optimal solution set has many elements, we can "view" this set stochastically. But this is true only inasmuch as we can view any set stochastically, namely, by imposing a probability distribution over its elements and claiming that we can sample from it, calculate its CDF, etc. The question you should ponder is, What do we stand to gain by introducing these additional parameters? More specifically:

  • What probability distribution over the optima makes sense?
  • Do you want a solver to actually do this random sampling? How? Why?
  • Is a random sample from the optimal solution set preferable, in some sense, to a specific or arbitrarily chosen element of the optimal solution set?

If the answer to the last question is yes, then I would suggest that there is a more fundamental issue with your optimization model: You have defined the feasible solution set and/or objective function in a way that does not truly incorporate all of your preferences.


One situation where multiple optima may be meaningful

One application of optimization is Lagrangian mechanics: By the laws of physics, systems tend to come to rest in the position that minimizes their potential energy, and this equilibrium state can therefore be modeled as an optimization problem. But the process by which the system equilibrates is, essentially, random: Random perturbations to the system knock it this way and that until it converges to a stable state. So, if a mechanical system has multiple equilibria, it may be meaningful to talk about the probability with which it attains each equilibrium according to the kinds of random perturbation present in the environment.

On the other hand, real-world systems are continuous, rather than discrete, and therefore the odds of having two solutions with exactly the same optimal potential energy is vanishingly rare. A more typical outcome would be that the potential energy is nonconvex in the parameters, and there are multiple local optima which can still represent an equilibrium state. Enumeration the local optima of a nonconvex problem is an hard problem in its own right, before we even get to speculating about the probability with which each equilibrium arises.

(I am not a physicist, so I invite any edits that improve the terminology used here.)


Randomized rounding

This isn't really related to the ideas above, but because you brought up the knapsack problem, it is worth mentioning that one heuristic for solving integer programs is to solve the LP relaxation and treat the $x_i$s as probability values for Bernoulli variables.

By randomly sampling these variables, we can sometimes generate a "pretty good" solution (but, of course, there is no guarantee that it will be optimal or even feasible). But this is different from your example, because you are proposing choosing randomly from among integer solution vectors, whereas the randomized rounding heuristic chooses the elements of the solution vector $x$ randomly and independently.

$\endgroup$
1
  • $\begingroup$ You can. assume that your calculated optimum is not exactly the real world optimum. So if you have ten different solutions with values that are close together, that's also interesting. $\endgroup$
    – gnasher729
    Aug 18, 2022 at 16:55
6
$\begingroup$

Results are only stochastic if your convergence criterion allows for that. If your convergence criterion is not met but you terminate anyway, there are no results to speak of, so this statement is conveniently consistent.

There is an element of stochasticity in all high performance solvers due to internal working limits, timeouts, RNG, etc., but as long as the solver will only converge if a certain criterion is met, it all really depends on what that criterion is.

There are methods to deterministically solve general optimisation problems to global optimality. Even in the case of multiple global solutions (different vectors with identical objective values), there are ways to deterministically find all of them, as long as the solver is told to do so.

What might vary is solution time - this is nearly always stochastic at high performance. What solution you get is something that can be controlled in many ways, even though that's not always done in practice.

$\endgroup$
5
$\begingroup$

In the example you give, the problem is not stochastic, but the solution that a potential solver gives you, in case multiple optimal solutions do exist. That is an important difference. Deterministic problems are, as the name suggests, not stochastic but multiple optimal solutions might exist. And in that case, it is up to the solver how to deal with this and there might (dependent on the solver) indeed be some stochasticity involved.

$\endgroup$
3
$\begingroup$

In Gurobi, there is a parameter called seed which "typically leads to different solution paths". But the default value is 0 (rather than some dynamically changing value), so that the solution is usually reproducible by default. I think randomly setting this parameter will make your solution stochastic.

$\endgroup$
1
  • $\begingroup$ Changing the seed selection each time and selecting an appropriated convergence criterion (see @NikosKazazakis answer) could make the solver looks stochastics to some degree. $\endgroup$ Sep 1, 2022 at 9:45
1
$\begingroup$

As @Max suggested, the answer depends on how we understand the word stochastic. For example, Lionel Pages pleads for the subjectivity of stochasticity, pointing at an ongoing scholarly debate.

In the case of a complex optimization problem, in which several solutions exist, as @Gabriel Gouvine said, we could sample the solution space - of solutions fulfilling our criteria - and from that deduce the probability of each solution, or solution value. However, the probabilities are only known after we solved the problem.

Enumerating solutions and taking the probability of each solution is the frequentist way to understand stochasticity.

Alternatively, we can understand stochasticity as subjective, as a measure of uncertainty.

In the case of a complex optimization problem, in which just one solution exists, the solution is already determinded, even if we are not able to know it before using a sophisticated solver.

In this case, the verdict to call the solution stochastic or not depends on our judgement, if we regard subjective indeterminism as subjective stochasticality or not.

If we don't accept subjective indeterminism as stochastic, the verdict to call a solution stochastic depends on the stochasticity of the solver as a random process and on the existance of several solutions. Because if there is just one solution, which is found by a random solver, it was still determined before finding it. In general, we don't know the number of solutions before solving the problem. Right now, I understand that we can only consider the unknown result of an optimization as stochastic, if we accept subjective indeterminism.

$\endgroup$

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.