Heuristics for the MinLA problem: some theoretical and empirical considerations
Josep Dı́az, Jordi Petit, Paul G. Spirakis, Marı́a Serna · 1998
This paper deals with some aspects on finding good solutions for the Minimum Linear Arrangement problem (MinLA). We consider some random type of sparse graphs, for which it is possible to obtain trivial constant approximations. For similar graphs, we prove that Metropolis can find good solutions, whereas we exhibit an instance for which Hill Climbing is expected to need an exponential number of steps to hit an optimum. Motivated by the last results, we present an heuristic (SS+SA) to approximate the MinLA problem on sparse graphs. The heuristic consists in using Spectral Sequencing to obtain a first primal solution and after improving it locally through (Parallel) Simulated Annealing. In the last part of the paper, we report experimental results obtained with the SS+SA heuristic when applied to a set of large sparse geometric graphs. Compared to other heuristics, the measurements obtained on an IBM SP2 computer with 8 processors show that the new heuristic improves the solution quality, decreases the running time and offers an excellent speedup when ran in parallel.