A Variable Formulation Search Approach for Three Graph Layout Problems

This paper studies the relationship between three linear layout problems: minimum linear arrangement, cutwidth minimization, and bandwidth minimization. Our research suggests that, given their correlation, optimizing one problem could optimize the others. The Variable Neighborhood Search metaheuristic can take advantage of this, especially by switching problem formulations during the search process. The paper presents experiments analyzing different strategies and provides insights about their effectiveness. Our findings indicate that the proposed variant of Variable Neighborhood Search outperforms traditional single-process optimization methods in terms of both solution quality and computational efficiency.