optimization – 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.