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 vertices. The case with , known as the minimum duplex arrangement (MinDA) problem, is investigated in this study. MinDA is -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.
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.