An iterated local search algorithm for solving large-scale instances of the duplex arrangement problem

Abstract

The minimum multiplex arrangement problem locates each vertex of a graph on an integer point on a line, with each integer point being assigned at most $\mathfrak{m}$ vertices. The case with $\mathfrak{m}=2$, known as the minimum duplex arrangement (MinDA) problem, is investigated in this study. MinDA is $\mathcal{N}\mathcal{P}$-hard and is related to applications such as manufacturing systems design and VLSI layout. A mixed-integer linear programming formulation of MinDA is presented. The capabilities of the proposed formulation are assessed on 63 problem instances with varying densities and sizes up to 25 vertices. Additionally, an examination of the structure of an optimal MinDA solution is conducted. Based on this analysis, an iterated local search (ILS) algorithm is established, and novel strategies are developed to enhance its effectiveness. In contrast to traditional ILS approaches, where the local search phase invariably reaches a local optimum, the local search phase in the proposed algorithm may converge to a point in the vicinity of a local optimum, thereby reducing the computational burden for large-scale instances. Extensive computational experiments employing the ILS algorithm are conducted on instances with sizes n up to 10,240 vertices.

Keywords:

• VLSI design
• iterated local search
• metaheuristics

Disclosure statement

No potential conflict of interest was reported by the author(s).

Data availability statement

The data that support the findings of this study are available on request from the author.

Additional information

Funding

This study was financed in part by Coordenação de Aperfeiçoamento de Pessoal de Nível Superior, Brasil (CAPES) [Finance Code 001]; and in part by Fundação de Amparo à Pesquisa e Inovação do Espírito Santo (FAPES).