Rectilinear Steiner Tree Construction

We describe RST construction in the language of lparse (Version 1.0.13) as in "Rectilinear Steiner Tree Construction using Answer Set Programming," by E. Erdem and M. D. F. Wong, in Proc. of ICLP'04, 2004.

The files describing the RST construction domain (rst.lp), some RST routing problems shown in figures (fig2, fig4) or used in our experiments (A, B, C, D), with the grid-points not covered by the obstacles (points.lp), and the other files mentioned below are enclosed in rst-lparse-basic.tar.gz.

With these files, we can solve RST construction problems using cmodels (with zchaff). For instance, a solution to problem A, with n=58 and radius=8, can be computed by the command

For a more efficient computation, we can add to the domain description noadjacency constraints and some other constraints presented in the file heuristics.lp:

To restrict the lengths of paths in an RST construction problem, we need the file restrict_length.lp. For instance, a solution to problem A, with n=58 and radius=8, where every path connecting a sink point to the source point is at most l=16, can be computed by the command

To construct a tree, that may not be an RST, we need the file tree.lp. For instance, a tree connecting the sink points to the source point in problem C, with n=85 and radius=8, can be computed by the command

Note that adding the file tree.lp above makes the domain description nontight.

For larger problems, you can try problems E and F.

Other Wire Routing Problems

To solve wire routing problems where pairs of pins are connected, in addition to rst.lp and points.lp, we need the file routing.lp. For instance, a solution to problem fig9 shown in Figure 9, with n=50 and radius=5, can be computed by the command

Some other routing problems of this kind (p7, p15, p20, p25) and the file routing.lp are enclosed in rst-lparse-basic.tar.gz.

Other ASP formalizations of wire routing problems where pairs of pins are connected: