An evolutionary constraint satisfaction solution for over the cell channel routing

Abstract

A novel evolutionary assignment-ordering approach for combinatorial optimization using constraint satisfaction problem (CSP) modeling is presented. In the assignment of values to variables, the order of assignment is determined by an ordering function combined with problem-specific features. No a priori information is available on the assignment-ordering function and it is completely determined by evolutionary optimization to produce the best assignment results. Indeed, experimental evaluations show that the proposed method outperforms very well-known approaches for the solution of NP-hard combinatorial optimization problems from VLSI layout design, namely, channel routing and multi-layer over the cell channel routing. (C) 2004 Elsevier B.V. All rights reserved.