# How important is initial state for local search optimisation?

I have been enjoying Pascal van Hentenryck's Discrete Optimisation course and we're in Week 4 on the wonders of Local Search algorithms for combinatorial optimisation.

I'm wondering how important the initial configuration is to the quality of solution achievable in a fixed time or, somewhat equivalently, how quickly a solution of a given quality can be reached.

So if I have a good heuristic or intuition for how to arrange things in the first place, is it helpful to devote some processing time to setting that up or is it all dominated by the effect of the local search process?

For example, in the Cartesian Travelling Salesman Problem (where we're working in a 2D plane and the cost of a journy is simply the straight-line distance) I might "feel" that a good route could roughly follow a clockwise sweep from the centre of the space. So I could use this to set my initial tour (i.e. order the nodes by their angle from the mean of all points). This intuition might be rubbish for certain instances and great for others, I was hoping to see a study where (let's say random TSP) instances had been solved by following a heuristic first state as opposed to a completely random (but legal) first state.

• Given a lack of details in the question, I can only give a broad answer: in general, an initial configuration can be extremely important. Local search is often used for NP-hard problems, some even without any finite polynomial-time approximation (assuming $P \ne NP$). Of course, if you start directly from the optimal solution, you'll get a much better answer than if you start from a random configuration. – Dmitry Sep 11 '20 at 11:17
• Thank you @Dmitry; you're right, my question is a little vague. I guess I was hoping that some studies had been done on specific problems - I've search Google Scholar, but not found anything that fits. I will amend my problem question with a slightly more concrete example. – Mr Felix U Sep 11 '20 at 11:39
• I don't know about TSP, but maybe the following somehow answers your general question: 1) One advantage of local search is that it can be applied after any other algorithm. Since a) it can only improve a solution and b) some solutions often outperform randomly initialized local search, one can say that initialization is important. (Note however, that local search probably won't improve a good solution too much). 2) One may think about k-means as a local search algorithm In this case, en.wikipedia.org/wiki/K-means%2B%2B initialization provides some guarantees, why a random one don't. – Dmitry Sep 11 '20 at 13:43
• The initial state is of utmost importance. For example, if the initial state is a global optimum, then the algorithm is guaranteed to perform optimally. In practice, one often tries many different initial states. – Yuval Filmus Sep 11 '20 at 19:35