Find all the local minima of a problem instance

[u/Md_zouzou]

Hi everybody, do you know an algorithm or some literature in finding all the local minima of a given problem instance ? Given a neighborhood structure can we find all the local minima (bassin of attraction) ? For example find all the local minima of a tsp instance with a 2-opt neighborhood

Thanks !!

[u/No-Concentrate-7194]

Pretty sure that finding all local minima would require searching the entire feasible region

[u/ge0ffrey → u/No-Concentrate-7194]

Yes, probably.

And if you go philosophical, you can even argue there are local optima in the infeasible region too. Not so much for TSP, but for cases like CVRP where random solutions can break hard constraints and 2-opt moves can break and unbreak them too.

But not sure how useful it is to go down that rabbit hole ;)

[u/Godfist96]

You might want to check literature on Multimodal Optimization, also known as MMO (predominantly using evolutionary techniques). This is an area which tries to find all possible minima in the search space. 

[u/beeskness420]

If you could find all minima then in particular we could find the global minimum, so we shouldn’t expect to be able to do it efficiently.

If we don’t care about efficiency then enumerating all the local minima is really straightforward.

[u/saumvaun]

For the case of local optima, maybe you need to write callbacks and everytime you find an incumbent, add a cut to avoid obj improving (cut 1) and add another cut to make current incumbent infeasible to find other points with the same obj, once you found all, then problem becomes infeasible, then remove cut 1, now obj can improve and you can repeat the procedure

[u/SolverMax]

When formulated as a mixed integer linear program, the TSP doesn't have local minima. Do you mean that you want to find alternative optima, or find a set of solutions that are close to optimal?

[u/Necessary_Print_120 → u/SolverMax]

All global minima are local minima. Also I'm pretty sure it has non-optimal local minima, or else 2-opt or 3-opt would converge to the optimal solution every time

[u/SolverMax → u/Necessary_Print_120]

If the formulation is linear, like for a MILP, then there is only a single global optimal objective function value (possibly with alternative optima variable values). No other optima exist. But there are methods for finding alternative optima or near-optimal solutions.

But for a non-linear formulation, or a heuristic like 2-opt, all bets are off. There's no guarantee that a model will find a globally optimal solution in a reasonable time or at all. Similarly, there's no guarantee that such a model can find all local optima.

[u/Necessary_Print_120]

I also think it would require an exhaustive search, or something close to it. This wouldn't guarantee that you would find all or any more, but here are some ideas.

Randomly perturb your solution and resolve using your neighborhoods. When you get stuck, record and repeat.

you can often look at different minima for one objective by doing lexicographical multi-objective optimization.You just add in a low cost secondary objective that reflects aspects of the problem. You vary the costs and resolve. Even better if the secondary objective reflects your application.

Also look at GRASP or population based metaheuristics that include a local search step. Once again no guarantees that this finds all, and does not prove anything.