## 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

`lparse -d none -c n=58 -c radius=8 A points.lp rst.lp |
cmodels
-zc`

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

`lparse -d none -c n=58 -c radius=8 A points.lp rst.lp
heuristics.lp | cmodels -zc`

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

`lparse -d none -c n=58 -c radius=8 -c l=16 A points.lp rst.lp
restrict_length.lp | cmodels -zc`

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

`lparse -d none -c n=85 -c radius=8 A points.lp rst.lp tree.lp
| cmodels -zc`

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

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

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

`lparse -d none -c n=50 -c radius=5 fig9 points.lp rst.lp
routing.lp | cmodels -zc`

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:

- in the language of lparse (Version 1.0.13):
routing-lparse.tar.gz
(for more information, see Chapter 7 of "Theory
and Applications of Answer Set Programming," E. Erdem, Ph.D. Thesis,
Technical
Report CS-TR-02-69, Department of Computer Sciences, University of Texas
at Austin, 2002.)

- in the language of ccalc (Version 1.9):
routing-ccalc.tar.gz
(for more information, see "Wire routing
and satisfiability planning," E. Erdem, V. Lifschitz, and M. D. F.
Wong, in *Proceedings of the First International Conference on
Computational Logic (CL'00)*, pages 822-836, 2000.)