The problem of ``Manhattan channel routing'' is an important subtask of VLSI circuit design [Wong et al. 1988]. Given two rows of labelled pins across a rectangular channel, we must connect like-labelled pins to one another by placing wire segments into vertical and horizontal tracks (see Figure 5). Segments may cross but not otherwise overlap. The objective is to minimize the area of the channel's rectangular bounding box--or equivalently, to minimize the number of different horizontal tracks needed.
Figure 5: A small channel routing problem.
Channel routing is known to be NP-hard, though good heuristics now make optimal solutions obtainable for commercial-grade problems. Nevertheless, it makes a good testbed for optimization algorithms. We follow the development of [Wong et al. 1988, Chapter 4,], which attacks the problem with simulated annealing. The operator set is sophisticated, involving manipulations to a partitioning of vertices in an acyclic constraint graph. If the partitioning meets certain additional constraints, then it corresponds to a legal routing, and the number of partitions corresponds to the channel size we are trying to minimize. Appendix B.2 presents our preliminary results with STAGE on this domain.