3
$\begingroup$

Given a combinatorial optimization problem, say the Traveling Salesman Problem, the optimal solution is a set of elements (edges in this case) that satisfy certain constraints (constituting to a connected two-regular spanner), for which the sum of associated values is minimal.

Question:

what is the probability, that an optimal solution (i.e. the set of constituting elements) changes after having added to each element a newly drawn random weight?

As the answer will certainly depend on certain conditions, e.g. how prominent the original optimal solution was, and on the interval from which the random numbers are drawn and also on the parameters of their distribution, these conditions should be part of the answers.

The motivation for this question is to be able to judge the "degree of correctness" of heuristics for combinatorial optimization: if an optimal solution different from a known one is reported with the same probability as the expected change due to the addition of random values, then that would speak in favor of the correctness of the algorithm.

Improve this question
$\endgroup$
1
  • 1
    $\begingroup$ This question pertains to the topic of robustness in optimization. I would just guess that a good point to start for looking into would be the MaxCut problem. Also, many optimization problems relate to finding the eigenvectors of a matrix. In that case, a small perturbation in the data might change the outcome of your solver drastically. $\endgroup$
    – Sina Baghal
    Jul 13, 2021 at 16:24

2 Answers 2

Reset to default
0
$\begingroup$

In any particular instance, we could in principle compute the probability, though in practice for a nontrivial problem it would be a very difficult computation. Assuming an objective function that is linear in the weights, for a discrete problem where the weights don't affect feasibility, the answer is the probability of the complement of a certain polytope in the space of weights, defined as the intersection of half-spaces where the given solution is better than another solution.

Improve this answer
$\endgroup$
0
$\begingroup$

This question is very interesting, but there may not be a single "correct" answer to it. One approach might be Smoothed Analysis; this perspective allows you to make (precise versions of) statements like "although this algorithm has exponential complexity, the solutions are typically invariant to small changes in the input, so the typical running time is much faster". The smoothing part seems to address your question, and has, in particular, been applied to the traveling salesman problem.

Improve this answer
$\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.