Title:Curse of Scale-Freeness: Intractability of Large-Scale Combinatorial Optimization with Multi-Start Methods

Abstract:This paper investigates the intractability of large-scale optimization using multi-start methods. For the theoretical performance analysis, we focus on random multi-start (RMS), one of the representative multi-start methods, including RMS local search and greedy randomized adaptive search procedure (GRASP). Our primary theoretical contribution is to derive, using extreme value theory, power-law formulas for the two quantities: (i) the expected improvement rate of the best empirical objective value (EOV); (ii) the expected relative gap between the best EOV and the supremum of empirical objective values. Notably, the expected relative gap exhibits scale-freeness as a function of the number of iterations. Consequently, the half-life of the expected relative gap is ultimately proportional to the number of iterations completed by an RMS algorithm. This result can be interpreted as the curse of scale-freeness -- a Zeno's paradox-like phenomenon, encapsulated by the metaphor ``reaching for the goal makes it slip away." Through numerical experiments, we observe that applying several RMS algorithms to traveling salesman problems is subject to the curse of scale-freeness. Furthermore, we show that overcoming this curse requires developing a powerful LS algorithm equipped with a diversification mechanism that is exponentially more effective than RMS.