This problem is described in the paper "Comparing ASP, CP, ILP on Wire Routing Problems", as follows:
Rectilinear Steiner Tree (RST)
construction asks for a connected graph that is composed of horizontal or
vertical line segments and that spans a given set of points such that the total
length of its edges is minimum. The decision problem version of RST
construction (i.e., whether there is a rectilinear tree of size less than or
equal to k, that connects the given points) is NP-hard.
We consider two problems: an optimization
problem RST and a decision problem that corresponds to it RST-DEC.
RST Given a subgraph G of a
rectangular grid, a source point s, and a set S of sink points, find a minimal
path connecting each sink node to source node.
RST-DEC Given a subgraph G of a
rectangular grid, a source point s, a set S of sink points, and an integer k,
decide that there is a subgraph of G such that each sink point is connected to
source node and total length of the path is less than k.
In the
following we present formulations of RST-DEC for each of the programming
paradigms: Constraint Programming, Integer Linear Programming, and Answer Set
Programming. First, we formalized the RST-DEC problem in a straight-forward
way. In order to test elaboration tolerance and observe performance changes, we
can add two kinds of heuristics constraints to
these formulations. Formulations are in the language of OPL (in the case of CP and ILP), and in the language of lparse (in the case of ASP).
|
Formulation |
CP |
ILP |
|
RST-DEC |
||
|
RST-DEC with heuristics |
||
|
RST |
Formulations
in the language of lparse are in this
webpage.
There is
another approach for solving RST construction problem: flow-based formulation.
All of the formulations including the flow-based approach are in one file: rst-tree&flow-models.zip.
With these files, we can solve problem instances of RST-DEC using clasp for
ASP, and using ILOG-OPL for CP and ILP. 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 detailed information about lparse commands, please visit this page.
In OPL, we run programs (*.mod files) with data files (*.dat files) and different options for CP and ILP. There are two types of data files. While optimizing the problem, we exclude all constraints of heuristics and path length restriction. If the file name includes “opt”, then you should use this data file to solve the problem; otherwise this data file should be used. As each data file includes four problems’ data, you need to command the other three problems.
The options -conflict and -relax are included only for CP
formulations. For instance, a solution to problem A can be computed by the following command in OPL, for CP:
oplrun -v -conflict -relax rst-tree-cp.mod rst-data.dat
and for ILP:
oplrun -v rst-tree-ilp.mod rst-data.dat
If OPL is running through a IDE, such as ILOG, you may change the options by including a *.ops file into the project. For more details, you may visit the ILOG web site.
In order to solve the original problem RST, we can run these commands with RST-DEC formulations for different values of n (search for a path with minimal length n that terminates with decision “YES”), or we can use the RST formulations (obtained by modifying RST-DEC formulations) to find the minimal value of n. When running RST formulations, we discard the parameter n and radius.
The options
-conflict and -relax are included only for CP formulations. For instance, a solution to
problem A can be computed by the following
command in OPL, for CP:
oplrun -v -conflict -relax rst-tree-cp-opt.mod rst-data-opt.dat
and for ILP:
oplrun -v rst-tree-ilp-opt.mod rst-data-opt.dat
With the formulations above, we tried to solve four problem instances of RST using the answer set solver CMODELS (Version3.74) with LPARSE (Version 1.0.17) and MINISAT (Version 2.0), and OPL (Version 5.5) on a machine with Xeon 1.5GHz CPU with 4x512MB RAM running RedHat Linux (Version 4.3).
The experimental results can be found here: rst-results.pdf.