Adaptive large neighborhood search applied to the design of electronic circuits

Abstract In this paper, a new algorithm is proposed for solving the Gate Matrix Layout Problem (GMLP). This combinatorial problem is NP -Hard and aims to determine the physical layout of the components of an electronic circuit in order to minimize the number of tracks required to connect its nets. By reducing the circuit area, it is possible to reduce manufacturing costs and also improve circuit performance. Computer-aided design of such layouts has direct practical applications in engineering and industry, including information technology, industrial processes automation, and consumer goods production. We propose new local search procedures combined in an Adaptive Large Neighborhood Search (ALNS) metaheuristic to generate solutions for the GMLP. To assess the quality of the proposed method, we have considered 1455 real-world and artificial instances from the literature and compared the proposed ALNS with the state-of-the-art method for the GMLP solution. The ALNS performance is robust as it matches 89% of known optimal solutions and also improves the best known results in some instances.