Rectilinear Steiner Tree Construction

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.

Problem Formulations

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-tree-cp.mod

rst-tree-ilp.mod

RST-DEC with heuristics

rst-tree-cp-heuristics.mod

rst-tree-ilp-heuristics.mod

RST

rst-tree-cp-opt.mod

rst-tree-opt.mod

 

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.

RST-DEC

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.

 

RST

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

Experimental Results

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.